Computing the Grothendieck constant of some graph classes

Abstract

Given a graph $G=([n],E)$ and $w\in {\mathbb{R}}^E$, consider the integer program ${\max }_{x\in \{\pm 1{\}}^n}{\sum }_{ij\in E}{w}_{ij}{x}_i{x}_j$ and its canonical semidefinite programming relaxation $\max {\sum }_{ij\in E}{w}_{ij}{v}_i^T{v}_j$, where the maximum is taken over all unit vectors $v_i\in {\mathbb{R}}^n$. The integrality gap of this relaxation is known as the Grothendieck constant $\ka(G)$ of $G$. We present a closed-form formula for the Grothendieck constant of $K_5$-minor free graphs and derive that it is at most 3/2. Moreover, we show that $\ka(G)\le \ka(K_k)$ if the cut polytope of $G$ is defined by inequalities supported by at most $k$ points. Lastly, since the Grothendieck constant of $K_n$ grows as $\Theta (\log n)$, it is interesting to identify instances with large gap. However this is not the case for the clique-web inequalities, a wide class of valid inequalities for the cut polytope, whose integrality ratio is shown to be bounded by 3.

7 pages