Intersecting families of discrete structures are typically trivial

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:132

Article

Balogh, Jozsef^1,2  Das, Shagnik³  Delcourt, Michelle¹  Liu, Hong¹  Sharifzadeh, Maryam¹ 

[1] Univ Illinois, Dept Math, Urbana, IL 61801 USA

[2] Univ Szeged, Bolyai Inst, H-6720 Szeged, Hungary

[3] ETH, Dept Math, CH-8092 Zurich, Switzerland

关键词: Extremal combinatorics;    Intersecting families;    Erdos-Ko-Rado;    Permutations;    Hypergraphs;    Vector spaces;    Bollobas set-pairs;    Kneser graph;    Random hypergraphs;   

DOI  :  10.1016/j.jcta.2015.01.003

来源: Elsevier

【 摘 要 】

The study of intersecting structures is central to extremal combinatorics. A family of permutations F subset of S-n 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 S-n are the trivial ones. The classic Erdos-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 Bollobas set-pairs inequality to bound the number of maximal intersecting families, which can then

【 授权许可】

Free