SPEAKER: Yuval Filmus, Department of
Computer Science, University of Toronto
TITLE: Triangle-Intersecting Families of Graphs
A family of graphs (sharing the same finite vertex set)
is *triangle-intersecting* if the intersection of any two graphs in the family
contains a triangle. Simonovits and Sós conjectured in 1976 that such a family
can contain at most 1/8 of the graphs; this bound is achieved by taking a
"triangle-junta" (all graphs containing a fixed triangle).
Up to the current work, the best known upper bound on the
size of a triangle-intersecting family was 1/4 (Chung, Graham,
Frankl & Shearer 1981). We prove the conjecture, showing moreover that the only
families achieving the bound are triangle-juntas.
The result follows a line of work initiated in 2008 by
Friedgut (multiply-intersecting families of sets) and continued by
Ellis, Friedgut and Pilpel (intersecting families of permutations). The proof uses rudimentary discrete Fourier analysis, and
some "entry-level" graph theory; the talk will focus on the former. No prior
knowledge of either subject is required.
Joint work with David Ellis (Cambridge) and Ehud Friedgut