Removal and stability for Erdős-Ko-Rado

DOI10.1137/15M105149XzbMATH Open1336.05141arXiv1412.7885MaRDI QIDQ2808164FDOQ2808164

Authors: Shagnik Das, Tuan Tran 

Publication date: 26 May 2016

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

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)$.

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

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

zbMATH Keywords

stabilityremoval lemmaErdős-Ko-Rado theorem

Mathematics Subject Classification ID

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

Cites Work

• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• On the Shannon capacity of a graph
• Transference for the Erdős-Ko-Rado theorem
• Title not available (Why is that?)
• Erdős-Ko-Rado for random hypergraphs: asymptotics and stability
• On the stability of the Erdős-Ko-Rado theorem
• SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Erdős-Ko-Rado theorem with conditions on the maximal degree
• Intersecting families of discrete structures are typically trivial
• Most probably intersecting hypergraphs
• Most probably intersecting families of subsets
• Compressions and probably intersecting families
• Friedgut-Kalai-Naor theorem for slices of the Boolean cube
• Erdős-Ko-Rado in random hypergraphs
• Intersecting Families are Essentially Contained in Juntas
• Probably intersecting families are not nested
• On Erdős-Ko-Rado for random hypergraphs. II
• On Erdős-Ko-Rado for random hypergraphs. I
• The minimum number of disjoint pairs in set systems and related problems
• Set systems without a simplex or a cluster
• Shadows and intersections: Stability and new proofs
• On the measure of intersecting families, uniqueness and stability
• Graph removal lemmas
• Boolean functions whose Fourier transform is concentrated on the first two levels.
• On ``stability in 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)\)
• Intersecting families of sets are typically trivial
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• 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
• Erdős-Ko-Rado for random hypergraphs: asymptotics and stability
• A simple removal lemma for large nearly-intersecting families
• 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)