# The Simonovits-Sos Conjecture was Proved by Ellis, Filmus and Friedgut

Let $\cal F$ be a family of graphs with N={1,2,…,n} as the set of vertices. Suppose that every two graphs in the family have a triangle in common. How large can $\cal F$ be?

(We talked about it in this post.)

One of the most beautiful conjectures in extremal set theory is the Simonovich-Sos Conjecture, the proposed answer to the question above:

Let $\cal F$ be a family of graphs with N as the set of vertices. Suppose that every two graphs in the family have a triangle in common. Than $|{\cal F}| \le 2^{{{n}\choose {2}}-3}$.

A few weeks ago David Ellis, Yuval Filmus, and Ehud Friedgut proved the conjecture. The paper is now written. The proof uses Discrete Fourier analysis/spectral methods and is quite involved. This is a wonderful achievement.

The example showing that this is tight are all graphs containing a fixed triangle.

Vera Sos’s, a great mathematical hero of mine, is ageless. Nevertheless, she had a birthday conference in early September.  The paper by Ellis, Filmus, and Friedgut is dedicated to Vera on the occasion of her birthday. What a nice birthday gift!

Let me add my own wishes: Happy birthday, Vera!

# Polymath3: Polynomial Hirsch Conjecture 4

So where are we? I guess we are trying all sorts of things, and perhaps we should try even more things. I find it very difficult to choose the more promising ideas, directions and comments as Tim Gowers and Terry Tao did so effectively in Polymath 1,4 and 5.  Maybe this part of the moderator duty can also be outsourced. If you want to point out an idea that you find promising, even if it is your own idea, please, please do.

This post has three parts. 1) Around Nicolai’s conjecture; 1) Improving the upper bounds based on the original method; 3) How to find super-polynomial constructions? Continue reading

# A New Appearance

I have changed the appearance of the blog. The main feature of the new appearance that I like is that the comments are with the same size fonts as the posts themselves. This is especially useful for the polymath3 posts. (I will make some tuning to the new appearance once I will learn how to.)

# Benoît’s Fractals

Mandelbrot set

Benoît Mandelbrot passed away a few dayes ago on October 14, 2010. Since 1987, Mandelbrot was a member of the Yale’s mathematics department. This chapterette from my book “Gina says: Adventures in the Blogosphere String War”   about fractals is brought here on this sad occasion.

A little demonstration of Mandelbrot’s impact: when you search in Google for an image for “Mandelbrot” do not get pictures of Mandelbrot himself but rather pictures of Mandelbrot’s creation. You get full pages of beautiful pictures of Mandelbrot sets

.

Benoit Mandelbrot (1924-2010)

Modeling physics by continuous smooth mathematical objects have led to the most remarkable achievements of science in the last centuries. The interplay between smooth geometry and stochastic processes is also a very powerfull and fruitful idea. Mandelbrot’s realization of the prominence of fractals and his works on their study can be added to this short list of major paradigms in mathematical modeling of real world phenomena.

## Fractals

Fractals are beautiful mathematical objects whose study goes back to the late 19th century. The Sierpiński triangle and the Koch snowflake are early examples of fractals which are constructed by simple recursive rules. Continue reading

# Budapest, Seattle, New Haven

Here we continue the previous post on Summer 2010 events in Reverse chronological order.

## Happy birthday Srac

In the first week of August we celebrated Endre Szemeredi’s birthday. This was a very impressive conference. Panni, Endre’s wife, assisted by her four daughters, organized a remarkable exhibition by mathematicians who are also artists. Panni also organized tours and activities for accompanying people which my wife told me were great. A few mathematicians chose to attend the tours rather than the lectures. In Hungary, Endre has a nickname “Srac” which means “kid”, and, to my amazement, people (including young people) really call him Srac.

Szemeredi Kati and Zsuzsa

### After-dinner speech. The distinction between surprising and amazing, and the question of do we age when it comes to our emotions and inner soul experiences

Being asked to give the after-dinner speech for Endre in the festive boat dinner ranks second in my life among cases where I was chosen for a job for which so many others were much, much more deserving and qualified. Continue reading

# Mabruk Elon, India, and More

I am starting this post in Jaipur. My three children are watching a movie in our Jaipur hotel room and I watch them while I begin to write this post. Hagai is in the middle of a long-planned three-month trip to India, and when I told my family about the ICM in Hyderabad, my two other children Neta and Lior jumped at the opportunity, and decided to come to India for three weeks, and in the last week give me a taste of India.  Hagai started his visit in Leh and experienced the flooding there. By the time we heard about it, already two days after the flooding, the Israeli foreign office’s emergency room had already made contact with the Israelis in Leh, including Hagai.  Hagai decided to stay in Leh to help clean houses and (mainly) the local hospital of the huge amounts of mud. He spent almost a month there and took a bus to meet me at Delhi. Neta and Lior were in Hampi, before we all met in Agra.

India is overwhelming and I do not even begin to comprehend her. Perhaps it will be easier to comprehend why so many young Israelis fall in love with India.

In this post (which I split to two parts), I wish to describe some of my Summer 2010 excitements in reverse chronological order.

Before that, here are the slides of my lecture on combinatorial and topological aspects of Helly-type theorems from the Szemeredi birthday conference, and my laudation paper and lecture slides on Dan Spielmen’s work from ICM 2010.

## ICM 2010, India

Monday evening was the end of the fourth day in ICM 2010. ICM stands for the International Congress of Mathematicians. This is an event that has taken place once every four years for over a century. This was the second meeting of the Combinatorics session featuring Henry Cohn, Brendan McKay and Benny Sudakov as invited speakers.  It was followed by a session of short 15-minute communications in combinatorics. Laci Lovasz, the president of IMU, had a lot on his mind in these four days. Due to his duties he had to miss many important lectures and events, but he nevertheless set aside time to attend this “contributed talks” session and I found it very nice. Continue reading

# Test Your Intuition (13): How to Play a Biased “Matching Pennies” Game

Recall the game “matching pennies“. Player I has to chose between ‘0’ or ‘1’, player II has to chose between ‘0’ and ‘1’.No player knows what is the choice of the other player before making his choice. Player II pays to player I one dollar if the two number match and gets one dollar from player I  if they do not match.

The optimal way to play the game for each of the player is via a mixed strategy. Player I has to choose ‘0’ with probability 1/2 and ‘1’ with probability 1/2. And so is player II.

Now, suppose that the game is the same except that if the outcomes match and both player chose ‘1’ player II pays 5 dollars to player I and not one dollar. (All other payoffs remain at one dollar.)

Test your intuition: What is the probability player I should play ‘1’. (More than 1/2? less than 1/2? more than 1/3? less than 1/3? more than 2/3? less than 2/3?)