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 - Ellis\, D (Cambridge)
DTSTART:20110405T141500Z
DTEND:20110405T151500Z
UID:TALK30600@talks.cam.ac.uk
CONTACT:Mustapha Amrani
DESCRIPTION:A family of graphs F on a fixed set of n vertices is said to b
 e triangle-intersecting if for any two graphs G\,H 2 F\, G  H contains a t
 riangle. Simonovits and Sos conjectured that such a family has size at mos
 t 18 2(n2)\,and that equality holds only if F consists of all graphs conta
 ining some fixed triangle. Recently\, the author\, Yuval Filmus and Ehud F
 riedgut proved a strengthening of this conjecture\, namely that if F is an
  odd-cycleintersecting family of graphs\, then |F|  18 2(n2). Equality hol
 ds only if F consists of all graphs containing some fixed triangle. A stab
 ility 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 outlin
 e 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 qu
 estions. \n\nAll will be based on joint work with Yuval Filmus (University
  of Toronto) and Ehud Friedgut (Hebrew University of Jerusalem).\n
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR