Regular bipartite graphs and intersecting families

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:155

Article

Kupavskii, Andrey^1,2 

[1] Moscow Inst Phys & Technol, Dolgoprudnyi, Moskovskaya Obl, Russia

[2] Ecole Polytech Fed Lausanne, Lausanne, Switzerland

关键词: Intersecting families;    Erdos-Ko-Rado theorem;    Hilton-Milner theorem;    Diversity;    Regular bipartite graphs;   

DOI  :  10.1016/j.jcta.2017.11.006

来源: Elsevier

【 摘 要 】

In this paper we present a simple unifying approach to prove several statements about intersecting and cross-intersecting families, including the Erdos-Ko-Rado theorem, the Hilton-Milner theorem, a theorem due to Frankl concerning the size of intersecting families with bounded maximal degree, and versions of results on the sum of sizes of non-empty cross intersecting families due to Frankl and Tokushige. Several new stronger results are also obtained. Our approach is based on the use of regular bipartite graphs. These graphs are quite often used in Extremal Set Theory problems, however, the approach we develop proves to be particularly fruitful. (C) 2017 Elsevier Inc. All rights reserved.

【 授权许可】

Free