Name
Abstract | ||
|---|---|---|
The study of intersecting structures is central to extremal combinatorics. A family of permutations F 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 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. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1016/j.jcta.2015.01.003 | Journal of Combinatorial Theory Series A |
Keywords | Field | DocType |
extremal combinatorics,kneser graph,vector spaces,hypergraphs,permutations | Discrete mathematics,Combinatorics,Vector space,Constraint graph,Permutation,Hypergraph,T-vertices,Mathematical proof,Extremal combinatorics,Kneser graph,Mathematics | Journal |
Volume | Issue | ISSN |
132 | C | 0097-3165 |
Citations | PageRank | References |
9 | 0.72 | 13 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| József Balogh | 1 | 862 | 89.91 |
| Shagnik Das | 2 | 32 | 6.57 |
| Michelle Delcourt | 3 | 13 | 4.58 |
| Hong Liu | 4 | 39 | 8.54 |
| Maryam Sharifzadeh | 5 | 11 | 3.83 |