Skip to content
DraconiticResearch
Search Sources API
190,839 studies31 sourcesUpdated 26 min ago
PreprintarXiv licencearXiv

Chvátal's conjecture: a proof from The Book

  • David Ellis
  • Yuval Filmus
  • Ehud Friedgut
Open at sourcePDFDOICite

Abstract

Chvátal conjectured that every downset has a maximum-size intersecting family which is a star, that is, consists of all members of the downset containing a fixed element. Recently, Chang, Liu and Liu gave a proof of this conjecture, which follows as a corollary of more general results such as Kleitman's conjecture and a version of Kahn's conjecture (which they also prove). We give a short, direct (spectral) proof of Chvátal's conjecture, and a proof of Kleitman's conjecture along the same lines. We also prove a strengthening of Chvátal's conjecture concerning the projection packing number. Finally, we propose two spectral Chvátal conjectures which are motivated by extensive numerical experiments.

Related

  1. A proof of Chvátal's conjecture via a sharp correlation inequality
    Fan Chang, Hong Liu, Miao Liu
    arXivPreprintarXiv licenceFull textAnalysis & PDEsCombinatorics & discrete mathematicsarXiv
  2. The Erdős--Chvátal Simplex Conjecture
    Jing Huang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. A proof of the Stanley-Stembridge conjecture
    Tatsuyuki Hikita
    Journal of the American Mathematical SocietyPeer-reviewedLicence not statedFull text6 citedCombinatorics & discrete 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. A Proof of Ebenfelt's weak SOS Conjecture
    Zhiwei Wang, Chenlong Yue, Xiangyu Zhou
    arXivPreprintarXiv licenceFull textAnalysis & PDEsarXiv

Cite

BibTeXRIS
BibTeX
@misc{ellis2026chvátals,
  title = {{Chvátal's conjecture: a proof from The Book}},
  author = {David Ellis and Yuval Filmus and Ehud Friedgut},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2609.28404},
  eprint = {2609.28404},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.28404},
}
RIS
TY  - UNPB
TI  - Chvátal's conjecture: a proof from The Book
AU  - David Ellis
AU  - Yuval Filmus
AU  - Ehud Friedgut
PY  - 2026
DA  - 2026/10/22
PB  - arXiv
DO  - 10.48550/arxiv.2609.28404
UR  - https://arxiv.org/abs/2609.28404
AB  - Chvátal conjectured that every downset has a maximum-size intersecting family which is a star, that is, consists of all members of the downset containing a fixed element. Recently, Chang, Liu and Liu gave a proof of this conjecture, which follows as a corollary of more general results such as Kleitman's conjecture and a version of Kahn's conjecture (which they also prove). We give a short, direct (spectral) proof of Chvátal's conjecture, and a proof of Kleitman's conjecture along the same lines. We also prove a strengthening of Chvátal's conjecture concerning the projection packing number. Finally, we propose two spectral Chvátal conjectures which are motivated by extensive numerical experiments.
ER  -