Back to Search Start Over

Short proof of two cases of Chv\'atal's conjecture

Authors :
Olarte, Jorge
Santos, Francisco
Spreer, Jonathan
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

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