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

Simonovits and Sos asked:

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?)

Continue reading

Polymath3 : Polynomial Hirsch Conjecture 3

Here is the third research thread for the polynomial Hirsch conjecture.  I hope that people will feel as comfortable as possible to offer ideas about the problem we discuss. Even more important, to think about the problem either in the directions suggested by others or on their own. Participants who follow the project and think about the issues without adding remarks are valuable.

The combinatorial problem is simple to state and also everything that we know about it is rather simple. At this stage joining the project should be easy.

Let me try to describe (without attemting to be complete) one main direction that we discuss. This direction started with the very first comment we had by Nicolai.

Please do not hesitate to repeat an idea raised by yourself or by other if you think it can be useful.

Thinking about multisets (monomials).

Let f^*(d,n) be the largest number of disjoint families F_1, F_2, ..., F_t of degree d monomials in the variables x_1,\dots,x_n such that

(*) for i < j < k, whenever m_1 \in F_i and m_2 \in F_k, then there exists a monomial u \in F_j such that gcd(m_1, m_2) | u.

Nicolai’s conjecture:

f^*(d,n)=d(n-1)+1.

The example that supports this conjecture consists of families with a single monomial in every family.

The monomials are

x_1^d,

x_1^{d-1}x_2,

\dots,

x_2^d,

x_2^{d-1}x_3,

\dots,

x_n^d.

There are other examples that achieve the same bound. The bound can be achieved by families whose union include all monomials, and for such families the conjecture is correct.

The case d=3.

An upper bound by EHRR (that can be extended to monomials) following works of Barnette and Larman on polytopes is f^*(d,n) \le 2^{d-1}n. For degree 3 monomials we have a gap

3n-2\le f^*(3,n) \le 4n-1.

It may be the case that understanding the situation for d=3 is the key for the whole problem.

There is another example achieving the lower bound that Terry found

F_i := \{ \{a,b,c\}: a+b+c = i+2 \} i=1,2,\dots 3n-2

More examples, please…

Various approaches to the conjecture

Several approaches to the cojecture were proposed. Using clever reccurence relations, finding useful ordering, applying the method of compression, and algebraic methods. In a series of remarks Tim is trying to prove Nicolai’s conjecture. An encouraging sign is that both examples of Nicolai, Klas, and Terry come up naturally. One way to help the project at this stage would be to try to enter Tim’s mind and find ways to help him “push the car”. In any case, if Nicolai’s conjecture is correct I see no reason why it shouldn’t have a simple proof (of course we will be happy with long proofs as well).

Constructions

Something that is also on the back of our minds is the idea to find examples that are inspired from the upper bound proofs. We do not know yet what direction is going to prevail so it is useful to remember that every proof of a weaker result and every difficulty in attempts to proof the hoped-for result can give some ideas for disproving what we are trying to prove.

Some preliminary attempts were made to examine what are the properties of examples for d=3 which will come close to the 4n bound. It may also be the case that counterexamples to Nicolai’s conjecture can be found for rather small values of n and d.

Two polls:

Polymath 3: The Polynomial Hirsch Conjecture 2

Here we start the second research thread about the polynomial Hirsch conjecture.  I hope that people will feel as comfortable as possible to offer ideas about the problem. The combinatorial problem looks simple and also everything that we know about it is rather simple: At this stage joining the project should be very easy. If you have an idea (and certainly a question or a request,) please don’t feel necessary to read all earlier comments to see if it is already there.

In the first post we described the combinatorial problem: Finding the largest possible number f(n) of disjoint families of subsets from an n-element set which satisfy a certain simple property (*).We denote by f(d,n) the largest possible number of families satisfying (*) of d-subsets from {1,2,…,n}.

The two principle questions we ask are:

Can the upper bounds be improved?

and

Can the lower bounds be improved?

What are the places that the upper bound argument is wasteful and how can we improve it? Can randomness help for constructions? How does a family for which the upper bound argument is rather sharp will look like?

We are also interested in the situation for small values of n and for small values of d. In particular, what is f(3,n)? Extending the problem to multisets (or monomials) instead of sets may be fruitful since there is a proposed suggestion for an answer.