Ellis–Filmus–Friedgut theorem for clique-intersecting graph families

From papers

Let tt and nn be positive integers with t2t\geq 2, and let G\mathcal{G} be a family of graphs on the common labeled vertex set [n]={1,,n}[n]=\{1,\ldots,n\}. The family is KtK_t-intersecting if the intersection of every two graphs in G\mathcal{G} contains a subgraph isomorphic to the complete graph KtK_t.

Ellis–Filmus–Friedgut theorem. Every KtK_t-intersecting family of graphs on [n][n] has size at most

2(n2)(t2),2^{\binom{n}{2}-\binom{t}{2}},

with equality for the family of all graphs containing a fixed clique on tt vertices.

This resolves the corresponding extremal problem for complete graphs and, in particular, proves the conjectured value in the triangle case. The statement is attributed in the source to Ellis, Filmus, and Friedgut.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Igal Sason, “On H-Intersecting Graph Families and Counting of Homomorphisms”, arXiv:2501.02894 (2025).

Solutions 0

No solutions have been posted yet.