Removal and stability for Erdős-Ko-Rado

DOI10.1137/15M105149XMaRDI QIDQ2808164zbMATH OpenFDO

Authors Shagnik Das, Tuan Tran

Publication date 26 May 2016

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

stabilityremoval lemmaErdős-Ko-Rado theorem

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Extremal set theory (05D05)

Abstract: A $k$-uniform family of subsets of $[n]$ is intersecting if it does not contain a disjoint pair of sets. The study of intersecting families is central to extremal set theory, dating back to the seminal ErdH{o}s-Ko-Rado theorem of 1961 that bounds the size of the largest such families. A recent trend has been to investigate the structure of set families with few disjoint pairs. Friedgut and Regev proved a general removal lemma, showing that when $gammanlekle(frac12-gamma)n$, a set family with few disjoint pairs can be made intersecting by removing few sets. We provide a simple proof of a removal lemma for large families, showing that families of size close to $$ with relatively few disjoint pairs must be close to a union of $ell$ stars. Our lemma holds for a wide range of uniformities; in particular, when $ell=1$, the result holds for all $2lek<fracn2$ and provides sharp quantitative estimates. We use this removal lemma to settle a question of Bollob'as, Narayanan and Raigorodskii regarding the independence number of random subgraphs of the Kneser graph $K(n,k)$. The ErdH{o}s-Ko-Rado theorem shows $$. For some constant $c>0$ and $klecn$, we determine the sharp threshold for when this equality holds for random subgraphs of $K(n,k)$, and provide strong bounds on the critical probability for $klefrac12(n-3)$.

Recommendations

• A simple removal lemma for large nearly-intersecting families
• On the stability of the Erdős-Ko-Rado theorem
• Transference for the Erdős-Ko-Rado theorem
• Sharp threshold for the Erdős–Ko–Rado theorem
• The Erdős-Ko-Rado theorem for small families

Cites work

• scientific article; zbMATH DE number 3478938 (Why is no real title available?)
• Boolean functions whose Fourier transform is concentrated on the first two levels.
• Compressions and probably intersecting families
• Erdős-Ko-Rado for random hypergraphs: asymptotics and stability
• Erdős-Ko-Rado in random hypergraphs
• Erdős-Ko-Rado theorem with conditions on the maximal degree
• Friedgut-Kalai-Naor theorem for slices of the Boolean cube
• Graph removal lemmas
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Intersecting Families are Essentially Contained in Juntas
• Intersecting families of discrete structures are typically trivial
• Most probably intersecting families of subsets
• Most probably intersecting hypergraphs
• On Erdős-Ko-Rado for random hypergraphs. I
• On Erdős-Ko-Rado for random hypergraphs. II
• On ``stability in the Erdős-Ko-Rado theorem
• On the Shannon capacity of a graph
• On the measure of intersecting families, uniqueness and stability
• On the stability of the Erdős-Ko-Rado theorem
• Probably intersecting families are not nested
• SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Set systems without a simplex or a cluster
• Shadows and intersections: Stability and new proofs
• The minimum number of disjoint pairs in set systems and related problems
• Transference for the Erdős-Ko-Rado theorem

Cited in

(20)

• 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
• A structure theorem for almost low-degree functions on the slice
• Asymptotics of the independence number of a random subgraph of the graph \(G(n, r, < s)\)
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Intersecting families of sets are typically trivial
• On the random version of the Erdős matching conjecture
• Stability for vertex isoperimetry in the cube
• Sharp bounds for the chromatic number of random Kneser graphs
• Structure and supersaturation for intersecting families
• A simple removal lemma for large nearly-intersecting families
• Erdős-Ko-Rado for random hypergraphs: asymptotics and stability
• The Removal of Weighted ε-Transitions
• Hypergraph removal lemmas via robust sharp threshold theorems
• Sharp threshold for the Erdős–Ko–Rado theorem
• Sharp bounds for the chromatic number of random Kneser graphs
• Kneser graphs are like Swiss cheese
• Inverse problems of the Erdős-Ko-Rado type theorems for families of vector spaces and permutations
• Invitation to intersection problems for finite sets
• Random Kneser graphs and hypergraphs

This page was built for publication: Removal and stability for Erdős-Ko-Rado

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