skip to content

Triangle-intersecting families of graphs

Presented by: 
D Ellis [Cambridge]
Tuesday 5th April 2011 - 15:15 to 16:15
INI Seminar Room 1
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 2 F, G \ H contains a triangle. Simonovits and S´os conjectured that such a family has size at most 18 2(n2),and that equality holds only if F consists of all graphs containing some fixed triangle. Recently, the author, Yuval Filmus and Ehud Friedgut proved a strengthening of this conjecture, namely that if F is an odd-cycleintersecting family of graphs, then |F| · 18 2(n2). Equality holds only if F consists of all graphs containing some fixed triangle. A stability result also holds: an odd-cycle-intersecting family with size close to the maximum must be close to a family of the above form. We will outline proofs of these results, which use Fourier analysis, together with an analysis of the properties of random cuts in graphs, and some results in the theory of Boolean functions. We will 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).
The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons