Skip to content
DraconiticResearch
Search Sources API
203,203 studies31 sourcesUpdated 31 min ago
PreprintarXiv licencearXiv

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

  • Fan Chang
  • Hong Liu
  • Miao Liu
Open at sourcePDFDOICite

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→{0,1}. Writing g*(x)=1−g(1−x), we show that ∑∅≠ S⊆[n]ĝ(S)2maxi∈ SInfi[f]≤2Cov(f,g)Cov(f,g*)/(Cov(f,g)+Cov(f,g*)). When g is antipodal, that is, g=g*, this yields Cov(f,g)≥1/4mini∈[n]Infi[f], the correlation formulation of Chvátal's conjecture due to Friedgut, Kahn, Kalai and Keller.

Related

  1. A Sharp Fisher-Information Inequality for Boolean Pairs: Proof of the Amari--Kobayashi Conjecture
    Jun Chen, Shun Watanabe, Lei Yu
    arXivPreprintarXiv licenceFull textGeneral mathematicsarXiv
  2. Chvátal's conjecture: a proof from The Book
    David Ellis, Yuval Filmus, Ehud Friedgut
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Digesting the proof of the sharp thin-shell inequality
    Yuansi Chen, Bo’az Klartag
    arXiv (Cornell University)PreprintLicence not statedFull text13 citedGeneral mathematicsOpenAlex
  4. A proof of Alexander’s Conjecture on an Inequality of Cassels
    Myriam Ounaïes
    Complex Analysis and Operator TheoryPeer-reviewedLicence not statedFull textGeometry & topologyHAL
  5. Royen's proof of the Gaussian correlation inequality as a supersymmetric dimensional reduction
    Yichao Huang
    arXivPreprintCC BY-NC-ND 4.0Full textMathematical physicsProbabilityarXiv

Cite

BibTeXRIS
BibTeX
@misc{chang2026proof,
  title = {{A proof of Chvátal's conjecture via a sharp correlation inequality}},
  author = {Fan Chang and Hong Liu and Miao Liu},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.19123},
  eprint = {2609.19123},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.19123},
}
RIS
TY  - UNPB
TI  - A proof of Chvátal's conjecture via a sharp correlation inequality
AU  - Fan Chang
AU  - Hong Liu
AU  - Miao Liu
PY  - 2026
DA  - 2026/09/16
PB  - arXiv
DO  - 10.48550/arxiv.2609.19123
UR  - https://arxiv.org/abs/2609.19123
AB  - 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→{0,1}. Writing g^*(x)=1−g(1−x), we show that ∑_∅≠ S⊆[n]ĝ(S)^2max_i∈ SInf_i[f]≤2Cov(f,g)Cov(f,g^*)/(Cov(f,g)+Cov(f,g^*)). When g is antipodal, that is, g=g^*, this yields Cov(f,g)≥1/4min_i∈[n]Inf_i[f], the correlation formulation of Chvátal's conjecture due to Friedgut, Kahn, Kalai and Keller.
ER  -