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

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: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.