2021/03/23 by Berger, Aaron, Zhao, Yufei
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2103.12671
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^\binomn2 - 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 Kt-intersecting families. We prove these conjectures for t ∈ \3,4\, showing that if \mathcal F1 and \mathcal F2 are families of graphs on n labeled vertices such that for any G1 ∈ \mathcal F1 and G2 ∈ \mathcal F2, G1 ∩ G2 contains a Kt, then | \mathcal F1 | | \mathcal F2 | ≤ 4^\binomn2 - \binomt2, with equality if and only if \mathcal F1 = \mathcal F2 consists of all graphs that contain some fixed Kt. We also establish a stability result. More generally, "G1 ∩ G2 contains a Kt" can be replaced by "G1 and G2 agree on a non-(t-1)-colorable graph."