Intersecting families of discrete structures are typically trivial

DOI10.1016/J.JCTA.2015.01.003MaRDI QIDQ2258906zbMATH OpenOpenAlexWikidataFDO

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

Publication date 27 February 2015

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1408.2559

zbMATH Keywords

Bollobás set-pairsErdős-Ko-Rado theoremextremal combinatoricshypergraphsintersecting familiesKneser graphpermutationsrandom hypergraphsvector spaces

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Hypergraphs (05C65) Random graphs (graph-theoretic aspects) (05C80)

Abstract: The study of intersecting structures is central to extremal combinatorics. A family of permutations $mathcalFsubset{S}_n$ is emph{$t$-intersecting} if any two permutations in $mathcalF$ agree on some $t$ indices, and is emph{trivial} if all permutations in $mathcalF$ agree on the same $t$ indices. A $k$-uniform hypergraph is emph{$t$-intersecting} if any two of its edges have $t$ vertices in common, and emph{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 ErdH{o}s--Ko--Rado theorem shows that the largest $t$-intersecting $k$-uniform hypergraphs are also trivial when $n$ is large. We determine the emph{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'as 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.

Recommendations

• Structure and supersaturation for intersecting families
• The structure of large non-trivial \(t\)-intersecting families of finite sets
• Intersecting families of sets and permutations: a survey
• Counting intersecting and pairs of cross-intersecting families
• The structure of large intersecting families

Cites work

• A Hilton-Milner theorem for vector spaces
• An extremal problem for two families of sets
• Counting sum-free sets in abelian groups
• Erdős-Ko-Rado for random hypergraphs: asymptotics and stability
• Erdős-Ko-Rado in random hypergraphs
• Explicit construction of linear sized tolerant networks
• Geometrical solution of an intersection problem for two hypergraphs
• scientific article; zbMATH DE number 3557819 (Why is no real title available?)
• scientific article; zbMATH DE number 3561367 (Why is no real title available?)
• scientific article; zbMATH DE number 3621717 (Why is no real title available?)
• scientific article; zbMATH DE number 1246230 (Why is no real title available?)
• Hypergraph containers
• Independent sets in hypergraphs
• Intersecting families of permutations
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Intersection theorems for systems of finite vector spaces
• On Dedekind's Problem: The Number of Monotone Boolean Functions
• On Erdős-Ko-Rado for random hypergraphs. I
• On Erdős-Ko-Rado for random hypergraphs. II
• On generalized graphs
• On the number of maximal intersecting \(k\)-uniform families and further applications of Tuza's set pair method
• On the Shannon capacity of a graph
• Setwise intersecting families of permutations
• SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Stability for t-intersecting families of permutations
• The complete nontrivial-intersection theorem for systems of finite sets
• The exact bound in the Erdős-Ko-Rado theorem
• The number of Sidon sets and the maximum size of Sidon sets contained in a sparse random set of integers

Cited in

(28)

• On the structure of large sum-free sets of integers
• On hypergraphs without loose cycles
• Colourings without monochromatic disjoint pairs
• The structure of large non-trivial \(t\)-intersecting families of finite sets
• Inverse problems of the Erdős-Ko-Rado type theorems for families of vector spaces and permutations
• Clique number of Xor products of Kneser graphs
• On the number of maximal intersecting \(k\)-uniform families and further applications of Tuza's set pair method
• Structure and supersaturation for intersecting families
• Removal and stability for Erdős-Ko-Rado
• On ``stability in the Erdős-Ko-Rado theorem
• Applications of graph containers in the Boolean lattice
• A simple removal lemma for large nearly-intersecting families
• Transference for the Erdős-Ko-Rado theorem
• The typical structure of maximal triangle-free graphs
• Intersecting Families are Essentially Contained in Juntas
• Counting intersecting and pairs of cross-intersecting families
• Intersecting families of sets and permutations: a survey
• On Erdős-Ko-Rado for random hypergraphs. I
• On the chromatic index of random uniform hypergraphs
• Erdős-Ko-Rado for random hypergraphs: asymptotics and stability
• Sharp threshold for the Erdős–Ko–Rado theorem
• Intersecting families of sets are typically trivial
• On the intersecting family process
• Intersecting families of polynomials over finite fields
• On the number of \(\mathcal{H}\)-free hypergraphs
• Robustness of Erdős-Ko-Rado theorems on permutations and perfect matchings
• The number of colorings of the middle layers of the Hamming cube
• On the measure of intersecting families, uniqueness and stability

This page was built for publication: Intersecting families of discrete structures are typically trivial

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2258906)