Let cal F be a family of sets. It is subset-closed if every subset of every member of cal F also belongs to cal F. Recall that cal F is sf EKR when some star cal F_x has size at least that of every intersecting subfamily cal H⊆cal F. Chvátal's conjecture. Every subset-closed family of sets is sf EKR. This conjecture asks for an Erdős–Ko–Rado-type extremal theorem for arbitrary subset-closed families. Its status is not specified in the source.

Chvátal's conjecture on subset-closed families

About 15 years old · traced to 2011

Let ${\cal F}$ be a family of sets. It is subset-closed if every subset of every member of ${\cal F}$ also belongs to ${\cal F}$ . Recall that ${\cal F}$ is ${\sf EKR}$ when some star ${\cal F}_x$ has size at least that of every intersecting subfamily ${\cal H}\subseteq{\cal F}$ .

Chvátal's conjecture. Every subset-closed family of sets is ${\sf EKR}$ .

This conjecture asks for an Erdős–Ko–Rado-type extremal theorem for arbitrary subset-closed families. Its status is not specified in the source.

References

Primary source

Neal Bushaw, James Danielsson and Glenn Hurlbert, “Erdős-Ko-Rado Theorems for Paths in Graphs”, arXiv:2504.05406 (2026).

Additional references

9 papers in this index state this conjecture (2011–2025). The statement above is taken from the most recent of them; the others are arXiv:2402.03150, arXiv:2201.03865, arXiv:1912.11641, arXiv:1809.01572, arXiv:1710.02518, arXiv:1511.08245, arXiv:1106.6144, arXiv:1103.3858.

erdos-ko-rado extremal-set-theory

Posted 1 month ago · edited 4 weeks ago

Progress summary

Refreshed 4 weeks ago

Open

The conjecture remains open: several restricted cases and small computational checks are known, but no proof or counterexample has been found.

Chvátal posed the conjecture in 1974: every subset-closed family has an intersecting subfamily no larger than one of its stars. The unrestricted statement remains unresolved.

Known results

Sterboul proved the conjecture for downsets of rank at most $3$ ; later short proofs are available.
Kleitman and Magnanti proved it when the intersecting family lies in the union of two stars.
Chvátal's result covers left-compressed subset-closed families; further structural special cases are known.
Eifler, Gleixner, and Pulaj verified it computationally for all subset-closed families of $2^{[7]}$ .

April 2025 literature status

The latest catalogued paper still treats Chvátal's conjecture as unresolved and reports no complete proof or counterexample. Related uniform-family theorems and variants do not settle the unrestricted conjecture.

Current status (as of September 2026): The conjecture is open; several special cases and finite computations are settled, but the general statement has no verified proof or counterexample.

Sources

No solutions have been posted yet.