Hebrew University
Math Colloquium
Ehud Friedgut, Huji
Triangle-intersecting families of graphs
Thursday , December 16th,  2010, 4:00 pm
Mathematics Building Lecture Hall 2
Givat-Ram Campus
Light refreshments will be served in the faculty lounge at 3:30.
You are cordially invited
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?
Sos 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: Lital Kenan   <litalk@math.huji.ac.il>