# A proof of Chvátal's conjecture via a sharp correlation inequality

Preprint · Fan Chang, Hong Liu, Miao Liu

- Archive id: arxiv:2609.19123
- Published: 2026-09-16
- arXiv: https://arxiv.org/abs/2609.19123
- Source URL: https://arxiv.org/abs/2609.19123
- PDF: https://arxiv.org/pdf/2609.19123
- Provenance: arxiv

## Abstract

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\]$, the correlation formulation of Chvátal's conjecture due to Friedgut, Kahn, Kalai and Keller.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.