{"ID":23021114,"CreatedAt":"2026-09-17T04:55:43.771560302Z","UpdatedAt":"2026-09-17T04:55:43.771560302Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2609.19123","arxiv_id":"2609.19123","title":"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.","short_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_{\\varn...","url_abs":"https://arxiv.org/abs/2609.19123","url_pdf":"https://arxiv.org/pdf/2609.19123v1","authors":"[\"Fan Chang\",\"Hong Liu\",\"Miao Liu\"]","published":"2026-09-16T17:45:18Z","proceeding":"math.CO","tasks":"[\"math.CO\",\"math.FA\",\"math.PR\"]","methods":"[]","has_code":false}