Intersecting families of discrete structures are typically trivial

József Balogh, Shagnik Das, Michelle Delcourt, Hong Liu, Maryam Sharifzadeh

Research output: Contribution to journalArticle

Abstract

The study of intersecting structures is central to extremal combinatorics. A family of permutations F⊂Sn is t-intersecting if any two permutations in F agree on some t indices, and is trivial if all permutations in F agree on the same t indices. A k-uniform hypergraph is t-intersecting if any two of its edges have t vertices in common, and trivial if all its edges share the same t vertices.The fundamental problem is to determine how large an intersecting family can be. Ellis, Friedgut and Pilpel proved that for n sufficiently large with respect to t, the largest t-intersecting families in Sn are the trivial ones. The classic Erdo's-Ko-Rado theorem shows that the largest t-intersecting k-uniform hypergraphs are also trivial when n is large. We determine the typical structure of t-intersecting families, extending these results to show that almost all intersecting families are trivial. We also obtain sparse analogues of these extremal results, showing that they hold in random settings.Our proofs use the Bollobás set-pairs inequality to bound the number of maximal intersecting families, which can then be combined with known stability theorems. We also obtain similar results for vector spaces.

Original languageEnglish (US)
Pages (from-to)224-245
Number of pages22
JournalJournal of Combinatorial Theory. Series A
Volume132
DOIs
StatePublished - May 1 2015

Keywords

  • Bollobás set-pairs
  • Erdo's-Ko-Rado
  • Extremal combinatorics
  • Hypergraphs
  • Intersecting families
  • Kneser graph
  • Permutations
  • Random hypergraphs
  • Vector spaces

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Intersecting families of discrete structures are typically trivial'. Together they form a unique fingerprint.

  • Cite this