School of Mathematical Sciences

Triangle-intersecting families of graphs menu

Triangle-intersecting families of graphs

David Ellis
Fri, 28/10/2011 - 17:30
Seminar series: 

A family of graphs F on a fixed set of n vertices is said to be triangle-intersecting if for any two graphs G,H in F, the intersection of G and H contains a triangle. Simonovits and Sos conjectured that such a family has size at most (1/8)2{n choose 2}, and that equality holds only if F consists of all graphs containing some fixed triangle. Recently, the author, Yuval Filmus and Ehud Friedgut proved this conjecture, using discrete Fourier analysis, combined with an analysis of the properties of random cuts in graphs. We will give a sketch of our proof, and then discuss some related open questions.

All will be based on joint work with Yuval Filmus (University of Toronto) and Ehud Friedgut (Hebrew University of Jerusalem).