Holroyd–Talbot conjecture on the EKR property of graphs

About 17 years old · traced to

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 v∈V(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 v∈V(G)v\in V(G) such that every intersecting family calF⊆calI(r)(G)calF\subseteq calI^{(r)}(G) satisfies ∣calF∣≤∣calIv(r)(G)∣|calF|\leq |calI^{(r)}_v(G)|. Holroyd–Talbot conjecture. Every graph GG is rr-EKR whenever

1≤r≤μ(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.

References

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.

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.