OpenAlex ·

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

David Ellis, Yuval Filmus and Ehud Friedgut

Published
Source
OpenAlex
Published in
arXiv (Cornell University)
DOI
10.48550/arxiv.2609.28404
Original
Read it at the publisher
Topics
CombinatoricsNumber Theory

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.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

Read it on ReadSearch

Each opens after you create an account, and brings you back to this paper.

Already a reader? Sign in

All new papers in Combinatorics

Get the few papers worth your time in Combinatorics every morning.

ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.

Papers belong to their authors and publishers; every page here links to the original. All research topics