Transference for the Erdős-Ko-Rado theorem

DOI10.1017/FMS.2015.21MaRDI QIDQ3449986zbMATH OpenOpenAlexFDO

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

Publication date 2 November 2015

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

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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

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)

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.

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

Cites work

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

Cited in

(26)

• On the stability of the Erdős-Ko-Rado theorem
• On threshold probability for the stability of independent sets in distance graphs
• On random subgraphs of Kneser and Schrijver graphs
• Sharp threshold for the Erdős–Ko–Rado theorem
• On the stability of the Erdös-Ko-Rado theorem
• On the chromatic number of random subgraphs of a certain distance graph
• On the random version of the Erdős matching conjecture
• Removal and stability for Erdős-Ko-Rado
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Kneser graphs are like Swiss cheese
• Random Kneser graphs and hypergraphs
• Extremal \(G\)-free induced subgraphs of Kneser graphs
• A simple removal lemma for large nearly-intersecting families
• 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
• Size and structure of large \((s,t)\)-union intersecting families
• On ``stability in the Erdős-Ko-Rado theorem
• On the stability of some Erdős-Ko-Rado type results
• Sharp bounds for the chromatic number of random Kneser graphs
• Stability versions of Erdős-Ko-Rado type theorems via isoperimetry
• Independence numbers of random subgraphs of some distance graph
• scientific article; zbMATH DE number 4045192 (Why is no real title available?)
• Stability results for vertex Turán problems in Kneser graphs
• Chromatic number of random Kneser hypergraphs
• Sharp bounds for the chromatic number of random Kneser graphs
• Erdős-Ko-Rado for random hypergraphs: asymptotics and stability

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)