Holroyd–Talbot conjecture on the EKR property of graphs

From papers

Let GG be a graph, let calI(r)(G)calI^{(r)}(G) denote the family of independent rr-subsets of V(G)V(G), and let calIv(r)(G)calI^{(r)}_v(G) denote the star centered at vV(G)v\in V(G). Write cmu(G)cmu(G) for the size of a smallest maximal independent set of GG. A graph is rr-EKR if there is a vertex vV(G)v\in V(G) such that every intersecting family calFcalI(r)(G)calF\subseteq calI^{(r)}(G) satisfies calFcalIv(r)(G)|calF|\leq |calI^{(r)}_v(G)|. Holroyd–Talbot conjecture. Every graph GG is rr-EKR whenever

1rμ(G)2.1\leq r\leq \frac{\mu(G)}{2}.

This conjecture extends the Erdős–Ko–Rado theorem from uniform set systems to independent sets in graphs. It asserts that the threshold for the EKR property is governed by the minimum size of a maximal independent set; its general status is not specified in the source.

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

Zaphenath Joseph, “An EKR Theorem for the Cartesian Product of Complete Graphs”, arXiv:2509.14291 (2025).

Additional references

9 papers in this index state this conjecture (2009–2025). The statement above is taken from the most recent of them; the others are arXiv:2501.16144, arXiv:2207.01661, arXiv:2106.09067, arXiv:2009.00732, arXiv:1610.08153, arXiv:1506.07741, arXiv:1001.0313, arXiv:0903.4203.

Solutions 0

No solutions have been posted yet.