On rank-monotone graph operations and minimal obstruction graphs for the Lovász–Schrijver SDP hierarchy

We study the lift-and-project rank of the stable set polytopes of graphs with respect to the Lovász–Schrijver SDP operator \({{\,\textrm{LS}\,}}_+\), with a particular focus on finding and characterizing the smallest graphs with a given \({{\,\textrm{LS}\,}}_+\)-rank (the needed number of iterations of the \({{\,\textrm{LS}\,}}_+\) operator on the fractional stable set polytope to compute the stable set polytope). We introduce a generalized vertex-stretching operation that appears to be promising in generating \({{\,\textrm{LS}\,}}_+\)-minimal graphs and study its properties. We also provide several new \({{\,\textrm{LS}\,}}_+\)-minimal graphs, most notably the first known instances of 12-vertex graphs with \({{\,\textrm{LS}\,}}_+\)-rank 4, which provides the first advance in this direction since Escalante, Montelar, and Nasini’s discovery of a 9-vertex graph with \({{\,\textrm{LS}\,}}_+\)-rank 3 in 2006.

Authors and Affiliations

1. Department of Mathematics and Statistics, University of Saskatchewan, Saskatoon, SK, S7N 5E6, Canada

   Yu Hin Au

2. Department of Combinatorics and Optimization, Faculty of Mathematics, University of Waterloo, Waterloo, ON, N2L 3G1, Canada

   Levent Tunçel

Corresponding author

Correspondence to Yu Hin Au.

Conflict of interest

The authors declare that they have no Conflict of interest.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

L. Tunçel: Research of this author was supported in part by an NSERC Discovery Grant.

Proofs of Lemmas 39, 40, and 41

The following lemmas provide the deferred technical details from the proof of Theorem 26. To reduce cluttering, given \(S \subseteq [n]\) we will let \(\hat{\chi }_S\) denote the vector \(\begin{bmatrix} 1 \\ \chi _S \end{bmatrix} \in \mathbb {R}^{n+1}\).

Lemma 39

Let \(Y_0\) be as defined in the proof of Theorem 26. Then

Proof

First, notice that \([Y_0(e_0 - e_1)]_{1} = 0\). Thus, let \(G' :=G_{4,1} - 1\) and v be the restriction of \(Y_0(e_0 - e_1)\) to the coordinates indexed by \({{\,\textrm{cone}\,}}({{\,\textrm{LS}\,}}_+^2(G'))\). Then, by Lemma 4, it suffices to show that \(v \in {{\,\textrm{cone}\,}}({{\,\textrm{LS}\,}}_+^2(G'))\). Consider the matrix

We claim that \(Y_2 \in \widehat{{{\,\textrm{LS}\,}}}_+^2(G')\). First, one can verify that \(Y_2 \succeq 0\) (a UV-certificate is provided in Table 1). Also, notice that the function \(f_2\) (restricted to \(V(G')\)) is an automorphism of \(G'\). Moreover, observe that for all \(i,j \in V(G')\), \(Y_2[i,j] = Y_2[f_2(i), f_2(j)]\). Thus, by symmetry, it only remains to prove the conditions \(Y_2e_i, Y_2(e_0-e_i) \in {{\,\textrm{cone}\,}}({{\,\textrm{LS}\,}}_+(G'))\) for \(i \in \left\{ 2,4_1,4_0,4_2,6_1,6_0\right\} \).

First, notice that

• \([Y_2e_{4_0}]_{0} = [Y_2e_{4_0}]_{4_0}\), \([Y_2e_{4_0}]_{4_1} = [Y_2e_{4_0}]_{4_2} = 0\), and that the following matrix certifies that \(Y_2e_{4_0}\) (with the entries corresponding to vertices \(4_1, 4_0, 4_2\) removed) belongs to \({{\,\textrm{cone}\,}}({{\,\textrm{LS}\,}}_+(G' \ominus 4_0))\).

  

• \([Y_2e_{6_0}]_{0} = [Y_2e_{6_0}]_{6_0}\), \([Y_2e_{6_0}]_{6_1} = [Y_2e_{6_0}]_{6_2} = 0\), and that the following matrix certifies that \(Y_2e_{6_0}\) (with the entries corresponding to vertices \(6_1, 6_0, 6_2\) removed) belongs to \({{\,\textrm{cone}\,}}({{\,\textrm{LS}\,}}_+(G' \ominus 6_0))\).

  

• \([Y_2(e_0-e_2)]_{2} =0\), and that the following matrix certifies that \(Y_2(e_0-e_2)\) (with the entry corresponding to vertex 2 removed) belongs to \({{\,\textrm{cone}\,}}({{\,\textrm{LS}\,}}_+(G' - 2))\).

  

• \([Y_2(e_0-e_{4_1})]_{4_1} =0\), and that the following matrix certifies that \(Y_2(e_0-e_{4_1})\) (with the entry corresponding to vertex \(4_1\) removed) belongs to \({{\,\textrm{cone}\,}}({{\,\textrm{LS}\,}}_+(G' - 4_1))\).

  

Also, notice that \(Y_{21}e_0 = Y_{21}(e_{5_0} + e_{5_2})\). Thus, if we let \(Y'_{21}\) be the matrix obtained from \(Y_{21}\) by removing the \(0^{\text {th}}\) row and column, then we see that \(Y'_{21} \succeq 0 \Rightarrow Y_{21} \succeq 0\). The UV-certificates of \(Y'_{21}, Y_{22}, Y_{23}\), and \(Y_{24}\) are provided in Table 1.

Next, observe that

Since all incidence vectors above correspond to stable sets in \(G'\), and we already showed earlier that \(Y_2e_{4_0}, Y_2e_{6_0} \in {{\,\textrm{cone}\,}}({{\,\textrm{LS}\,}}_+(G'))\), we obtain that all the vectors above belong to \({{\,\textrm{cone}\,}}({{\,\textrm{LS}\,}}_+(G'))\). Thus, we conclude that \(Y_0(e_0-e_1) \in {{\,\textrm{cone}\,}}({{\,\textrm{LS}\,}}_+^2(G_{4,1}))\). \(\square \)

Lemma 40

Let \(Y_0\) be as defined in the proof of Theorem 26. Then

Proof

First, notice that \([Y_0e_{6_0}]_{0} = [Y_0e_{6_0}]_{6_0}\), and \([Y_0e_{6_0}]_{6_1} = [Y_0e_{6_0}]_{6_2} = 0\). Thus, let \(G' :=G_{4,1} \ominus 6_0\) and v be the restriction of \(Y_0e_{6_0}\) to the coordinates indexed by \({{\,\textrm{cone}\,}}({{\,\textrm{LS}\,}}_+^2(G'))\). Then, by Lemma 4, it suffices to show that \(v \in {{\,\textrm{cone}\,}}({{\,\textrm{LS}\,}}_+^2(G'))\). Consider the matrix

We claim that \(Y_1 \in \widehat{{{\,\textrm{LS}\,}}}_+^2(G')\). First, one can verify that \(Y_1 \succeq 0\) (a UV-certificate is provided in Table 1). Also, notice that the function \(f_2\) (restricted to \(V(G')\)) is an automorphism of \(G'\). Moreover, observe that for all \(i,j \in V(G')\), \(Y_1[i,j] = Y_1[f_2(i), f_2(j)]\). Thus, by symmetry, it only remains to prove the conditions \(Y_1e_i, Y_1(e_0-e_i) \in {{\,\textrm{cone}\,}}({{\,\textrm{LS}\,}}_+(G'))\) for \(i \in \left\{ 1,2,4_1,4_0,4_2\right\} \).

First, notice that \([Y_1e_{4_0}]_{0} = [Y_1e_{4_0}]_{4_0}\), \([Y_1e_{4_0}]_{4_1} = [Y_1e_{4_0}]_{4_2} = 0\), and that the following matrix certifies that \(Y_1e_{4_0}\) (with the entries corresponding to vertices \(4_1, 4_0, 4_2\) removed) belongs to \({{\,\textrm{cone}\,}}({{\,\textrm{LS}\,}}_+(G' \ominus 4_0))\). (See Table 1 for a UV-certificate.)

Now consider the following vectors:

Notice that \(z^{(1)} \in {{\,\textrm{cone}\,}}({{\,\textrm{LS}\,}}_+(G'))\) follows from \(Y_1e_{4_0} \in {{\,\textrm{cone}\,}}({{\,\textrm{LS}\,}}_+(G'))\) as shown above. Then it follows from the symmetry of \(G'\) that \(z^{(2)} \in {{\,\textrm{cone}\,}}({{\,\textrm{LS}\,}}_+(G'))\) as well. \(z^{(3)}, z^{(4)} \in {{\,\textrm{cone}\,}}({{\,\textrm{LS}\,}}_+(G'))\) follows respectively from \(Y_2e_{4_0}, Y_2e_{6_0} \in {{\,\textrm{cone}\,}}({{\,\textrm{LS}\,}}_+(G_{4,1} - 1))\), as shown in Lemma 39. Next, observe that

Since all incidence vectors above correspond to stable sets in \(G'\), we obtain that all the vectors above belong to \({{\,\textrm{cone}\,}}({{\,\textrm{LS}\,}}_+(G'))\). Thus, we conclude that \(Y_0e_{6_0} \in {{\,\textrm{cone}\,}}({{\,\textrm{LS}\,}}_+^2(G_{4,1}))\). \(\square \)

Lemma 41

Let \(Y_0\) be as defined in the proof of Theorem 26. Then

Proof

For convenience, let \(G :=G_{4,1}\) throughout this proof. Using \(Y_0e_{6_0} \in {{\,\textrm{cone}\,}}({{\,\textrm{LS}\,}}_+^2(G))\) from Lemma 40 and the symmetry of G, we know that the vector

belongs to \({{\,\textrm{cone}\,}}({{\,\textrm{LS}\,}}_+^2(G))\). Now observe that

Notice that all incidence vectors above correspond to stable sets in G. Since \({{\,\textrm{cone}\,}}({{\,\textrm{LS}\,}}_+^{2}(G))\) is a lower-comprehensive convex cone, it follows that \(Y_0(e_0-e_{4_1}) \in {{\,\textrm{cone}\,}}({{\,\textrm{LS}\,}}_+^{2}(G))\). \(\square \)

Finally, we provide in Table 1 the UV-certificates of all PSD matrices used in Theorem 26 and Lemmas 39, 40, and 41.

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions