2014/08/11 by József Balogh, Shagnik Das, Balogh, József +7 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #math.CO
paper · pdf · doi:10.48550/arxiv.1408.2559
19 pages. Update 1: better citation of the Gauy--Hàn--Oliveira result. Update 2: corrected statement of the unpublished Hamm--Kahn result, and slightly modified notation in Theorem 1.6 Update 3: new title, updated citations, and some minor corrections
openalex publication_date 2014/08/11 · arxiv created 2015/01/09 · arxiv updated 2015/01/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 Erdő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.