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!

This entry was posted in Combinatorics, Open problems and tagged , , , . Bookmark the permalink.

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

1. Gil Kalai says:

Let me add the extremal problems on set systems where the ground set is regarded as the set of edges of the complete graph (so you have extra structure) is a very interesting subject initiated by Simonovits and Sos. Look, for example at the formulations of the polynomial Hales Jewett problem http://gowers.wordpress.com/2009/11/14/the-first-unknown-case-of-polynomial-dhj/. Such problems are also related to the counterexample by Jeff Kahn and me to Borsuk’s problem.

2. Sasho Nikolov says:

Is there a result that generalizes extremal results like Erdos-Ko-Rado, the Siminovits-Sos conjecture (or EFF theorem now 🙂 ) and similar results. For example, let $U$ be the ground set (universe), and let $\mathcal{X} \subseteq {U \choose k}$. We could conjecture that if $\mathcal{F} \subseteq 2^U$ and for any two $F_1, F_2 \in \mathcal{F}$ we have $X \subseteq F_1 \cap F_2$ for some $X \in \mathcal{X}$, then $|\mathcal{F}| \leq 2^{|U| - k}$. In EKR, $\mathcal{X}$ is the set of singleton subsets of $U$. In Simonovits-Sos, $U = {[n] \choose 2}$ and $\mathcal{X}$ is the set of triangles. I noticed that the paper above establishes this theorem for all odd cycles.

Are there counter examples? In case there are, it might be interesting to look for ways to characterize $\mathcal{X}$ that make the above true.

Are there bolder/more subtle generalizations?

• Gil Kalai says:

Dear Shasho, this is a good question. I am not aware of very general conjecture in the form you propose, but several problems results can be described in this way.

• Yuval says:

Take a look at the classic “Some intersection theorems for ordered sets and graphs”. You would like to have the stronger condition that the optimal families are kernel families (e.g. all supersets of a given triangle).

They conjectured that this is the case in the following four settings:
(1) All cyclic translates of a some fixed set. They proved it for intervals; Griggs and Walker proved it for infinitely many values of n, “Anticlusters and intersecting families of subsets”.
(2) The Simonovits-Sos conjecture.
(3) Like (2), replacing “triangle” by a path of length 3; an unpublished counterexample was given by Christofides (David has it).
(4) Sets of integers whose intersection contains a 3-term arithmetic progression. As far as I know, widely open.

• Yuval says:

If you take unrestricted 2-intersecting families, then instead of getting 1/4 of the sets, you’ll get almost 1/2 of them (take all sets with at least n/2+1 elements). The more interesting question is identifying the “Ahlswede-Khachatrian spectrum”, which is the maximal mu_p measure for various p (your question corresponds to p=1/2).

3. Yuval says:

Another possibly related line of research is exemplified by “Extremal set systems with restricted k-wise intersections” by Fueredi and Sudakov. On the title page it reads “Communicated by Gil Kalai” so I’m sure Gil could tell us more about it.

• Yuval says:

(should have been a comment to Sasho)

• Gil Kalai says:

I was thinking if one direction to go is to look at families of graphs such that each pair of graphs in the family share a copy of some size $k$ *connected* graph $H$. The counterexample to Simonovits-Sos with “triangle” replaced by “length-3 path” refutes that. Oh well..
A concrete “puzzle” is whether kernel sets based on a triangle are also optimal for cycle-intersecting families. Stated differently, is there some $n$ and a family of more than $2^{n-3}$ graphs on $n$ vertices such that the intersection of any two contains a cycle?