$K_4$-intersecting families of graphs

Abstract

Ellis, Filmus, and Friedgut proved an old conjecture of Simonovits and Sós showing that the maximum size of a triangle-intersecting family of graphs on $n$ vertices has size at most $2^{\left(\genfrac{}{}{0ex}{}{n}{2}\right)-3}$, with equality for the family of graphs containing some fixed triangle. They conjectured that their results extend to cross-intersecting families, as well to $K_t$-intersecting families. We prove these conjectures for $t\in \{3,4\}$, showing that if ${\mathcal{F}}_1$ and ${\mathcal{F}}_2$ are families of graphs on $n$ labeled vertices such that for any $G_1\in {\mathcal{F}}_1$ and $G_2\in {\mathcal{F}}_2$, $G_1\cap G_2$ contains a $K_t$, then $|{\mathcal{F}}_1||{\mathcal{F}}_2|\le 4^{\left(\genfrac{}{}{0ex}{}{n}{2}\right)-\left(\genfrac{}{}{0ex}{}{t}{2}\right)}$, with equality if and only if ${\mathcal{F}}_1={\mathcal{F}}_2$ consists of all graphs that contain some fixed $K_t$. We also establish a stability result. More generally, "$G_1\cap G_2$ contains a $K_t$" can be replaced by "$G_1$ and $G_2$ agree on a non-$(t-1)$-colorable graph."

16 pages, 3 tables