Back to Search
Start Over
Short proof of two cases of Chv\'atal's conjecture
- Source :
- Discrete Mathematics 342 (2019) 2192-2194
- Publication Year :
- 2018
-
Abstract
- In 1974 Chv\'atal conjectured that no intersecting family $\mathcal{F}$ in a downset can be larger than the largest star. In the same year Kleitman and Magnanti proved the conjecture when $\mathcal{F}$ is contained in the union of two stars, and Sterboul when $\operatorname{rank}(\mathcal{F})\le 3$. We give short self-contained proofs of these two statements.<br />Comment: 3 pages, updated with additional references
- Subjects :
- Mathematics - Combinatorics
05E45, 52C10, 05D05
Subjects
Details
- Database :
- arXiv
- Journal :
- Discrete Mathematics 342 (2019) 2192-2194
- Publication Type :
- Report
- Accession number :
- edsarx.1804.03646
- Document Type :
- Working Paper
- Full Text :
- https://doi.org/10.1016/j.disc.2019.04.011