Computer Science/Discrete Mathematics Seminar I

In 1970s Paul Erdos asked the following question: Consider all the boolean strings of length n. Assume that one has chosen a subset S of the strings such that no two chosen strings are different in precisely n/4 (or its closest even integer) coordinates. How big can the set of chosen strings be? Erdos conjectured that the answer is small (in a precise sense) and put a $250 prize for a solution. In 1987 Frankl and Rodl proved a strong form of this conjecture showing that such a set has to be exponentially smaller than the set of all strings of length n. 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)