A proof of Chvátal's conjecture via a sharp correlation inequality
We prove Chvátal's conjecture, posed in 1972: every hereditary family of subsets of a finite set has a largest intersecting subfamily that is a star. More generally, we prove a sharp correlation inequality for increasing Boolean functions $f,g:\{0,1\}^n\to\{0,1\}$. Writing $g^*(x)=1-g(1-x)$, we show that $$ \sum_{\varnothing\ne S\subseteq[n]}\hat{g}(S)^2\max_{i\in S}\mathrm{Inf}_i[f]\le\frac{2\mathrm{Cov}(f,g)\mathrm{Cov}(f,g^*)}{\mathrm{Cov}(f,g)+\mathrm{Cov}(f,g^*)}. $$ When $g$ is antipodal, that is, $g=g^*$, this yields $\mathrm{Cov}(f,g)\ge\frac{1}{4}\min_{i\in[n]}\mathrm{Inf}_i[f]$,…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.19123
curl -X POST /api/v1/records/arxiv/2609.19123/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.19123/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'