Chvátal's Erdős–Chvátal simplex conjecture

About 20 years old · traced to

Let k>r≥1k>r\geq 1 and n≥r+1rkn\geq \frac{r+1}{r}k. A family F⊆([n]k)\mathcal{F}\subseteq\binom{[n]}{k} is without an rr-simplex if it contains no rr-simplex.

Erdős–Chvátal simplex conjecture. Every family F⊆([n]k)\mathcal{F}\subseteq\binom{[n]}{k} without an rr-simplex contains at most

(n−1k−1)\binom{n-1}{k-1}

sets.

This conjecture asserts that the largest uniform families without an rr-simplex are typically trivial, with the bound attained by the family of all kk-sets containing a fixed element. Its general status is not specified in the source.

References

Primary source

Stijn Cambie and Nika Salia, “Set systems without a simplex, Helly hypergraphs and union-efficient families”, arXiv:2210.16211 (2022).

Additional references

2 papers in this index state this conjecture (2006–2022). The statement above is taken from the most recent of them; the others are arXiv:math/0605171.

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.