Event time:
Thursday, January 29, 2015 - 11:00am to 12:00pm
Location:
215 LOM
Speaker:
Y.Filmus
Speaker affiliation:
IAS
Event description:
Simonovits and Sós asked the following question in 1976, prompted by the classical Erdős–Ko–Rado theorem:
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. We prove their conjecture, furthermore identifying the optimal collections (triangle-juntas).
We also prove a stability result, stating that a collection of measure $1/8-\epsilon$ is $O(\epsilon)$-close to an optimal collection.
Our proof technique is spectral and relies on the Lovász theta function.
Joint work with David Ellis (Queen Mary’s University of London) and Ehud Friedgut (Weizmann institute).