Regular bipartite graphs and intersecting families

Andrey Kupavskii, Dmitriy Zakharov

Research output: Contribution to journalArticlepeer-review

26 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)180-189
Number of pages10
JournalJournal of Combinatorial Theory, Series A
Volume155
DOIs
StatePublished - Apr 2018
Externally publishedYes

Keywords

  • Diversity
  • Erdos–Ko–Rado theorem
  • Hilton–Milner theorem
  • Intersecting families
  • Regular bipartite graphs

Fingerprint

Dive into the research topics of 'Regular bipartite graphs and intersecting families'. Together they form a unique fingerprint.

Cite this