For every finite set X and every hereditary family F⊆ 2^X—that is, A∈F and B⊆ A imply B∈F—every intersecting subfamily A⊆F satisfies |A|≤ max_x∈ Xbigl|A∈F:x∈ Abigr|, where intersecting means that A cap B≠varnothing for all A,B∈A. Equivalently, F has a largest intersecting subfamily that is a star.

Chvátal’s conjecture

For every finite set $X$ and every hereditary family $\mathcal{F}\subseteq 2^X$ —that is, $A\in\mathcal{F}$ and $B\subseteq A$ imply $B\in\mathcal{F}$ —every intersecting subfamily $\mathcal{A}\subseteq\mathcal{F}$ satisfies

|\mathcal{A}|\leq \max_{x\in X}\bigl|\{A\in\mathcal{F}:x\in A\}\bigr|,

where intersecting means that $A\cap B\neq\varnothing$ for all $A,B\in\mathcal{A}$ . Equivalently, $\mathcal{F}$ has a largest intersecting subfamily that is a star.

Equivalent formulations 1Other wordings

Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.

Correlation formulation of Chvátal's conjecture
For every increasing Boolean function $f:\{0,1\}^n\to\{0,1\}$ and every antipodal increasing Boolean function $g:\{0,1\}^n\to\{0,1\}$ , meaning $g=g^*$ where $g^*(x)=1-g(1-x)$ , one has, with respect to the uniform measure on $\{0,1\}^n$ ,
$\operatorname{Cov}(f,g)\geq \frac14\min_{i\in[n]}\operatorname{Inf}_i[f].$
source: Chang, Fan, Liu, Hong, Liu, Miao, “A proof of Chvátal's conjecture via a sharp correlation inequality”

References

Primary source

arXiv

Additional references

A proof of Chvátal's conjecture via a sharp correlation inequality — arXiv — Fan Chang, Hong Liu, Miao Liu

boolean-analysis extremal-combinatorics

Posted 2 weeks ago · edited 2 weeks ago

Progress summary

Refreshed 2 weeks ago

Claimed solved

A September 2026 preprint claims to prove Chvátal’s conjecture, but the result has not yet been independently checked.

Chvátal’s 1974 conjecture asks whether every finite hereditary family has a largest intersecting subfamily formed by fixing one element. It has equivalent formulations involving correlation inequalities for increasing Boolean functions.

Known results

Sterboul (1974): the conjecture holds when all family members have size at most $3$ .
Schönheim (1975), Stein (1983), and Miklós (1984): several structural special cases.
Czabarka, Hurlbert, and Kamat (2017), and Olarte, Santos, and Spreer (2018): reproved the size- $3$ case.
Machine-assisted work (2018): verified all downsets with $|U(\mathcal{D})|\le 7$ ; the case $|U(\mathcal{D})|=8$ was not established.

September 2026 claimed proof

Fan Chang, Hong Liu, and Miao Liu claim that a sharp correlation inequality for increasing Boolean functions yields the full hereditary-family statement, which would settle the conjecture. The claim is an unrefereed same-day preprint and remains unverified; earlier 2026 work had explicitly left the required off-diagonal inequality open.

Current status (as of September 2026): A preprint claims a complete proof, but the conjecture remains unsettled pending independent verification.

Sources

No solutions have been posted yet.

Correlation formulation of Chvátal's conjecture

Primary source

Additional references

Progress summary