Geodesic
Kneser graphs are like Swiss cheese
Discrete analysis (2018) Cet article a éte moissonné depuis la source Scholastica

Voir la notice de l'article

We prove that for a large family of product graphs, and for Kneser graphs $K(n,αn)$ with fixed $α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].
Publié le : 
@article{DAS_2018_a20,
     author = {Ehud Friedgut and Oded Regev},
     title = {Kneser graphs are like {Swiss} cheese},
     journal = {Discrete analysis},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DAS_2018_a20/}
}
TY  - JOUR
AU  - Ehud Friedgut
AU  - Oded Regev
TI  - Kneser graphs are like Swiss cheese
JO  - Discrete analysis
PY  - 2018
UR  - http://geodesic.mathdoc.fr/item/DAS_2018_a20/
LA  - en
ID  - DAS_2018_a20
ER  - 
%0 Journal Article
%A Ehud Friedgut
%A Oded Regev
%T Kneser graphs are like Swiss cheese
%J Discrete analysis
%D 2018
%U http://geodesic.mathdoc.fr/item/DAS_2018_a20/
%G en
%F DAS_2018_a20
Ehud Friedgut; Oded Regev. Kneser graphs are like Swiss cheese. Discrete analysis (2018). http://geodesic.mathdoc.fr/item/DAS_2018_a20/