Title: Triangle-intersecting Families of Graphs
Speaker: Yuval Filmus, Institute for Advanced Study
Date: Tuesday, February 4, 2014 2:00pm
Location: Hill Center, Room 525, Rutgers University, Busch Campus, Piscataway, NJ
In 1938, Erdos, Ko and Rado proved their seminal result on intersecting families of sets. They only published their result in 1961, and their paper gave birth to an entire area in extremal combinatorics. One of the questions in this are was asked in 1976 by Simonovits and Sós: How big can a collection of subgraphs of K_n be, if the intersection of any two of them contains a triangle? They conjectured that such a collection can contain at most 1/8 of the graphs. The first non-trivial bound for this question, obtained by Chung, Frankl, Graham and Shearer in 1986, was an upper bound of 1/4. We prove the conjecture of Simonovits and Sós, furthermore determining the optimal collections, and obtaining a stability result. The methods we use are spectral we use a bound due to Hoffman which is a special case of the Lovász theta function. Joint work with David Ellis (Queen Mary's University of London) and Ehud Friedgut (Weizmann institute).
See: http://math.rutgers.edu/seminars/allseminars.php?sem_name=Discrete%20Math