The integrality gap of the Goemans-Linial SDP relaxation for sparsest cut is at least a constant multiple of √log n
Assaf Naor, Robert M. Young · 2017
We prove that the integrality gap of the Goemans-Linial semidefinite programming relaxation for the Sparsest Cut Problem is Ω(√logn) on inputs with n vertices, thus matching the previously best known upper bound (logn)1/2+o(1) up to lower-order factors. This statement is a consequence of the following new isoperimetric-type inequality. Consider the 8-regular graph whose vertex set is the 5-dimensional integer grid ℤ5 and where each vertex (a,b,c,d,e)∈ ℤ5 is connected to the 8 vertices (a± 1,b,c,d,e), (a,b± 1,c,d,e), (a,b,c± 1,d,e± a), (a,b,c,d± 1,e± b). This graph is known as the Cayley graph of the 5-dimensional discrete Heisenberg group. Given Ω⊆ ℤ5, denote the size of its edge boundary in this graph (a.k.a. the horizontal perimeter of Ω) by |∂hΩ|. For t ϵ ℕ, denote by |∂vtΩ| the number of (a,b,c,d,e)ϵ ℤ5 such that exactly one of the two vectors (a,b,c,d,e),(a,b,c,d,e+t) is in Ω. The vertical perimeter of Ω is defined to be |∂vΩ|= √Σt=1∞|∂vtΩ|2/t2. We show that every subset Ω⊆ ℤ5 satisfies |∂vΩ|=O(|∂hΩ|). This vertical-versus-horizontal isoperimetric inequality yields the above-stated integrality gap for Sparsest Cut and answers several geometric and analytic questions of independent interest.