Simonovits and Sos asked:
Let 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 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 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 .
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!
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.
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 be the ground set (universe), and let . We could conjecture that if and for any two we have for some , then . In EKR, is the set of singleton subsets of . In Simonovits-Sos, and 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 that make the above true.
Are there bolder/more subtle generalizations?
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.
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.
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).
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.
(should have been a comment to Sasho)
Many thanks for your comments, Yuval
Thanks for the insightful comments from me too, Yuval! And congratulations on a great result!
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 *connected* graph . 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?