Ellis–Filmus–Friedgut theorem for clique-intersecting graph families
Ellis–Filmus–Friedgut theorem for clique-intersecting graph families
Let and be positive integers with , and let be a family of graphs on the common labeled vertex set . The family is -intersecting if the intersection of every two graphs in contains a subgraph isomorphic to the complete graph .
Ellis–Filmus–Friedgut theorem. Every -intersecting family of graphs on has size at most
with equality for the family of all graphs containing a fixed clique on 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
Sign in to submit a solution.
No solutions have been posted yet.