Transference for the Erdős-Ko-Rado theorem

DOI10.1017/FMS.2015.21zbMATH Open1323.05128arXiv1609.01001OpenAlexW2197142428MaRDI QIDQ3449986FDOQ3449986

Bhargav P. Narayanan, József Balogh, Béla Bollobás

Publication date: 2 November 2015

Published in: Forum of Mathematics, Sigma (Search for Journal in Brave)

Abstract: For natural numbers $n,rinmathbbN$ with $nger$, the Kneser graph $K(n,r)$ is the graph on the family of $r$-element subsets of $1,dots,n$ in which two sets are adjacent if and only if they are disjoint. Delete the edges of $K(n,r)$ with some probability, independently of each other: is the independence number of this random graph equal to the independence number of the Kneser graph itself? We answer this question affirmatively as long as $r/n$ is bounded away from $1/2$, even when the probability of retaining an edge of the Kneser graph is quite small. This gives us a random analogue of the ErdH{o}s-Ko-Rado theorem since an independent set in the Kneser graph is the same as a uniform intersecting family. To prove our main result, we give some new estimates for the number of disjoint pairs in a family in terms of its distance from an intersecting family, these might be of independent interest.

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

Recommendations

• On the stability of the Erdős-Ko-Rado theorem
• On the stability of some Erdős-Ko-Rado type results
• Sharp threshold for the Erdős–Ko–Rado theorem
• A simple removal lemma for large nearly-intersecting families
• On ``stability in the Erdős-Ko-Rado theorem

zbMATH Keywords

Kneser graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Extremal set theory (05D05) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Cites Work

• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• On the Shannon capacity of a graph
• Title not available (Why is that?)
• Independent sets in hypergraphs
• Extremal Results in Random Graphs
• On the number of graphs without 4-cycles
• SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• On generalized graphs
• Intersecting families of discrete structures are typically trivial
• Erdős–Ko–Rado in Random Hypergraphs
• Intersecting Families are Essentially Contained in Juntas
• Rado Partition Theorem for Random Subsets of Integers
• Threshold Functions for Ramsey Properties
• Set systems without a simplex or a cluster
• Shadows and intersections: Stability and new proofs
• On the measure of intersecting families, uniqueness and stability
• Extremal subgraphs of random graphs
• On separating systems of a finite set

Cited In (23)

• Asymptotics of the independence number of a random subgraph of the graph \(G(n,r,<s)\)
• On stability of the independence number of a certain distance graph
• On ``stability in the Erdős-Ko-Rado theorem
• On the stability of some Erdős-Ko-Rado type results
• Removal and stability for Erdős-Ko-Rado
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Chromatic number of random Kneser hypergraphs
• On random subgraphs of Kneser and Schrijver graphs
• On threshold probability for the stability of independent sets in distance graphs
• Erdős–Ko–Rado for Random Hypergraphs: Asymptotics and Stability
• On the chromatic number of random subgraphs of a certain distance graph
• On the random version of the Erdős matching conjecture
• Size and structure of large \((s,t)\)-union intersecting families
• Stability results for vertex Turán problems in Kneser graphs
• Sharp bounds for the chromatic number of random Kneser graphs
• Extremal \(G\)-free induced subgraphs of Kneser graphs
• A simple removal lemma for large nearly-intersecting families
• Stability versions of Erdős-Ko-Rado type theorems via isoperimetry
• Sharp threshold for the Erdős–Ko–Rado theorem
• Sharp bounds for the chromatic number of random Kneser graphs
• Independence numbers of random subgraphs of some distance graph
• Random Kneser graphs and hypergraphs
• Title not available (Why is that?)

This page was built for publication: Transference for the Erdős-Ko-Rado theorem

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