Kneser graphs are like Swiss cheese

Ehud Friedgut, Oded Regev

We prove that for a large family of product graphs, and for Kneser graphs $K(n,\alpha n)$ with fixed $\alpha <1/2$, the following holds. Any set of vertices that spans a small proportion of th…