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

About 1 year old · traced to

Let tt and nn be positive integers with t≥2t\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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.