1 Introduction↩︎

In combinatorial optimization, a standard approach for tackling a given problem is to encode its set of feasible solutions geometrically (e.g., via an integer programming formulation). While the exact solution set is often difficult to analyze, we can focus on relaxations of this set that have certain desirable properties (e.g., combinatorially simple to describe, approximates the underlying set of solutions well, and/or is computationally efficient to optimize over). In that regard, the lift-and-project approach provides a systematic procedure which generates progressively tighter convex relaxations of any given \(0,1\) optimization problem. In the last four decades, many procedures that fall under the lift-and-project approach have been devised (see, among others, [1]–[6]), and there is an extensive body of work on their general properties and performance on a wide range of discrete optimization problems (see, for instance, [7] and the references therein). Lift-and-project operators can be classified into two groups based on the type of convex relaxations they generate: Those that generate polyhedral relaxations only (leading to Linear Programming relaxations), and those that generate spectrahedral relaxations (leading to Semidefinite Programming relaxations) which are not necessarily polyhedral. Herein, we focus on \(\mathop{\mathrm{LS}}_+\) (defined in detail in Section 2), the SDP-based lift-and-project operator due to Lovász and Schrijver [2], and its performance on the stable set problem of graphs. This lift-and-project operator was originally called \(N_+\) in [2].

\(\mathop{\mathrm{LS}}_+\) is an operator on convex subsets of the hypercube \([0,1]^n\) — given a convex set \(P \subseteq [0,1]^n\), \(\mathop{\mathrm{LS}}_+(P)\) is a convex set sandwiched between \(P\) and the convex hull of integral points in \(P\), denoted by \(P_I\): \[P \supseteq \mathop{\mathrm{LS}}_+(P) \supseteq P_I.\] The convex hull of integral points in a set is also called its integer hull. So, \(P_I\) is the integer hull of \(P\).

We can apply \(\mathop{\mathrm{LS}}_+\) iteratively to obtain yet tighter relaxations. Given \(p \in \mathbb{N}\), let \(\mathop{\mathrm{LS}}_+^p(P)\) be the set obtained from applying \(p\) successive \(\mathop{\mathrm{LS}}_+\) operations to \(P\). Then it is well known (e.g., it follows from [2] and the definition of \(\mathrm{LS}_+\)) that \[\mathop{\mathrm{LS}}_+^0(P) \mathrel{\vcenter{:}}= P \supseteq \mathop{\mathrm{LS}}_+(P) \supseteq \mathop{\mathrm{LS}}_+^2(P) \supseteq \cdots \supseteq \mathop{\mathrm{LS}}_+^{n-1}(P) \supseteq \mathop{\mathrm{LS}}_+^n(P) = P_I.\] Thus, \(\mathop{\mathrm{LS}}_+\) generates a hierarchy of progressively tighter convex relaxations which converge to \(P_I\) in no more than \(n\) iterations. The reader may refer to Lovász and Schrijver [2] for some other fundamental properties of the \(\mathop{\mathrm{LS}}_+\) operator.

The \(\mathop{\mathrm{LS}}_+\)-rank of a convex subset of the hypercube is defined to be the number of iterations it takes \(\mathop{\mathrm{LS}}_+\) to return its integer hull. As we stated above, the \(\mathop{\mathrm{LS}}_+\)-rank of every convex set \(P \subseteq [0,1]^n\) is at most \(n\), and a number of elementary polytopes in \(\mathbb{R}^n\) have been shown to have \(\mathop{\mathrm{LS}}_+\)-rank \(\Theta(n)\) (see, among others, [8]–[12]).

Next, given a simple, undirected graph \(G=(V,E)\), we denote by \(\mathop{\mathrm{STAB}}(G)\) the stable set polytope of \(G\) (the convex hull of incidence vectors of stable sets in \(G\)), and by \(\mathop{\mathrm{FRAC}}(G)\) the fractional stable set polytope of \(G\) (which is defined by edge inequalities — i.e., \(x_i + x_j \leq 1\) for every edge \(\left\{i,j\right\} \in E(G)\) — and non-negativity constraints, see Section 2.2). Then, we define the \(\mathop{\mathrm{LS}}_+\)-rank of a graph \(G\) as the minimum non-negative integer \(p\) for which \(\mathop{\mathrm{LS}}_+^p(\mathop{\mathrm{FRAC}}(G)) = \mathop{\mathrm{STAB}}(G)\). We denote the \(\mathop{\mathrm{LS}}_+\)-rank of a graph \(G\) by \(r_+(G)\). When \(G\) is bipartite, \(\mathop{\mathrm{FRAC}}(G) = \mathop{\mathrm{STAB}}(G)\), and thus \(r_+(G)=0\) in this case.

Another well-studied convex relaxation of \(\mathop{\mathrm{STAB}}(G)\) is \(\mathop{\mathrm{TH}}(G)\), the Lovász theta body [13] of the given graph. A remarkable property of \(\mathop{\mathrm{LS}}_+\) is that \(\mathop{\mathrm{LS}}_+(\mathop{\mathrm{FRAC}}(G)) \subseteq \mathop{\mathrm{TH}}(G)\) for every graph \(G\). That is, applying one iteration of \(\mathop{\mathrm{LS}}_+\) to the fractional stable set polytope of a graph already yields a tractable relaxation of the stable set polytope that is stronger than \(\mathop{\mathrm{TH}}(G)\) (see [2] for a proof). Therefore, it follows that \(r_+(G) \leq 1\) when \(G\) is a perfect graph (defined in Section 2.2), as it is well-known that \(\mathop{\mathrm{TH}}(G) = \mathop{\mathrm{STAB}}(G)\) in this case [13]. For more analyses of various lift-and-project relaxations of the stable set problem, see (among others) [2], [6], [14]–[23].

On the other hand, while the stable set problem is known to be strongly \(\mathcal{NP}\)-hard, hardness results for \(\mathop{\mathrm{LS}}_+\) (or any other lift-and-project operator utilizing semidefinite programming) on the stable set problem have been relatively scarce. Prior to this manuscript, the worst (in terms of performance by \(\mathop{\mathrm{LS}}_+\)) family of graphs was given by the line graphs of odd cliques. Using the fact that the \(\mathop{\mathrm{LS}}_+\)-rank of the fractional matching polytope of the \((2k+1)\)-clique is \(k\) [24], the natural correspondence between the matchings in a given graph and the stable sets in the corresponding line graph, as well as the properties of the \(\mathop{\mathrm{LS}}_+\) operator, it follows that the fractional stable set polytope of the line graph of the \((2k+1)\)-clique (which contains \(\binom{2k+1}{2} = k(2k+1)\) vertices) has \(\mathop{\mathrm{LS}}_+\)-rank \(k\), giving a family of graphs \(G\) with \(r_+(G) = \Theta\left(\sqrt{|V(G)|}\right)\). This lower bound on the \(\mathop{\mathrm{LS}}_+\)-rank of the fractional stable set polytopes has not been improved since 1999. In this manuscript, we present what we believe is the first known family of graphs whose \(\mathop{\mathrm{LS}}_+\)-rank is asymptotically a linear function of the number of vertices.

1.1 A family of challenging graphs \(\left\{H_k\right\}\) for the \(\mathop{\mathrm{LS}}_+\) operator↩︎

For a positive integer \(k\), let \([k] \mathrel{\vcenter{:}}=\left\{1,2, \ldots, k\right\}\). We first define the family of graphs that pertains to our main result.

Figure 1 illustrates the graphs \(H_k\) for several small values of \(k\). Note that \(H_2\) is the cycle on six vertices. Moreover, \(H_k\) can be obtained from a complete bipartite graph by fixing a perfect matching and replacing each edge by a path of length two (subdividing each matching edge). Figure 2 represents a drawing emphasizing this second feature.

The following is the main result of this paper. Its proof is given in Section 4.

We remark that, given \(p \in \mathbb{N}\) and a polytope \(P \subseteq [0,1]^n\) with \(\Omega(n^c)\) facets for some constant \(c\), the straightforward formulation of \(\mathop{\mathrm{LS}}_+^p(P)\) is an SDP with size \(n^{\Omega(p)}\). Since the fractional stable set polytope of the graph \(H_k\) has dimension \(n=3k\) with \(\Omega(n^2)\) facets, Theorem 1 implies that the SDP described by \(\mathop{\mathrm{LS}}_+\) that fails to exactly represent the stable set polytope of \(H_k\) has size \(n^{\Omega(n)}\). Thus, the consequence of Theorem 1 on the size of the SDPs generated from the \(\mathop{\mathrm{LS}}_+\) operator is incomparable with the extension complexity bound due to Lee, Raghavendra, and Steurer [25], who showed (in the context of SDP extension complexity) that it takes an SDP of size \(2^{\Omega(n^{1/13})}\) to exactly represent the stable set polytope of a general \(n\)-vertex graph as a projection of a spectrahedron (such sets are also called spectrahedral shadows). That is, while the general lower bound by  [25] covers every lifted-SDP formulation, our lower bound is significantly larger but it only applies to a specific family of lifted-SDP formulations.

1.2 Organization of the paper↩︎

In Section 2, we introduce the \(\mathop{\mathrm{LS}}_+\) operator and the stable set problem, and establish some notations and basic facts that will aid our subsequent discussion. In Section 3, we study the family of graphs \(H_k\), their stable set polytope and set up some fundamental facts and the proof strategy. We then prove Theorem 1 in Section 4. In Section 5 we determine the Chvátal–Gomory rank of the stable set polytope of the graphs \(H_k\). In Section 6, we show that the results in Sections 3 and 4 readily lead to the discovery of families of vertex-transitive graphs whose \(\mathop{\mathrm{LS}}_+\)-rank also exhibits asymptotically linear growth. Finally, in Section 7, we close by mentioning some natural research directions inspired by these new findings.

2 Preliminaries↩︎

In this section, we establish the necessary definitions and notation for our subsequent analysis.

2.1 The lift-and-project operator \(\mathop{\mathrm{LS}}_+\)↩︎

Here, we define the lift-and-project operator \(\mathop{\mathrm{LS}}_+\) due to Lovász and Schrijver [2] and mention some of its basic properties. Given a convex set \(P \subseteq [0,1]^n\), we define the cone \[\mathop{\mathrm{cone}}(P) \mathrel{\vcenter{:}}=\left\{ \begin{bmatrix} \lambda\\ \lambda x \end{bmatrix} : \lambda\geq 0, x \in P\right\},\] and index the new coordinate by \(0\). Given a vector \(x\) and an index \(i\), we may refer to the \(i\)-entry in \(x\) by \(x_i\) or \([x]_i\). All vectors are column vectors, so here the transpose of \(x\), \(x^{\top}\), is a row vector. Next, given a symmetric matrix \(M \in \mathbb{R}^{n \times n}\) (which necessarily has only real eigenvalues), we say that \(M\) is positive semidefinite and write \(M \succeq 0\) if all eigenvalues of \(M\) are non-negative. We let \(\mathbb{S}_+^n\) denote the set of \(n\)-by-\(n\) symmetric positive semidefinite matrices, and \(\mathop{\mathrm{diag}}(Y)\) be the vector formed by the diagonal entries of a square matrix \(Y\). We also let \(e_i\) be the \(i^{\textrm{th}}\) unit vector.

Given \(P \subseteq [0,1]^n\), the operator \(\mathop{\mathrm{LS}}_+\) first lifts \(P\) to the following set of matrices: \[\widehat{\mathop{\mathrm{LS}}}_+(P) \mathrel{\vcenter{:}}=\left\{ Y \in \mathbb{S}_+^{n+1} : Ye_0 = \mathop{\mathrm{diag}}(Y), Ye_i, Y(e_0-e_i) \in \mathop{\mathrm{cone}}(P)~\forall i \in [n] \right\}.\] It then projects the set back down to the following set in \(\mathbb{R}^n\): \[\mathop{\mathrm{LS}}_+(P) \mathrel{\vcenter{:}}=\left\{ x \in \mathbb{R}^n : \exists Y \in \widehat{\mathop{\mathrm{LS}}}_+(P), Ye_0 = \begin{bmatrix} 1 \\ x \end{bmatrix}\right\}.\] Given \(x \in \mathop{\mathrm{LS}}_+(P)\), we say that \(Y \in \widehat{\mathop{\mathrm{LS}}}_+(P)\) is a certificate matrix for \(x\) if \(Ye_0 = \begin{bmatrix} 1 \\ x \end{bmatrix}\). The following is a foundational property of \(\mathop{\mathrm{LS}}_+\) [2].

Therefore, \(\mathop{\mathrm{LS}}_+(P)\) contains the same set of integral solutions as \(P\). Moreover, if \(P\) is a tractable set (i.e., one can optimize a linear function over \(P\) in polynomial time), then so is \(\mathop{\mathrm{LS}}_+(P)\). It is also known that \(\mathop{\mathrm{LS}}_+(P)\) is strictly contained in \(P\) unless \(P = P_I\). Thus, while it is generally \(\mathcal{NP}\)-hard to optimize over the integer hull \(P_I\), \(\mathop{\mathrm{LS}}_+(P)\) offers a tractable relaxation of \(P_I\) that is tighter than the initial relaxation \(P\). Again, the reader may refer to Lovász and Schrijver [2] additional discussion and properties of the \(\mathop{\mathrm{LS}}_+\) operator.

2.2 The stable set polytope and the \(\mathop{\mathrm{LS}}_+\)-rank of graphs↩︎

Given a simple, undirected graph \(G \mathrel{\vcenter{:}}=(V(G), E(G))\), we define its fractional stable set polytope to be \[\mathop{\mathrm{FRAC}}(G) \mathrel{\vcenter{:}}=\left\{ x \in [0,1]^{V(G)} : x_i + x_j \leq 1, \forall \left\{i, j \right\} \in E(G)\right\}.\] We also define \[\mathop{\mathrm{STAB}}(G) \mathrel{\vcenter{:}}=\mathop{\mathrm{FRAC}}(G)_I = \mathop{\mathrm{conv}}\left( \mathop{\mathrm{FRAC}}(G) \cap \left\{0,1\right\}^{V(G)} \right)\] to be the stable set polytope of \(G\). Notice that \(\mathop{\mathrm{STAB}}(G)\) is exactly the convex hull of the incidence vectors of stable sets in \(G\). Also, to reduce cluttering, we will write \(\mathop{\mathrm{LS}}_+^p(G)\) instead of \(\mathop{\mathrm{LS}}_+^p(\mathop{\mathrm{FRAC}}(G))\).

Given a graph \(G\), recall that we let \(r_+(G)\) denote the \(\mathop{\mathrm{LS}}_+\)-rank of \(G\), which is defined to be the smallest integer \(p\) where \(\mathop{\mathrm{LS}}_+^p(G) = \mathop{\mathrm{STAB}}(G)\). More generally, given a linear inequality \(a^{\top} x \leq \beta\) valid for \(\mathop{\mathrm{STAB}}(G)\), we define its \(\mathop{\mathrm{LS}}_+\)-rank to be the smallest integer \(p\) for which \(a^{\top} x \leq \beta\) is a valid inequality of \(\mathop{\mathrm{LS}}_+^p(G)\). Then \(r_+(G)\) can be alternatively defined as the maximum \(\mathop{\mathrm{LS}}_+\)-rank over all valid inequalities of \(\mathop{\mathrm{STAB}}(G)\).

It is well known that \(r_+(G) = 0\) (i.e., \(\mathop{\mathrm{STAB}}(G) = \mathop{\mathrm{FRAC}}(G)\)) if and only if \(G\) is bipartite. Next, given a graph \(G\) and \(C \subseteq V(G)\), we say that \(C\) is a clique if every pair of vertices in \(C\) is joined by edge in \(G\). Then observe that the clique inequality \(\sum_{i \in C} x_i \leq 1\) is valid for \(\mathop{\mathrm{STAB}}(G)\). A graph \(G\) is perfect if \(\mathop{\mathrm{STAB}}(G)\) is defined by only clique and non-negativity inequalities. Since clique inequalities of graphs have \(\mathop{\mathrm{LS}}_+\)-rank \(1\) (see [2] for a proof), we see that \(r_+(G) \leq 1\) for all perfect graphs \(G\).

The graphs \(G\) where \(r_+(G) \leq 1\) are commonly called \(\mathop{\mathrm{LS}}_+\)-perfect graphs. In addition to perfect graphs, it is known that odd holes, odd antiholes, and odd wheels (among others) are also \(\mathop{\mathrm{LS}}_+\)-perfect. While it remains an open problem to find a simple combinatorial characterization of \(\mathop{\mathrm{LS}}_+\)-perfect graphs, there has been significant recent interest and progress on this front [26]–[30].

Next, we mention two simple graph operations that have been critical to the analyses of the \(\mathop{\mathrm{LS}}_+\)-ranks of graphs. Given a graph \(G\) and \(S \subseteq V(G)\), we let \(G-S\) denote the subgraph of \(G\) induced by the vertices in \(V(G) \setminus S\), and call \(G-S\) the graph obtained by the deletion of \(S\). (When \(S = \left\{i\right\}\) for some vertex \(i\), we simply write \(G-i\) instead of \(G - \left\{i\right\}\).) Next, given \(i \in V(G)\), let \(\Gamma(i) \mathrel{\vcenter{:}}=\left\{ j \in V(G) : \left\{i,j\right\} \in E(G)\right\}\) (i.e., \(\Gamma(i)\) is the set of vertices that are adjacent to \(i\)). Then the graph obtained from the destruction of \(i\) in \(G\) is defined as \[G \ominus i \mathrel{\vcenter{:}}= G - ( \left\{i\right\} \cup \Gamma(i)).\] Then we have the following.

We next mention a fact that is folklore, with related insights dating back to Balas’ work on disjunctive programming in the 1970s (see, for instance, [31] and [10]).

Using Lemma 2, we obtain another elementary property of \(\mathop{\mathrm{LS}}_+\) that will be useful.

We are interested in studying relatively small graphs with high \(\mathop{\mathrm{LS}}_+\)-rank — that is, graphs whose stable set polytope is difficult to obtain for \(\mathop{\mathrm{LS}}_+\). First, Lipták and the second author [16] proved the following general upper bound:

In Section 4, we prove that the family of graphs \(H_k\) satisfies \(r_+(H_k) = \Theta(|V(H_k)|)\). This shows that Theorem 3 is asymptotically tight, and rules out the possibility of a sublinear upper bound on the \(\mathop{\mathrm{LS}}_+\)-rank of a general graph.

3 Analyzing \(H_k\) and exploiting symmetries↩︎

3.1 The graphs \(H_k\) and their basic properties↩︎

Recall the family of graphs \(H_k\) defined in Section 1 (Definition 1). For convenience, we let \([k]_p \mathrel{\vcenter{:}}=\left\{ j_p : j \in [k]\right\}\) for each \(p \in \left\{0,1,2\right\}\). Then, as mentioned earlier, one can construct \(H_k\) by starting with a complete bipartite graph with bipartitions \([k]_0\) and \([k]_2\), and then for every \(j \in [k]\) subdividing the edge \(\left\{j_0, j_2\right\}\) into a path of length \(2\) and labelling the new vertex \(j_1\). Figure 2 illustrates alternative drawings for \(H_k\) which highlight this aspect of the family of graphs.

Given a graph \(G\), we say that \(\sigma : V(G) \to V(G)\) is an automorphism of \(G\) if, for every \(i,j \in V(G)\), \(\left\{i,j\right\} \in E(G)\) if and only if \(\left\{\sigma(i), \sigma(j)\right\} \in E(G)\). Notice that the graphs \(H_k\) have very rich symmetries, and we mention two automorphisms of \(H_k\) that are of particular interest. Define \(\sigma_1 : V(H_k) \to V(H_k)\) where, for every \(p \in \left\{0,1,2\right\}\), \[\label{eqH95ksigma1} \sigma_1\left( j_p \right) \mathrel{\vcenter{:}}= \begin{cases} (j+1)_p & \textrm{if 1 \leq j \leq k-1;}\\ 1_p & \textrm{if j = k.} \end{cases}\tag{1}\] Also define \(\sigma_2 : V(H_k) \to V(H_k)\) where \[\label{eqH95ksigma2} \sigma_2\left( j_p \right) \mathrel{\vcenter{:}}= j_{(2-p)}~\textrm{for every j \in [k] and p \in \left\{0,1,2\right\}.}\tag{2}\] Visually, \(\sigma_1\) corresponds to rotating the drawings of \(H_k\) in Figure 1 counterclockwise by \(\frac{2\pi}{k}\), and \(\sigma_2\) corresponds to reflecting the drawings of \(H_k\) in Figure 2 along the centre vertical line. Also, notice that \(H_k \ominus i\) is either isomorphic to \(H_{k-1}\) (if \(i \in [k]_1\)), or is bipartite (if \(i \in [k]_0 \cup [k]_2\)). As we shall see, these properties are very desirable in our subsequent analysis of \(H_k\).

Given a graph \(G\), let \(\alpha(G)\) denote the maximum cardinality of a stable set in \(G\). Notice that since \(H_2\) is the \(6\)-cycle, \(\alpha(H_2)=3\), and the maximum cardinality stable sets of \(H_2\) are \(\{1_0, 1_2, 2_1\}\) and \(\{1_1, 2_0,2_2\}\). Moreover, due to the simple recursive structure of this family of graphs, we can construct stable sets for \(H_k\) from stable sets for \(H_{k-1}\) for every integer \(k \geq 3\). If \(S\) is a (maximum-cardinality) stable set for \(H_{k-1}\) then \(S \cup \{k_1\}\) is a (maximum-cardinality) stable set for \(H_k\). This shows that \(\alpha(H_k) = k+1\) for every \(k \geq 2\).

Also, notice that each of the sets \([k]_0\), \([k]_1\), and \([k]_2\) is a stable set in \(H_k\). While they each have cardinality \(k\) and thus are not maximum cardinality stable sets in \(H_k\), they are inclusion-wise maximal (i.e., each of them is not a proper subset of another stable set in \(H_k\)). The following result characterizes all inclusion-wise maximal stable sets in \(H_k\).

Next, we describe two families of valid inequalities of \(\mathop{\mathrm{STAB}}(H_k)\) that are of particular interest. Given distinct indices \(j,j' \in [k]\), define \[B_{j,j'} \mathrel{\vcenter{:}}= V(H_k) \setminus \left\{j_1, j_2, j_0', j_1'\right\}.\] Then we have the following.

3.2 Working from the shadows to prove lower bounds on \(\mathop{\mathrm{LS}}_+\)-rank↩︎

Next, we aim to exploit the symmetries of \(H_k\) to help simplify our analysis of its \(\mathop{\mathrm{LS}}_+\)-relaxations. Before we do that, we describe the broader framework of this reduction that shall also be useful in analyzing lift-and-project relaxations in other settings. Given a graph \(G\), let \(\mathop{\mathrm{Aut}}(G)\) denote the automorphism group of \(G\). We also let \(\chi_S\) denote the incidence vector of a set \(S\). Then we define the notion of \(\mathcal{A}\)-balancing automorphisms.

In other words, if \(\mathcal{S}\) is \(\mathcal{A}\)-balancing, then the automorphisms in \(\mathcal{S}\) only map vertices in \(A_{\ell}\) to vertices in \(A_{\ell}\) for every \(\ell \in [L]\). Moreover, for every \(i \in A_{\ell}\), the \(|\mathcal{S}|\) images of \(i\) under automorphisms in \(\mathcal{S}\) spread over \(A_{\ell}\) evenly, with \(|\left\{ \sigma \in \mathcal{S}: \sigma(i) = j\right\}| = \frac{|\mathcal{S}|}{|A_{\ell}|}\) for every \(j \in A_{\ell}\).

For example, for the graph \(H_k\), consider the vertex partition \(\mathcal{A}_1 \mathrel{\vcenter{:}}=\left\{ [k]_0, [k]_1, [k]_2\right\}\) and \(\mathcal{S}_1 \mathrel{\vcenter{:}}=\left\{ \sigma_1^j : j \in [k]\right\}\) (where \(\sigma_1\) is as defined in 1 ). Then observe that, for every \(p \in \left\{0,1,2\right\}\), \(\left\{ \sigma(i) : i \in [k]_p \right\} = [k]_p\), and \[| \left\{ \sigma \in \mathcal{S}_1 : \sigma(i) = j\right\} | = 1\] for every \(i,j \in [k]_p\). Thus, \(\mathcal{S}_1\) is \(\mathcal{A}_1\)-balancing. Furthermore, if we define \(\mathcal{A}_2 \mathrel{\vcenter{:}}=\left\{ [k]_0 \cup [k]_2 , [k]_1\right\}\) and \[\label{eqS2balancing} \mathcal{S}_2 \mathrel{\vcenter{:}}=\left\{ \sigma_1^j \circ \sigma_2^{j'} : j \in [k], j' \in [2]\right\}\tag{7}\] (where \(\sigma_2\) is as defined in 2 ), one can similarly show that \(\mathcal{S}_2\) is \(\mathcal{A}_2\)-balancing.

Next, we prove several lemmas about \(\mathcal{A}\)-balancing automorphisms that are relevant to the analysis of \(\mathop{\mathrm{LS}}_+\)-relaxations. Given \(\sigma\in \mathop{\mathrm{Aut}}(G)\), we extend the notation to refer to the function \(\sigma : \mathbb{R}^{V(G)} \to \mathbb{R}^{V(G)}\) where \(\sigma(x)_{i} = x_{\sigma(i)}\) for every \(i \in V(G)\). The following lemma follows readily from the definition of \(\mathcal{A}\)-balancing automorphisms.

Combining the above results, we obtain the following.

Notice that the symmetrized vector \(x'\) in Proposition 4 has at most \(L\) distinct entries, one for each of \(A_{\ell} \in \mathcal{A}\). Thus, instead of fully analyzing a family of SDPs in \(\mathbb{S}_+^{\Omega(n^p)}\) or its projections \(\mathop{\mathrm{LS}}_+^p(G)\), the presence of \(\mathcal{A}\)-balancing automorphisms allows us to work with a spectrahedral shadow in \([0,1]^L\), a set of much lower dimension, for a part of the analysis. For instance, in the extreme case when \(G\) is vertex-transitive, we see that the entire automorphism group \(\mathop{\mathrm{Aut}}(G)\) is \(\left\{V(G)\right\}\)-balancing, and so for every \(x \in \mathop{\mathrm{LS}}_+^p(G)\), Proposition 4 implies that \(\frac{1}{|V(G)|}\left(\sum_{i \in V(G)} x_i \right) \bar{e} \in \mathop{\mathrm{LS}}_+^p(G)\), where \(\bar{e}\) denotes the vector of all ones.

Now we turn our focus back to the graphs \(H_k\). The presence of an \(\mathcal{A}_2\)-balancing set of automorphisms (as described in 7 ) motivates the study of points in \(\mathop{\mathrm{LS}}_+^p(H_k)\) of the following form.

For an example, the inequality 4 can be rewritten as \(w(k-1,k-2)^{\top} x \leq k(k-1)\). The following is a main reason why we are interested in looking into points of the form \(w_k(a,b)\).

A key ingredient in our proof of the main result is to find a point \(x \in \mathop{\mathrm{LS}}_+^p(H_k)\) where \(x\) violates 4 for some \(p \in \Theta(k)\), which would imply that \(r_+(H_k) > p\). Lemma 8 assures that, due to the symmetries of \(H_k\), we are not sacrificing any sharpness of the result by only looking for such points \(x\) of the form \(w_k(a,b)\). This enables us to capture important properties of \(\mathop{\mathrm{LS}}_+^p(H_k)\) by analyzing a corresponding “shadow” of the set in \(\mathbb{R}^2\). More explicitly, given \(P \subseteq \mathbb{R}^{V(H_k)}\), we define \[\Phi(P) \mathrel{\vcenter{:}}=\left\{ (a,b) \in \mathbb{R}^2 : w_k(a,b) \in P\right\}.\] For example, it is not hard to see that \[\Phi(\mathop{\mathrm{FRAC}}(H_k)) = \mathop{\mathrm{conv}}\left(\left\{ (0,0), \left(\frac{1}{2},0\right), \left(\frac{1}{2}, \frac{1}{2}\right), (0,1)\right\}\right)\] for every \(k \geq 2\). We can similarly characterize \(\Phi(\mathop{\mathrm{STAB}}(H_k))\).

Even though \(\mathop{\mathrm{STAB}}(H_k)\) is an integral polytope, notice that \(\Phi(\mathop{\mathrm{STAB}}(H_k))\) is not integral. Nonetheless, it is clear that \[\mathop{\mathrm{LS}}_+^p(H_k) = \mathop{\mathrm{STAB}}(H_k) \Rightarrow \Phi(\mathop{\mathrm{LS}}_+^p(H_k)) = \Phi(\mathop{\mathrm{STAB}}(H_k)).\] Thus, to show that \(r_+(H_k) > p\), it suffices to find a point \((a,b) \in \Phi(\mathop{\mathrm{LS}}_+^p(H_k)) \setminus \Phi(\mathop{\mathrm{STAB}}(H_k))\). More generally, given a graph \(G\) with a set of \(\mathcal{A}\)-balancing automorphisms where \(\mathcal{A}\) partitions \(V(G)\) into \(L\) sets, one can adapt our approach and study the \(\mathop{\mathrm{LS}}_+\)-relaxations of \(G\) via analyzing \(L\)-dimensional shadows of these sets.

3.3 Strategy for the proof of the main result↩︎

So far, we have an infinite family of graphs \(\left\{H_k\right\}\) with nice symmetries. In Lemma 5(i) we derived a family of facets of \(\mathop{\mathrm{STAB}}(H_k)\), and then showed in Lemma 5(ii) that these facets imply a symmetrized valid inequality for \(\mathop{\mathrm{STAB}}(H_k)\). Notably, the left hand side of this symmetrized inequality only has two distinct entries — one for the vertices in \([k]_0 \cup [k]_2\), and the other for vertices in \([k]_1\).

Also, due to the symmetries of \(H_k\), these graphs admit \(\mathcal{A}\)-balancing automorphisms. Using that and Proposition 4, we can use an arbitrary point \(x \in \mathop{\mathrm{LS}}_+^p(H_k)\) to derive a symmetrized point \(x' \in \mathop{\mathrm{LS}}_+^p(H_k)\) for every \(k \geq 2\) and \(p \geq 0\). In particular, using the \(\mathcal{A}\)-balancing automorphisms described in 7 , we are assured that the symmetrized \(x'\) has at most two distinct entries — one for vertices in \([k]_0 \cup [k]_2\), and one for vertices in \([k]_1\).

These findings motivate the study of the two dimensional shadow \(\Phi(\mathop{\mathrm{LS}}_+^p(H_k))\) of \(\mathop{\mathrm{LS}}_+^p(H_k)\). We also have a complete characterization of \(\Phi(\mathop{\mathrm{STAB}}(H_k))\) for every integer \(k\geq 2\) (Lemma 9). Thus, to show that \(H_k\) has \(\mathop{\mathrm{LS}}_+\)-rank greater than \(p\), it suffices to establish the existence of a point in the two dimensional set \(\Phi(\mathop{\mathrm{LS}}_+^p(H_k)) \setminus \Phi(\mathop{\mathrm{STAB}}(H_k))\).

The rest of the proof of the main result, presented in the next section, starts by characterizing all symmetric positive semidefinite matrices that could certify the membership of a vector \(x'\) in \(\mathop{\mathrm{LS}}_+(H_k)\) (\(x'\), as mentioned above, has at most two distinct entries). This characterization is relatively simple, since due to the isolated symmetries of \(x'\), there always exists a symmetric positive semidefinite certificate matrix for certifying the membership of \(x'\) in \(\mathop{\mathrm{LS}}_+(H_k)\) which has at most four distinct entries (ignoring the \(00^{\mathrm{th}}\) entry of the certificate matrix, which is one). Next, we construct a compact convex set which is described by three linear inequalities and a quadratic inequality such that this set is a subset of \(\Phi(\mathop{\mathrm{LS}}_+(H_k))\) and a strict superset of \(\Phi(\mathop{\mathrm{STAB}}(H_k))\) for every integer \(k \geq 4\). This enables us to conclude for all \(k \geq 4\), \(r_+(H_k) \geq 2\), and establish some of the tools for the rest of the proof. The point \(w_k\left(\frac{1}{k},\frac{k-1}{k}\right)\) already plays a special role.

Then, we put all these tools together to prove that there is a point in \(\mathop{\mathrm{LS}}_+^p(H_k) \setminus \mathop{\mathrm{STAB}}(H_k)\) which is very close to \(w_k\left(\frac{1}{k},\frac{k-1}{k}\right)\) (we do this partly by working in the \(2\)-dimensional space where \(\Phi(\mathop{\mathrm{LS}}_+^p(H_k)\) lives). For the recursive construction of certificate matrices (to establish membership in \(\mathop{\mathrm{LS}}_+^p(H_k)\)), we show that in addition to the matrix being symmetric, positive semidefinite, and satisfying a simple linear inequality, membership of two suitable vectors \(w_{k-1}(a_1,b_1)\) and \(w_{k-1}(a_2,b_2)\) in \(\mathop{\mathrm{LS}}_+^{p-1}(H_{k-1})\) suffice (Lemma 11). The rest of the analysis proves that there exist values for these parameters which allow the construction of certificate matrices for suitable pairs of integers \(k\) and \(p\).

4 Proof of the main result↩︎

4.1 \(\Phi(\mathop{\mathrm{LS}}_+(H_k))\) — the shadow of the first relaxation↩︎

Here, we aim to study the set \(\Phi(\mathop{\mathrm{LS}}_+(H_k))\). To do that, we first look into potential certificate matrices for \(w_k(a,b)\) that have plenty of symmetries. Given \(k \in \mathbb{N}\) and \(a,b,c,d \in \mathbb{R}\), we define the matrix \(W_k(a,b,c,d) \mathrel{\vcenter{:}}=\begin{bmatrix} 1 & w_k(a,b)^{\top} \\ w_k(a,b) & \overline{W} \end{bmatrix}\), where \[\overline{W} \mathrel{\vcenter{:}}=\begin{bmatrix} a & 0 & a-c \\ 0 & b & 0 \\ a-c & 0 & a \end{bmatrix} \otimes I_k + \begin{bmatrix} c & a-c & 0 \\ a-c & d & a-c \\ 0 & a-c & c \end{bmatrix} \otimes (J_k - I_k).\] Note that \(\otimes\) denotes the Kronecker product, \(I_k\) is the \(k\)-by-\(k\) identity matrix, and \(J_k\) is the \(k\)-by-\(k\) matrix of all ones. Also, \(W_k(a,b,c,d) \in \mathbb{R}^{(\left\{0\right\} \cup V(H_k)) \times (\left\{0\right\} \cup V(H_k))}\), and the \(|V_k| = 3k\) columns of \(\overline{W}\) are indexed by the vertices \(1_0, 1_1, 1_2, 2_0, 2_1, 2_2, \ldots\) from left to right, with the rows following the same ordering. Then we have the following.

Next, for convenience, define \(q_k \mathrel{\vcenter{:}}= 1-\sqrt{\frac{k}{2k-2}}\), and \[p_k(x,y) \mathrel{\vcenter{:}}=(2x^2-x)+2q_k^2(y^2-y)+4q_kxy.\] Notice that the curve \(p_k(x,y) = 0\) is a parabola for all \(k \geq 3\). Then, using Lemma 10, we have the following.

An immediate consequence of Proposition 5 is the following.

Corollary 1 is sharp — notice that destroying any vertex in \(H_3\) yields a bipartite graph, so it follows from Theorem 2(i) that \(r_+(H_3)=1\). Also, since destroying a vertex in \(H_4\) either results in \(H_3\) or a bipartite graph, we see that \(r_+(H_4) = 2\).

4.2 Showing \(r_+(H_k) = \Theta(k)\)↩︎

We now develop a few more tools that we need to establish the main result of this section. Again, to conclude that \(r_+(H_k) > p\), it suffices to show that \(\Phi(\mathop{\mathrm{LS}}_+^p(H_k)) \supset \Phi(\mathop{\mathrm{STAB}}(H_k))\). In particular, we will do so by finding a point in \(\Phi(\mathop{\mathrm{LS}}_+^p(H_k)) \setminus \Phi(\mathop{\mathrm{STAB}}(H_k))\) that is very close to the point \(\left(\frac{1}{k}, \frac{k-1}{k}\right)\). Given \((a,b) \in \mathbb{R}^2\), let \[s_k(a,b) \mathrel{\vcenter{:}}=\frac{\frac{k-1}{k} - b}{\frac{1}{k} - a}.\] That is, \(s_k(a,b)\) is the slope of the line that contains the points \((a,b)\) and \(\left(\frac{1}{k}, \frac{k-1}{k}\right)\). Next, define \[f(k, p) \mathrel{\vcenter{:}}=\sup \left\{ s_k(a,b) : (a,b) \in \Phi(\mathop{\mathrm{LS}}_+^p(H_k)), a > \frac{1}{k}\right\}.\] In other words, \(f(k,p)\) is the slope of the tangent line to \(\Phi(\mathop{\mathrm{LS}}_+^p(H_k))\) at the point \(\left(\frac{1}{k}, \frac{k-1}{k}\right)\) towards the right hand side. Thus, for all \(\ell < f(k,p)\), there exists \(\varepsilon > 0\) where the point \(\left( \frac{1}{k} + \varepsilon, \frac{k-1}{k} + \ell \varepsilon \right)\) belongs to \(\Phi(\mathop{\mathrm{LS}}_+^p(H_k))\). For \(p=0\) (and so \(\mathop{\mathrm{LS}}_+^p(H_k) = \mathop{\mathrm{FRAC}}(H_k)\)), observe that \(f(k, 0) = -1\) for all \(k \geq 2\) (attained by the point \(\left( \frac{1}{2}, \frac{1}{2} \right))\). Next, for \(p=1\), consider the polynomial \(p_k(x,y)\) defined before Proposition 5. Then any point \((x,y)\) on the curve \(p_k(x,y) = 0\) has slope \[\frac{\partial}{\partial x} p_k(x,y) = \frac{1-4x- 4q_k y}{4q_k^2y - q_k + 4q_kx}.\] Thus, by Proposition 5, \[\label{dydx:eq1} f(k,1) \geq \left. \frac{\partial}{\partial x} p_k(x,y) \right|_{(x,y) = \left(\frac{1}{k}, \frac{k-1}{k}\right)} = -1 - \frac{k}{3k^2- 2(k-1)^2 \sqrt{ \frac{2k}{k-1}} -4k}\tag{18}\] for all \(k \geq 4\). Finally, if \(p \geq r_+(H_k)\), then \(f(k,p) = -\frac{2(k-1)}{k-2}\) (attained by the point \(\left( \frac{1}{2},0 \right) \in \Phi(\mathop{\mathrm{STAB}}(H_k))\)).

We will prove our \(\mathop{\mathrm{LS}}_+\)-rank lower bound on \(H_k\) by showing that \(f(k,p) > -\frac{2(k-1)}{k-2}\) for some \(p = \Theta(k)\). To do so, we first show that the recursive structure of \(H_k\) allows us to establish \((a,b) \in \Phi(\mathop{\mathrm{LS}}_+^p(H_k))\) by verifying (among other conditions) the membership of two particular points in \(\Phi(\mathop{\mathrm{LS}}_+^{p-1}(H_{k-1}))\), which will help us relate the quantities \(f(k-1,p-1)\) and \(f(k,p)\). Next, we bound the difference \(f(k-1,p-1) - f(k,p)\) from above, which implies that it takes \(\mathop{\mathrm{LS}}_+\) many iterations to knock the slopes \(f(k,p)\) from that of \(\Phi(\mathop{\mathrm{FRAC}}(H_k))\) down to that of \(\Phi(\mathop{\mathrm{STAB}}(H_k))\).

First, here is a tool that will help us verify certificate matrices recursively.

Next, we apply Lemma 11 iteratively to find a lower bound for the \(\mathop{\mathrm{LS}}_+\)-rank of \(H_k\) as a function of \(k\). The following is an updated version of Lemma 11 that gets us a step closer to directly relating \(f(k,p)\) and \(f(k-1,p-1)\).

Next, we define four values corresponding to each \(k\) that will be important in our subsequent argument: \[\begin{align} u_1(k) & \mathrel{\vcenter{:}}=-\frac{2(k-1)}{k-2}, & u_2(k) & \mathrel{\vcenter{:}}=\frac{k-4- \sqrt{17k^2-48k+32}}{2(k-2)},\\ u_3(k) & \mathrel{\vcenter{:}}=\frac{4(k-1)(-3k+4-2\sqrt{k-1}) }{(k-2)(9k-10)}, & u_4(k) & \mathrel{\vcenter{:}}=-1 - \frac{k}{3k^2- 2(k-1)^2 \sqrt{ \frac{2k}{k-1}} -4k}. \end{align}\]

Notice that \(u_1(k) = f(k,p)\) for all \(p \geq r_+(H_k)\), and \(u_4(k)\) is the expression given in 18 , the lower bound for \(f(k,1)\) that follows from Proposition 5. Then we have the following.

Now we are ready to prove the following key lemma which bounds the difference between \(f(k-1,p-1)\) and \(f(k,p)\).

Applying Lemma 14 iteratively, we obtain the following.

Lemmas 14 and 15 provide a simple procedure of establishing \(\mathop{\mathrm{LS}}_+\)-rank lower bounds for \(H_k\).

Next, we prove a lemma that will help us obtain a lower bound for \(r_+(H_k)\) analytically.

We are finally ready to prove the main result of this section.

Since \(H_k\) has \(3k\) vertices, Theorem 6 (and the fact that \(r_+(H_3) =1\)) readily implies Theorem 1. In other words, we now know that for every \(\ell \in \mathbb{N}\), there exists a graph on no more than \(16\ell\) vertices that has \(\mathop{\mathrm{LS}}_+\)-rank \(\ell\).

5 Chvátal–Gomory rank of \(\mathop{\mathrm{STAB}}(H_k)\)↩︎

In this section we determine the degree of hardness of \(\mathop{\mathrm{STAB}}(H_k)\) relative to another well-studied cutting plane procedure that is due to Chvátal [33] with earlier ideas from Gomory [34]. Given a set \(P \subseteq [0,1]^n\), if \(a^{\top}x \leq \beta\) is a valid inequality of \(P\) and \(a \in \mathbb{Z}^n\), we say that \(a^{\top}x \leq \lfloor \beta\rfloor\) is a Chvátal–Gomory cut for \(P\). Then we define \(\mathop{\mathrm{CG}}(P)\), the Chvátal–Gomory closure of \(P\), to be the set of points that satisfy all Chvátal–Gomory cuts for \(P\). Note that \(\mathop{\mathrm{CG}}(P)\) is a closed convex set which contains all integral points in \(P\). Furthermore, given an integer \(p \geq 2\), we can recursively define \(\mathop{\mathrm{CG}}^p(P) \mathrel{\vcenter{:}}=\mathop{\mathrm{CG}}( \mathop{\mathrm{CG}}^{p-1}(P))\). Then given any valid linear inequality of \(P_I\), we can define its \(\mathop{\mathrm{CG}}\)-rank (relative to \(P\)) to be the smallest integer \(p\) for which the linear inequality is valid for \(\mathop{\mathrm{CG}}^p(P)\).

In Section 4, we proved that the inequality 4 has \(\mathop{\mathrm{LS}}_+\)-rank \(\Theta(|V(H_k)|)\). This implies that the inequality 3 also has \(\mathop{\mathrm{LS}}_+\)-rank \(\Theta(|V(H_k)|)\) (since it was shown in the proof of Lemma 5(ii) that 4 is a non-negative linear combination of 3 ). Here, we show that 3 has \(\mathop{\mathrm{CG}}\)-rank \(\Theta(\log(|V(H_k)|))\).

Before providing a proof of Theorem 7, first, we need a lemma about the valid inequalities of \(\mathop{\mathrm{STAB}}(H_k)\).

We will also need the following result.

We are now ready to prove Theorem 7.

Thus, we conclude that the facet 3 has \(\mathop{\mathrm{LS}}_+\)-rank \(\Theta(|V(H_k)|)\) and \(\mathop{\mathrm{CG}}\)-rank \(\Theta(\log(|V(H_k)|))\). We remark that the two results are incomparable in terms of computational complexity since it is generally \(\mathcal{NP}\)-hard to optimize over \(\mathop{\mathrm{CG}}^p(P)\) even for \(p = O(1)\). These rank bounds for \(H_k\) also provides an interesting contrast with the aforementioned example involving line graphs of odd cliques from [24], which have \(\mathop{\mathrm{LS}}_+\)-rank \(\Theta(\sqrt{|V(G)|})\) and \(\mathop{\mathrm{CG}}\)-rank \(\Theta(\log(|V(G)|))\). In the context of the matching problem, odd cliques have \(\mathop{\mathrm{CG}}\)-rank one with respect to the fractional matching polytope. This last claim follows from an observation of Chvátal [33].

6 Symmetric graphs with high \(\mathop{\mathrm{LS}}_+\)-ranks↩︎

So far we have established that there exists a family of graphs (e.g., \(\left\{H_k \, \, : \,\, k \geq 2\right\}\)) which have \(\mathop{\mathrm{LS}}_+\)-rank \(\Theta(|V(G)|)\). However, the previous best result in this context \(\Theta(\sqrt{|V(G)|})\) was achieved by a vertex-transitive family of graphs (line graphs of odd cliques). In this section, we show that there exists a family of vertex-transitive graphs which also have \(\mathop{\mathrm{LS}}_+\)-rank \(\Theta(|V(G)|)\).

6.1 The \(L_k\) construction↩︎

In this section, we look into a procedure that is capable of constructing highly symmetric graphs with high \(\mathop{\mathrm{LS}}_+\)-rank by virtue of containing \(H_k\) as an induced subgraph.

For example, let \(C_4\) be the \(4\)-cycle with \(V(C_4) \mathrel{\vcenter{:}}=\left\{0,1,2,3\right\}\) and \[E(C_4) \mathrel{\vcenter{:}}=\left\{ \left\{0,1\right\}, \left\{1,2\right\}, \left\{2,3\right\}, \left\{3,0\right\}\right\}.\] Figure 4 illustrates the graphs \(L_2(C_4)\) and \(L_3(C_4)\).

Moreover, notice that if we define \(P_2\) to be the graph which is a path of length \(2\), with \(V(P_2) \mathrel{\vcenter{:}}=\left\{0,1,2\right\}\) and \(E(P_2) \mathrel{\vcenter{:}}=\left\{ \left\{0,1\right\}, \left\{1,2\right\}\right\}\), then \(L_k(P_2) = H_k\) for every \(k \geq 2\). Thus, we obtain the following.

Since \(L_k(C_4)\) has \(4k\) vertices, Theorem 6 and Proposition 8 immediately imply the following.

Since \(\left\{ L_k(C_4) : k \geq 3\right\}\) is a family of vertex-transitive graphs, Theorem 9 can also be proved directly by utilizing versions of the techniques in Sections 3 and 4. The graphs \(L_k(C_4)\) are particularly noteworthy because \(C_4\) is the smallest vertex-transitive graph that contains \(P_2\) as an induced subgraph. In general, observe that if \(G\) is vertex-transitive, then so is \(L_k(G)\). Thus, we now know that there exists a family of vertex-transitive graphs \(G\) with \(r_+(G) = \Theta(|V(G)|)\).

6.2 Generalizing the \(L_k\) construction↩︎

Next, we study one possible generalization of the aforementioned \(L_k\) construction, and mention some interesting graphs it produces.

Thus, when \(G_2 = \overline{G_1}\) (the complement of \(G_1\)), then \(L_k(G_1, G_2)\) specializes to \(L_k(G_1)\). Next, given \(\ell \in \mathbb{N}\) and \(S \subseteq [\ell]\), let \(Q_{\ell, S}\) denote the graph whose vertices are the \(2^{\ell}\) binary strings of length \(\ell\), and two strings are joined by an edge if the number of positions they differ by is contained in \(S\). For example, \(Q_{\ell, \left\{1\right\}}\) gives the \(\ell\)-cube. Then we have the following.

The graph \(Q_{k, \left\{1,k\right\}}\) is known as the folded-cube graph, and Proposition 10 implies the following.

We remark that the Clebsch graph is also special in the following aspect. Given a vertex-transitive graph \(G\), we say that \(G\) is transitive under destruction if \(G \ominus i\) is also vertex-transitive for every \(i \in V(G)\). As mentioned above, destroying any vertex in the Clebsch graph results in the Petersen graph, and so the Clebsch graph is indeed transitive under destruction. On the other hand, even though \(L(G_1, G_2)\) is vertex-transitive whenever \(G_1, G_2\) are vertex-transitive, the Clebsch graph is the only example which is transitive under destruction we could find using the \(L_k\) construction. For instance, one can check that \(Q_{k, \left\{1,k\right\}} \ominus i\) is not a regular graph for any \(k \geq 5\). Also, observe that the Clebsch graph can indeed be obtained from the “regular” \(L_k\) construction defined in Definition 4, as \[Q_{4, \left\{1,4\right\}} = L_4( Q_{2, \left\{1\right\}}, Q_{2, \left\{2\right\}} ) = L_4( C_4, \overline{C_4}) = L_4(C_4).\] However, one can check that \(L_k(C_{\ell})\) is transitive under destruction if and only if \((k,\ell) = (4,4)\) (i.e., the Clebsch graph example), and that \(L_k(K_{\ell, \ell})\) is transitive under destruction if and only if \((k,\ell) = (4,2)\) (i.e., the Clebsch graph example again). It would be fascinating to see what other interesting graphs can result from the \(L_k\) construction.

7 Some Future Research Directions↩︎

In this section, we mention some follow-up questions to our work in this manuscript that could lead to interesting future research.

While we showed that \(r_+(H_k) \geq 0.19k\) asymptotically in Section 4, there is likely room for improvement for this bound. First, Lemma 11 is not sharp. In particular, the assumptions needed for \(Y(e_0-e_{1_0}), Y(e_0-e_{1_1}) \in \mathop{\mathrm{LS}}_+^{p-1}(H_k)\) are sufficient but not necessary. Using CVX, a package for specifying and solving convex programs [36], [37] with SeDuMi [38], we obtained that \(r_+(H_6) \geq 3\). However, there do not exist \(a,b,c,d\) that would satisfy the assumptions of Lemma 11 for \(k=6\).

Even so, using Lemma 15 and the approach demonstrated in Example 2, we found computationally that \(r_+(H_k) > 0.25k\) for all \(3 \leq k \leq 10000\). One reason for the gap between this computational bound and the analytical bound given in Theorem 6 is that the analytical bound only takes advantage of squeezing \(\ell_i\)’s over the interval \((u_1(k), u_2(k))\). Since we were able to show that \(h(k,\ell) = \Theta(\frac{1}{k})\) over this interval (Lemma 16), this enabled us to establish a \(\Theta(k)\) rank lower bound. Computationally, we see that we could get more \(\ell_i\)’s in over the interval \((u_2(k), u_3(k))\). However, over this interval, \(h(k, \ell)\) is an increasing function that goes from \(\frac{2}{k-2}\) at \(u_2(k)\) to \(\Theta\left(\frac{1}{\sqrt{k}}\right)\) at \(u_3(k)\). This means that simply bounding \(h(k,\ell)\) from above by \(h(k, u_3(k))\) would only add an additional factor of \(\Theta(\sqrt{k})\) in the rank lower bound. Thus, improving the constant factor in Theorem 6 would seem to require additional insights.

As for an upper bound on \(r_+(H_k)\), we know that \(r_+(H_4) = 2\), and \(r_+(H_{k+1})\leq r_+(H_k) + 1\) for all \(k\). This gives the obvious upper bound of \(r_+(H_k) \leq k-2\). It would be interesting to obtain sharper bounds or even nail down the exact \(\mathop{\mathrm{LS}}_+\)-rank of \(H_k\).

Theorem 3 raises the natural question: Are there graphs on \(3\ell\) vertices that have \(\mathop{\mathrm{LS}}_+\)-rank exactly \(\ell\)? Such \(\ell\)-minimal graphs have been found for \(\ell=2\) [16] and for \(\ell=3\) [18]. Thus, results from [16], [18] show that the answer is “yes” for \(\ell = 1,2,3\). In [39], we construct the first \(4\)-minimal graph which shows that the answer is also “yes” for \(\ell = 4\). Does the pattern continue for larger \(\ell\)? And more importantly, how can we verify the \(\mathop{\mathrm{LS}}_+\)-rank of these graphs analytically or algebraically, as opposed to primarily relying on specific numerical certificates?

After \(\mathop{\mathrm{LS}}_+\), many stronger semidefinite lift-and-project operators (such as \(\mathop{\mathrm{Las}}\) [4],
\(\mathop{\mathrm{BZ}}_+\) [5], \(\Theta_p\) [40], and \(\mathop{\mathrm{SA}}_+\) [6]) have been proposed. While these stronger operators are capable of producing tighter relaxations than \(\mathop{\mathrm{LS}}_+\), these SDP relaxations can also be more computationally challenging to solve. For instance, while the \(\mathop{\mathrm{LS}}_+^p\)-relaxation of a set \(P \subseteq [0,1]^n\) involves \(O(n^p)\) PSD constraints of order \(O(n)\), the operators \(\mathop{\mathrm{Las}}^p, \mathop{\mathrm{BZ}}_+^p\) and \(\mathop{\mathrm{SA}}_+^p\) all impose one (or more) PSD constraint of order \(\Omega(n^p)\) in their formulations. It would be interesting to determine the corresponding properties of graphs which are minimal with respect to these stronger lift-and-project operators.

Declarations↩︎

Conflict of interest: The authors declare that they have no conflict of interest.

References↩︎