BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Triangle-Intersecting Families of Graphs - David Ellis (St John's 
 College\, Cambridge)
DTSTART:20110210T150000Z
DTEND:20110210T160000Z
UID:TALK29676@talks.cam.ac.uk
CONTACT:Andrew Thomason
DESCRIPTION: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 intersec
 tion of G and H contains a triangle. Simonovits and S\\'{o}s conjectured t
 hat 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 pro
 ved 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 \\choos
 e 2}}$. Equality holds only if $F$ consists of all graphs containing some 
 fixed triangle. A stability result also holds: an odd-cycle-intersecting f
 amily with size close to the maximum must be close to a family of the abov
 e form. We will outline proofs of these results\, which use Fourier analys
 is\, together with an analysis of the properties of random cuts in graphs\
 , and some results from the theory of Boolean functions. We will then disc
 uss some related open questions.\n\nAll will be based on joint work with Y
 uval Filmus (University of Toronto) and Ehud Friedgut (Hebrew University o
 f Jerusalem).\n
LOCATION:MR12
END:VEVENT
END:VCALENDAR