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).