The  Weizmann  Institute  of  Science
                  Faculty of Mathematics and Computer Science
 
             Geometric Functional Analysis and Probability Seminar
 
                    Seminar Room, Room 261, Ziskind Building
                         on Thursday, February 10, 2011
                                    at 11:30
 
                              Note late start 
 
                                 Ehud Friedgut
                               Hebrew University
 
                                 will speak on
 
                    Triangle-intersecting families of graphs
 
Abstract:
How many graphs can you choose on a fixed set of $n$ vertices such that the
intersection of any two of them contains a triangle? S\'{o}s and Simonovits
conjectured in 1976 that the largest such families of graphs are obtained by
taking all graphs containing a fixed triangle, and that these are the only
extremal constructions. This question turned out to be relatively resilient to
the standard methods in extremal combinatorics, with partial progress being
made in 1986 after Chung-Graham-Frankl-Shearer introduced some novel entropy
arguments. Recently, with David Ellis and Yuval Filmus, we have been able to
prove the conjecture, using discrete Fourier analysis and spectral methods.  In
this talk I'll sketch the proof.
 
---------------------------------------------------------
Technion Math Net-2 (TECHMATH2)
Editor: Michael Cwikel   <techm@math.technion.ac.il> 
Announcement from: Gady Kozma   <gady.kozma@weizmann.ac.il>