Kneser graphs are like Swiss cheese

DOI10.19086/DA.3103MaRDI QIDQ4645027zbMATH OpenOpenAlexFDO

Authors Ehud Friedgut, Oded Regev

Publication date 9 January 2019

Published in Discrete Analysis (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Extremal set theory (05D05)

Abstract: We prove that for a large family of product graphs, and for Kneser graphs $K(n,alphan)$ with fixed $alpha<1/2$, the following holds. Any set of vertices that spans a small proportion of the edges in the graph can be made independent by removing a small proportion of the vertices of the graph. This allows us to strengthen the results of [DinurFR06] and [DinurF09], and show that any independent set in these graphs is almost contained in an independent set which depends on few coordinates. Our proof is inspired by, and follows some of the main ideas of, Fox's proof of the graph removal lemma [Fox11].

Recommendations

• Independence number of products of Kneser graphs
• A simple removal lemma for large nearly-intersecting families
• On the stability of some Erdős-Ko-Rado type results
• Transference for the Erdős-Ko-Rado theorem
• On random subgraphs of Kneser and Schrijver graphs

Cites work

• A new proof of the graph removal lemma
• A removal lemma for systems of linear equations over finite fields
• An arithmetic analogue of Fox's triangle removal argument
• Conditional Hardness for Approximate Coloring
• scientific article; zbMATH DE number 3609704 (Why is no real title available?)
• Independent sets in graph powers are almost contained in juntas
• Intersecting Families are Essentially Contained in Juntas
• Noise stability of functions with low influences: invariance and optimality
• On the conditional hardness of coloring a 4-colorable graph with super-constant number of colors
• On the removal lemma for linear systems over abelian groups
• Removal and stability for Erdős-Ko-Rado

Cited in

(11)

• On set systems without a simplex-cluster and the junta method
• On arithmetic progressions in symmetric sets in finite field model
• The junta method for hypergraphs and the Erdős-Chvátal simplex conjecture
• High dimensional Hoffman bound and applications in extremal combinatorics
• Hypergraph removal lemmas via robust sharp threshold theorems
• On symmetric intersecting families of vectors
• KKL's influence on me
• Kneser graphs are Hamiltonian
• Testing intersectingness of uniform families
• Kneser graphs are Hamiltonian
• Testing intersectingness of uniform families

This page was built for publication: Kneser graphs are like Swiss cheese

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