[Combprob] combinatorics and probability seminar this semester

[Daniel Spielman]

This semester, the combinatorics and probability seminar will meet
on Thursdays at 4:00PM.

The first talk will be on January 29:

Yuval Filmus (IAS): Triangle-intersecting families of graphs

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


  --Dan
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.yale.edu/pipermail/combprob/attachments/20150116/1e17a741/attachment.html