TY - JOUR
T1 - Regular bipartite graphs and intersecting families
AU - Kupavskii, Andrey
AU - Zakharov, Dmitriy
N1 - Publisher Copyright:
© 2017 Elsevier Inc.
PY - 2018/4
Y1 - 2018/4
N2 - In this paper we present a simple unifying approach to prove several statements about intersecting and cross-intersecting families, including the Erdős–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.
AB - In this paper we present a simple unifying approach to prove several statements about intersecting and cross-intersecting families, including the Erdős–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.
KW - Diversity
KW - Erdos–Ko–Rado theorem
KW - Hilton–Milner theorem
KW - Intersecting families
KW - Regular bipartite graphs
UR - http://www.scopus.com/inward/record.url?scp=85034039020&partnerID=8YFLogxK
U2 - 10.1016/j.jcta.2017.11.006
DO - 10.1016/j.jcta.2017.11.006
M3 - Article
AN - SCOPUS:85034039020
SN - 0097-3165
VL - 155
SP - 180
EP - 189
JO - Journal of Combinatorial Theory, Series A
JF - Journal of Combinatorial Theory, Series A
ER -