Triangle-Intersecting Families of Graphs

Add to your list(s) Download to your calendar using vCal

• David Ellis (St John's College, Cambridge)
• Thursday 10 February 2011, 15:00-16:00
• MR12.

If you have a question about this talk, please contact Andrew Thomason.

A family of graphs F on a fixed set of n vertices is aid to be `triangle-intersecting’ if for any two graphs G and H in F, the intersection of G and H contains a triangle. Simonovits and S\’{o}s conjectured that such a family has size at most $\frac{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 a strengthening of this conjecture, namely that if F is an odd-cycle-intersecting family of graphs, then $|F| \leq tfrac{1}{8} 2^{{n \choose 2}}$. 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 from 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).

This talk is part of the Combinatorics Seminar series.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• Combinatorics Seminar
• DPMMS Lists
• DPMMS Pure Maths Seminar
• DPMMS info aggregator
• DPMMS lists
• Hanchen DaDaDash
• Interested Talks
• MR12
• School of Physical Sciences
• bld31

Note that ex-directory lists are not shown.