We study the following "density" variant of the above problem: Assume that one has selected a "big" subset of the strings of length n. By Frankl-Rodl we know that there is at least one pair of selected strings that are different in exactly n/4 coordinates, but can one show a stronger statement? In particular, can one show that there are "many" pairs of selected strings which are different in exactly n/4 coordinates? We answer this question positively using a proof technique very different than Frankl and Rodl's. In particular our proof relies on Fourier analysis on the cube. Our Theorem can be thought of as an Isoperimetric inequality of the Hamming Cube and is closely related to a result of E. Mossel, R. O'Donnell, O. Regev, J. Steif and B. Sudakov.

We use our theorem to show that certain strong linear and semidefinite programming relaxations of the Vertex Cover and Independent Set problems in degree-bounded graphs have large Integrality Gaps, i.e. they can not be used to get approximation algorithms far better than what is currently known. Our approach lets us start with a previously known Integrality Gap for the general problem (which uses a certain underlying graph) and use a simple sampling argument to transform it to an Integrality Gap in the degree-bounded setting while mostly avoiding the hard work that goes into constructing solutions for the linear/semidefinite programming relaxation.

Based on a joint work with Hamed Hatami (McGill) and Avner Magen (formerly U. of Toronto)