betaFeedback

WorksMathematics

Optimal solution ranks in the Max-Cut semidefinite relaxation

Abstract

For every nn and rr with 1≤r1\le r and (r+12)≤n\binom{r+1}{2}\le n, we construct a connected unweighted graph on nn vertices whose Max-Cut semidefinite relaxation has a unique optimal solution of rank rr. The main examples are the Kneser graphs K(m,2)K(m,2), whose unique optima have rank m−1m-1. A six-vertex wheel supplies rank three, and attaching pendant vertices preserves both rank and uniqueness. For dense random graphs, we also prove a polynomial lower bound on the optimal rank.

Introduction

The semidefinite relaxation of Max-Cut replaces the two signs defining a cut by unit vectors. This raises a natural question: how many dimensions can a graph force an optimal representation to use? We show that connected unweighted graphs can require every dimension allowed by the general rank bound, even with a unique optimal Gram matrix.

Let GG be a graph on the vertex set [n][n] with symmetric nonnegative weight matrix A=(aij)A=(a_{ij}), zero diagonal, and Laplacian L=Diag(A1)−AL=\mathop{\mathrm{Diag}}(A\mathbf{1})-A. We denote the Goemans–Williamson relaxation [1] by SDP(G)\mathrm{SDP}(G) and its optimal value by sdp(G)\mathrm{sdp}(G):

sdp(G)=max⁡{14⟨L,X⟩:X∈En},En={X∈Rn×n:X⪰0, diagX=1},\begin{aligned} \mathrm{sdp}(G)&=\max\Bigl\{\tfrac14\langle L,X\rangle:X\in\mathcal{E}_n\Bigr\},\\ \mathcal{E}_n&=\{X\in\mathbb{R}^{n\times n}:X\succeq0,\ \mathop{\mathrm{diag}}X=\mathbf{1}\}, \end{aligned}

where En\mathcal{E}_n is the elliptope. A point of En\mathcal{E}_n is the Gram matrix of a family of unit vectors, and its rank is the dimension of the space they span. Rank one is the integral case: X∈EnX\in\mathcal{E}_n has rank one exactly when X=xx⊤X=xx^\top with x∈{±1}nx\in\{\pm1\}^n, a cut. Let F(G)F(G) be the set of optimal solutions of SDP(G)\mathrm{SDP}(G), which is a face of En\mathcal{E}_n, and define the optimal rank

ρ(G)=min⁡{rankX:X∈F(G)}.\rho(G)=\min\{\mathop{\mathrm{rank}}X:X\in F(G)\}.

Thus ρ(G)\rho(G) measures the dimension needed by the best optimal representation, and ρ(G)=1\rho(G)=1 exactly when the relaxation is exact. Bhardwaj [2] shows that recognising exactness is NP-hard even for unweighted graphs. Optimal ranks have been studied from several angles [3, 4], and low-rank formulations also underlie heuristics for Max-Cut [5]. Here we ask how large ρ(G)\rho(G) can be as a function of the number of vertices.

An upper bound on ρ(G)\rho(G) comes from general theory. F(G)F(G) is a nonempty compact face of En\mathcal{E}_n, so it has an extreme point, which is an extreme point of En\mathcal{E}_n; and by the theorem of Barvinok [6] and Pataki [7], an extreme point of a spectrahedron defined by nn linear equations has rank rr with (r+12)≤n\binom{r+1}2\le n. Thus an optimal solution of SDP(G)\mathrm{SDP}(G) attains a rank satisfying this bound, and hence

ρ(G)≤rBP(n):=max⁡{r:(r+12)≤n}=⌊8n+1−12⌋.\begin{equation} \rho(G)\le r_{\mathrm{BP}}(n):=\max\Bigl\{r:\tbinom{r+1}2\le n\Bigr\} =\Bigl\lfloor\tfrac{\sqrt{8n+1}-1}2\Bigr\rfloor . \tag*{(1)} \end{equation}

The question we answer is whether equality in (1) is attained for every nn, even by connected unweighted graphs.

The distinction between arbitrary objectives and graph objectives is essential here. Extreme points of En\mathcal{E}_n exist at every rank permitted by (1) [9, 10]. Since every face of a spectrahedron is exposed [11], each is the unique optimum of a suitable linear functional. The same sharp rank bound appears in the extreme Gram dimension of Eisenberg-Nagy, Laurent and Varvitsiotis [13], where the objective coefficients on a fixed graph may be arbitrary real numbers. For an unweighted graph, the off-diagonal entries of its Laplacian belong to {0,−1}\{0,-1\}. Since diagonal terms contribute a constant on En\mathcal{E}_n, it is this restriction on the off-diagonal coefficients that distinguishes our objectives. Our result realizes every admissible rank under this restriction, while also requiring connectivity and uniqueness.

The main construction uses Kneser graphs, familiar from graph coloring and Lovász’s work [21]. The graph K(m,2)K(m,2) has the two-element subsets of [m][m] as vertices, with two vertices adjacent exactly when the corresponding subsets are disjoint.

Theorem 1.1. Let m≥5m\ge5 and n=(m2)n=\binom m2. Then the relaxation SDP(K(m,2))\mathrm{SDP}(K(m,2)) has a unique optimal solution X∗X^\ast, given by Xef∗=m ∣e∩f∣−42(m−2)(e,f∈([m]2)),X^\ast_{ef}=\frac{m\,|e\cap f|-4}{2(m-2)}\qquad(e,f\in\tbinom{[m]}2), and rankX∗=m−1=rBP(n)\mathop{\mathrm{rank}}X^\ast=m-1=r_{\mathrm{BP}}(n). In particular ρ(K(m,2))=rBP(n)\rho(K(m,2))=r_{\mathrm{BP}}(n).

Explicitly, X∗X^\ast is the Gram matrix obtained by assigning to the pair {a,b}\{a,b\} the unit vector proportional to the centred indicator vector ea+eb−2m1e_a+e_b-\frac2m\mathbf{1}, where eae_a is the aa-th standard basis vector. Disjoint pairs have inner product −2m−2-\frac2{m-2} and distinct overlapping pairs have inner product m−42(m−2)\frac{m-4}{2(m-2)}. For m=5m=5 this is the Petersen graph, whose unique optimal solution has rank 4=rBP(10)4=r_{\mathrm{BP}}(10).

The Kneser family skips rank three, because K(4,2)K(4,2) is a perfect matching. The wheel formed by joining a hub to all five vertices of a cycle supplies the missing rank, already on six vertices (Theorem 4.1). To reach any larger order, we attach pendant vertices: each new leaf receives the negative of its neighbour’s vector, preserving both the rank and the uniqueness of the optimum. These observations give a complete realization result.

Theorem 1.2. For every n≥1n\ge1 and every integer 1≤r≤rBP(n)1\le r\le r_{\mathrm{BP}}(n), there is a connected unweighted graph on nn vertices whose Max-Cut semidefinite relaxation has a unique optimal solution of rank rr.

Corollary 1.3. For every n≥1n\ge1, the maximum of ρ(G)\rho(G) over connected unweighted graphs on nn vertices equals rBP(n)r_{\mathrm{BP}}(n). The same maximum is obtained over all unweighted graphs, or over graphs with nonnegative real edge weights.

Thus every rank permitted by the general theory occurs as the rank of a unique optimum, even when the graph is required to be connected and all its edge weights are one.

The constructions also suggest a question about random graphs: must the dimension grow when the edges are chosen independently? For G∼G(n,12)G\sim G(n,\frac12), where each pair is an edge independently with probability 1/21/2, we prove

ρ(G)≥c(n(log⁡n)3)1/7\rho(G)\ge c\left(\frac{n}{(\log n)^3}\right)^{1/7}

with probability tending to one, for an absolute constant c>0c>0 (Theorem 6.1). Thus, with probability tending to one, every optimal representation of an Erdős–Rényi graph with edge probability 1/21/2 requires polynomially many dimensions. The proof compares the best objective value at bounded rank with a feasible matrix concentrated near the upper spectral edge. We also formulate a conjecture on the growth rate, motivated by the Gaussian spin-glass literature.

The proofs of the realization results follow a common pattern: first locate the range of every optimum, then use the diagonal equations to determine the Gram matrix. For the Kneser graphs, the classical Laplacian eigenvalue bound [20, 8] confines this range to the top Laplacian eigenspace. Van Dam and Sotirov [14] show that the spectral bound is attained for all walk-regular graphs, a class containing the Kneser graphs. Attaining the value alone does not determine the minimum optimal rank. We prove that the diagonal equations are independent on the relevant space of symmetric matrices, so the entire optimal face consists of one point. This is an application of the classical extremality criterion for correlation matrices [9, 10].

The centred-incidence representation is also central to the work of Godsil, Roberson, Rooney, Šámal and Varvitsiotis [12], who prove universal completability and unique vector colorability of Kneser graphs. Those problems prescribe or bound individual edge correlations; Max-Cut optimizes their sum. The difference is substantive: K4K_4 has a unique optimal vector coloring, represented by a regular tetrahedron, while its Max-Cut relaxation has both this rank-three optimum and rank-one optima coming from balanced cuts. For K(m,2)K(m,2), we establish uniqueness using the diagonal equations alone within the least adjacency eigenspace.

The wheel uses the same principle with the kernel of a dual slack matrix in place of the top Laplacian eigenspace. Finally, attaching a leaf preserves the optimal rank and uniqueness. This extension is a special case of the vertex-sum constructions in [3]. We collect the necessary facts in § 2, prove the Kneser and wheel results in § 3 and § 4, and assemble the construction proving Theorem 1.2 in § 5. The final section gives a polynomial lower bound for random graphs and proposes a conjecture on the growth of their optimal rank.

The optimal face

We begin with the geometry shared by the two constructions. The dual of the relaxation is min⁡{∑iyi:Diag(y)−14L⪰0}\min\{\sum_iy_i:\mathop{\mathrm{Diag}}(y)-\frac14L\succeq0\}. The identity matrix is strictly feasible for the primal problem, so strong duality holds and the dual optimum is attained. If SS is an optimal dual slack, complementary slackness confines every optimum XX to rangeX⊆ker⁡S\mathop{\mathrm{range}}X\subseteq\ker S. A scalar diagonal choice gives the familiar eigenvalue bound.

Lemma 2.1 (Eigenvalue bound [20, 8]). Let λ=λmax⁡(L)\lambda=\lambda_{\max}(L) and let EE be its eigenspace. For every X∈EnX\in\mathcal{E}_n we have ⟨L,X⟩≤nλ\langle L,X\rangle\le n\lambda, with equality if and only if rangeX⊆E\mathop{\mathrm{range}}X\subseteq E. If some X∈EnX\in\mathcal{E}_n satisfies rangeX⊆E\mathop{\mathrm{range}}X\subseteq E, then sdp(G)=n4λ\mathrm{sdp}(G)=\frac n4\lambda and F(G)={X∈En:rangeX⊆E}.F(G)=\{X\in\mathcal{E}_n:\mathop{\mathrm{range}}X\subseteq E\}.

Proof. λI−L⪰0\lambda I-L\succeq0 and X⪰0X\succeq0 give ⟨λI−L,X⟩≥0\langle\lambda I-L,X\rangle\ge0, that is ⟨L,X⟩≤λtr⁡X=nλ\langle L,X\rangle\le\lambda\operatorname{tr}X=n\lambda. Equality holds if and only if ⟨λI−L,X⟩=0\langle\lambda I-L,X\rangle=0, which for two positive semidefinite matrices means (λI−L)X=0(\lambda I-L)X=0, that is rangeX⊆E\mathop{\mathrm{range}}X\subseteq E. ◻

Lemma 2.2 (Parametrising the face). Let E⊆RnE\subseteq\mathbb{R}^n be a subspace of dimension gg, let U∈Rn×gU\in\mathbb{R}^{n\times g} have columns forming a basis of EE, and let ui⊤u_i^\top be the ii-th row of UU. Then the map M↦UMU⊤M\mapsto UMU^\top is a rank-preserving bijection from M={M∈Sym(Rg):M⪰0, ui⊤Mui=1 (i∈[n])}\mathcal M=\{M\in\mathop{\mathrm{Sym}}(\mathbb{R}^g):M\succeq0,\ u_i^\top Mu_i=1\ (i\in[n])\} onto {X∈En:rangeX⊆E}\{X\in\mathcal{E}_n:\mathop{\mathrm{range}}X\subseteq E\}.

Proof. A symmetric XX has rangeX⊆rangeU\mathop{\mathrm{range}}X\subseteq\mathop{\mathrm{range}}U if and only if X=UMU⊤X=UMU^\top for a symmetric MM, which is unique because UU has full column rank; for the same reason X⪰0X\succeq0 if and only if M⪰0M\succeq0, and rankX=rankM\mathop{\mathrm{rank}}X=\mathop{\mathrm{rank}}M. The condition Xii=1X_{ii}=1 reads ui⊤Mui=1u_i^\top Mu_i=1. ◻

In these coordinates, uniqueness becomes a question about linear equations: do the conditions ui⊤Mui=1u_i^\top Mu_i=1 determine MM? The following form of the correlation-matrix extremality criterion [9, 10] will be useful.

Lemma 2.3 (Spanning forces a single point). In the setting of Lemma 2.2, suppose that the rank-one matrices uiui⊤u_iu_i^\top, i∈[n]i\in[n], span Sym(Rg)\mathop{\mathrm{Sym}}(\mathbb{R}^g), and that M\mathcal M contains a positive definite matrix M0M_0. Then M={M0}\mathcal M=\{M_0\}. If moreover EE is the top eigenspace of LL, then F(G)={UM0U⊤}F(G)=\{UM_0U^\top\} and ρ(G)=g\rho(G)=g.

Proof. The equations ⟨uiui⊤,M⟩=1\langle u_iu_i^\top,M\rangle=1 are linear in MM, and if the coefficient matrices span Sym(Rg)\mathop{\mathrm{Sym}}(\mathbb{R}^g) they have at most one solution. The second statement follows from Lemmas 2.1 and 2.2. ◻

The converse holds whenever M0≻0M_0\succ0: a nonzero symmetric matrix orthogonal to every uiui⊤u_iu_i^\top gives sufficiently small feasible perturbations of both signs. Thus uniqueness is equivalent to the absence of such a perturbation. In particular, n≥(g+12)n\ge\binom{g+1}{2} is necessary. Our constructions achieve equality before any pendant vertices are added.

We will use two small graphs to start the construction. The graph K1K_1 has the unique feasible matrix (1)(1), of rank one. For the triangle K3K_3, the objective of a Gram matrix of unit vectors v1,v2,v3v_1,v_2,v_3 is

14(9−∥v1+v2+v3∥2).\frac14\left(9-\|v_1+v_2+v_3\|^2\right).

Three unit vectors summing to zero attain the maximum. Taking inner products with each vector shows that all three off-diagonal entries of their Gram matrix are −1/2-1/2. Hence the optimum for K3K_3 is unique and has rank two.

The following extension lets us add vertices without changing the optimal rank.

Lemma 2.4. Let G′G' be obtained from a graph GG by adding a new vertex ℓ\ell and a single edge vℓv\ell of weight one, where v∈V(G)v\in V(G). Then sdp(G′)=sdp(G)+1,ρ(G′)=ρ(G).\mathrm{sdp}(G')=\mathrm{sdp}(G)+1,\qquad \rho(G')=\rho(G). If the optimal solution for GG is unique, then so is the optimal solution for G′G'.

Proof. For any unit-vector representation of G′G', the old edges contribute at most sdp(G)\mathrm{sdp}(G) and the new edge contributes 14∥vℓ−vv∥2≤1\frac14\|v_\ell-v_v\|^2\le1. Conversely, an optimal representation of GG extends by setting vℓ=−vvv_\ell=-v_v, attaining sdp(G)+1\mathrm{sdp}(G)+1 without increasing the rank. Every optimum for G′G' must therefore restrict to an optimum for GG, which proves the equality of optimal ranks. Moreover, equality on the new edge forces vℓ=−vvv_\ell=-v_v. All correlations involving the new vertex are consequently fixed by the old Gram matrix, proving the assertion about uniqueness. ◻

The Kneser graphs

We now construct the optimal representation and show that it is forced by the diagonal equations. Fix m≥5m\ge5, let G=K(m,2)G=K(m,2) and n=(m2)n=\binom m2. We write vertices as pairs e={a,b}e=\{a,b\}, and AA for the adjacency matrix. The graph is regular of degree d=(m−22)d=\binom{m-2}2, so L=dI−AL=dI-A and the top Laplacian eigenspace is the least adjacency eigenspace.

Let N∈Rn×mN\in\mathbb{R}^{n\times m} be the incidence matrix of pairs versus points, Ne,a=1N_{e,a}=1 if a∈ea\in e. Then N⊤N=(m−2)I+JN^\top N=(m-2)I+J, where JJ is the all-ones matrix, because a point lies in m−1m-1 pairs and two distinct points lie in exactly one. Put

E={Nf:f∈Rm, 1⊤f=0}.E=\{Nf:f\in\mathbb{R}^m,\ \mathbf{1}^\top f=0\}.

Since N⊤N=(m−2)IN^\top N=(m-2)I on 1⊥\mathbf{1}^\perp, the map f↦Nff\mapsto Nf is injective there and dim⁡E=m−1\dim E=m-1.

Lemma 3.1. The Laplacian LL of K(m,2)K(m,2) has eigenvalue 00 on span(1)\mathop{\mathrm{span}}(\mathbf{1}), eigenvalue d+m−3d+m-3 on EE, and eigenvalue d−1d-1 on the orthogonal complement of span(1)⊕E\mathop{\mathrm{span}}(\mathbf{1})\oplus E. In particular λmax⁡(L)=d+m−3\lambda_{\max}(L)=d+m-3 and its eigenspace is exactly EE.

Proof. For x=Nfx=Nf with 1⊤f=0\mathbf{1}^\top f=0 we have xab=fa+fbx_{ab}=f_a+f_b, and

(Ax)ab=∑{c,c′}∩{a,b}=∅(fc+fc′)=(m−3)∑c∉{a,b}fc=−(m−3)(fa+fb),\begin{aligned} (Ax)_{ab}&=\sum_{\{c,c'\}\cap\{a,b\}=\varnothing}(f_c+f_{c'})\\ &=(m-3)\sum_{c\notin\{a,b\}}f_c=-(m-3)(f_a+f_b), \end{aligned}

because each c∉{a,b}c\notin\{a,b\} lies in m−3m-3 pairs disjoint from {a,b}\{a,b\}. So Ax=−(m−3)xAx=-(m-3)x on EE. The space span(1)⊕E\mathop{\mathrm{span}}(\mathbf{1})\oplus E is the range of NN, since 1=N(121)\mathbf{1}=N(\frac12\mathbf{1}); its orthogonal complement is ker⁡N⊤={x:∑b≠axab=0 for all a}\ker N^\top=\{x:\sum_{b\ne a}x_{ab}=0\text{ for all }a\}. For such xx also ∑exe=12∑a∑b≠axab=0\sum_ex_e=\frac12\sum_a\sum_{b\ne a}x_{ab}=0, so

(Ax)ab=∑exe−∑b′≠axab′−∑a′≠bxa′b+xab=xab,(Ax)_{ab}=\sum_ex_e-\sum_{b'\ne a}x_{ab'}-\sum_{a'\ne b}x_{a'b}+x_{ab}=x_{ab},

the last term correcting for the pair {a,b}\{a,b\}, which is subtracted twice. Finally A1=d1A\mathbf{1}=d\mathbf{1}. Hence L=dI−AL=dI-A has the stated eigenvalues, and d+m−3>d−1d+m-3>d-1. ◻

Proof of Theorem 1.1. Let π=I−1mJ\pi=I-\frac1mJ be the orthogonal projector of Rm\mathbb{R}^m onto 1⊥\mathbf{1}^\perp. By Lemma 3.1 and the identity N⊤N=(m−2)IN^\top N=(m-2)I on 1⊥\mathbf{1}^\perp, the orthogonal projector onto EE is PE=1m−2NπN⊤P_E=\frac1{m-2}N\pi N^\top, with entries

(PE)ef=1m−2(1e−2m1) ⁣⊤(1f−2m1)=∣e∩f∣−4mm−2,(P_E)_{ef}=\frac{1}{m-2}\bigl(\mathbf{1}_e-\tfrac2m\mathbf{1}\bigr)^{\!\top} \bigl(\mathbf{1}_f-\tfrac2m\mathbf{1}\bigr)=\frac{|e\cap f|-\frac4m}{m-2},

where 1e=ea+eb\mathbf{1}_e=e_a+e_b is the indicator vector of e={a,b}e=\{a,b\}. The matrix X∗=nm−1PE=m2PEX^\ast=\frac{n}{m-1}P_E=\frac m{2}P_E has entries m∣e∩f∣−42(m−2)\frac{m|e\cap f|-4}{2(m-2)}; its diagonal entries (∣e∩f∣=2|e\cap f|=2) are 11, it is positive semidefinite, and its range is EE. By Lemma 2.1, X∗X^\ast is optimal and F(G)={X∈En:rangeX⊆E}F(G)=\{X\in\mathcal{E}_n:\mathop{\mathrm{range}}X\subseteq E\}.

It remains to show that every optimum equals X∗X^\ast. By Lemma 2.3, it suffices to prove that the matrices (π1e)(π1e)⊤(\pi\mathbf{1}_e)(\pi\mathbf{1}_e)^\top span the symmetric operators on 1⊥\mathbf{1}^\perp. Indeed, the rows of NN restricted to this subspace are represented by π1e\pi\mathbf{1}_e, and the positive definite scalar operator M0=m2(m−2)IM_0=\frac{m}{2(m-2)}I gives X∗X^\ast.

Suppose a symmetric operator MM on 1⊥\mathbf{1}^\perp is orthogonal to all these rank-one matrices. Extend it to a symmetric matrix M~\widetilde M on Rm\mathbb{R}^m by setting M~1=0\widetilde M\mathbf{1}=0. Orthogonality then reads

M~aa+2M~ab+M~bb=0(a≠b).\widetilde M_{aa}+2\widetilde M_{ab}+\widetilde M_{bb}=0\qquad(a\ne b).

Let δa=M~aa\delta_a=\widetilde M_{aa} and T=∑aδaT=\sum_a\delta_a. Summing over b≠ab\ne a and using ∑b≠aM~ab=−δa\sum_{b\ne a}\widetilde M_{ab}=-\delta_a gives (m−1)δa−2δa+(T−δa)=0(m-1)\delta_a-2\delta_a+(T-\delta_a)=0, that is (m−4)δa+T=0(m-4)\delta_a+T=0 for every aa. Summing over aa gives (2m−4)T=0(2m-4)T=0, so T=0T=0, and then δa=0\delta_a=0 for every aa because m≠4m\ne4. The displayed relation now gives M~ab=0\widetilde M_{ab}=0 for a≠ba\ne b, so M=0M=0. By Lemma 2.3, F(G)={X∗}F(G)=\{X^\ast\} and ρ(G)=m−1\rho(G)=m-1.

Finally 8n+1=4m2−4m+1=(2m−1)28n+1=4m^2-4m+1=(2m-1)^2, so rBP(n)=m−1r_{\mathrm{BP}}(n)=m-1 by (1). ◻

Remark 3.2. An alternative proof of the required nonsingularity follows from the entrywise square of X∗X^\ast. The Kneser construction uses exactly (m2)=dim⁡Sym(1⊥)\binom{m}{2}=\dim\mathop{\mathrm{Sym}}(\mathbf{1}^\perp) vectors, so the diagonal system is square. Indeed, (Xef∗)2=⟨ueue⊤,ufuf⊤⟩(X^\ast_{ef})^2=\langle u_eu_e^\top,u_fu_f^\top\rangle for its unit Gram vectors ueu_e. Thus X∗∘X∗X^\ast\circ X^\ast is the Gram matrix of the coefficient matrices in the diagonal equations. With B=J−I−AB=J-I-A, the adjacency matrix of the triangular graph, it equals I+(m−4)24(m−2)2B+4(m−2)2AI+\frac{(m-4)^2}{4(m-2)^2}B+\frac{4}{(m-2)^2}A. On the three subspaces in Lemma 3.1, its eigenvalues are, respectively,

m2,m(m−4)24(m−2)2,m22(m−2)2.\frac m2,\qquad \frac{m(m-4)^2}{4(m-2)^2},\qquad \frac{m^2}{2(m-2)^2}.

All are positive for m≥5m\ge5. At m=4m=4 the middle eigenvalue vanishes: K(4,2)K(4,2) is a perfect matching and has ρ=1\rho=1, explaining the missing rank in the Kneser family.

Remark 3.3. The optimal value is sdp(K(m,2))=n4(d+m−3)=m2(m−1)(m−3)16\mathrm{sdp}(K(m,2))=\frac n4(d+m-3)=\frac{m^2(m-1)(m-3)}{16}.

Rank three

The Kneser family leaves one rank to account for. The triangle supplies rank two, but K(4,2)K(4,2) is a perfect matching and has an integral optimum. For rank three we turn to a familiar graph: the wheel consisting of a five-cycle and a hub adjacent to every cycle vertex. It has six vertices, the smallest order allowed by the Barvinok–Pataki bound for rank three.

Theorem 4.1. Let HH be the unweighted graph obtained by joining a new vertex to every vertex of C5C_5. Then the Max-Cut semidefinite relaxation of HH has a unique optimal solution of rank three and optimal value (23+4φ)/4(23+4\varphi)/4, where φ=(1+5)/2\varphi=(1+\sqrt5)/2.

Proof. Write hh for the hub, label the cycle vertices 0,…,40,\ldots,4 in cyclic order, and put

φ=1+52,b=φ+2,a=b−1,s=1−a2.\varphi=\frac{1+\sqrt5}{2},\quad b=\varphi+2,\quad a=b^{-1},\quad s=\sqrt{1-a^2}.

Assign the hub the unit vector uh=(0,0,1)u_h=(0,0,1) and assign the cycle vertices

uj=(scos⁡θj,ssin⁡θj,−a),θj=4πj5(0≤j≤4).u_j=(s\cos\theta_j,s\sin\theta_j,-a),\quad \theta_j=\frac{4\pi j}{5}\quad(0\le j\le4).

The five cycle vectors lie on a circle below the hub vector, with consecutive cycle vertices separated by an angle of 4π/54\pi/5 around that circle. To see the choice of height, replace aa by t∈[0,1]t\in[0,1] in this representation. The sum of the edge inner products is 52((φ+2)t2−2t−φ)\frac52((\varphi+2)t^2-2t-\varphi), minimized at t=at=a. We next certify that this representation is optimal among all feasible Gram matrices. Let U∈R6×3U\in\mathbb{R}^{6\times3} have the displayed rows. Its columns are independent, so X∗=UU⊤X^*=UU^\top is feasible and has rank three.

Let ACA_C be the adjacency matrix of C5C_5 and consider, in the vertex order h,0,…,4h,0,\ldots,4, the matrix

S=(5/b1⊤1AC+φI).S=\begin{pmatrix} 5/b&\mathbf{1}^\top\\ \mathbf{1}&A_C+\varphi I \end{pmatrix}.

The eigenvalues of ACA_C are 2cos⁡(2πk/5)2\cos(2\pi k/5), 0≤k≤40\le k\le4. On the nonconstant cycle eigenspaces, SS therefore has eigenvalues 00 and 5\sqrt5, each twice. On the remaining subspace, with the constant cycle vector normalized to unit length, it is represented by

(5/b55b).\begin{pmatrix}5/b&\sqrt5\\\sqrt5&b\end{pmatrix}.

This matrix has determinant zero and trace 5/b+b=55/b+b=5. Thus S⪰0S\succeq0 and dim⁡ker⁡S=3\dim\ker S=3.

The identity 2cos⁡(4π/5)=−φ2\cos(4\pi/5)=-\varphi shows that SS annihilates the first two columns of UU. For the third column, the hub equation is 5/b−5a=05/b-5a=0 and each cycle equation is 1−(2+φ)a=01-(2+\varphi)a=0. Hence SU=0SU=0 and ker⁡S=rangeU\ker S=\mathop{\mathrm{range}}U.

Let AHA_H be the adjacency matrix of HH. Since SS and AHA_H have the same off-diagonal entries, every X∈E6X\in\mathcal{E}_6 satisfies

⟨AH,X⟩=⟨S,X⟩−5/b−5φ≥−5/b−5φ.\langle A_H,X\rangle=\langle S,X\rangle-5/b-5\varphi\ge-5/b-5\varphi.

Equality holds for X∗X^* because SU=0SU=0. Minimizing ⟨AH,X⟩\langle A_H,X\rangle is equivalent to maximizing the Max-Cut objective, so X∗X^* is optimal. For any optimum XX, equality gives SX=0SX=0, and therefore rangeX⊆ker⁡S=rangeU\mathop{\mathrm{range}}X\subseteq\ker S=\mathop{\mathrm{range}}U.

The graph has ten edges, so the optimal value is 5+(5/b+5φ)/4=(23+4φ)/4≈7.3685+(5/b+5\varphi)/4=(23+4\varphi)/4\approx7.368. Its maximum cut has value 77: if kk cycle vertices lie opposite the hub, at most k+2min⁡{k,5−k}≤7k+2\min\{k,5-k\}\le7 edges cross the cut, and equality is attained by placing cycle vertices 0,2,40,2,4 opposite the hub.

It remains to show that the diagonal equations allow no other optimum. By Lemma 2.2, write X=UMU⊤X=UMU^\top with M∈Sym(R3)M\in\mathop{\mathrm{Sym}}(\mathbb{R}^3) positive semidefinite. The hub equation gives M33=1M_{33}=1. The equation uj⊤Muj=1u_j^\top Mu_j=1 at each cycle vertex becomes

0=s22(M11+M22−2)+s22(M11−M22)cos⁡(2θj)+s2M12sin⁡(2θj)−2asM13cos⁡θj−2asM23sin⁡θj.\begin{split} 0={}&\frac{s^2}{2}(M_{11}+M_{22}-2)\\ &+\frac{s^2}{2}(M_{11}-M_{22})\cos(2\theta_j) +s^2M_{12}\sin(2\theta_j)\\ &-2asM_{13}\cos\theta_j-2asM_{23}\sin\theta_j. \end{split}

The five functions 1,cos⁡θ,sin⁡θ,cos⁡2θ,sin⁡2θ1,\cos\theta,\sin\theta,\cos2\theta,\sin2\theta are linearly independent when evaluated at the five angles θj\theta_j. Indeed, multiplying a vanishing linear combination by e2iθe^{2i\theta} gives a polynomial of degree at most four with five distinct roots eiθje^{i\theta_j}. All five coefficients in the displayed equation must therefore vanish. Since a,s>0a,s>0, this gives M12=M13=M23=0M_{12}=M_{13}=M_{23}=0 and M11=M22=1M_{11}=M_{22}=1. Hence M=IM=I, proving uniqueness. ◻

Remark 4.2. The wheel illustrates why it is useful to allow a general dual slack matrix. Its largest Laplacian eigenvalue is 66 and is simple: an eigenvector has entry −5-5 at the hub and entry 11 at every cycle vertex. No Gram matrix with unit diagonal can have its range in this eigenspace. The matrix SS in the proof instead uses a diagonal shift of the adjacency matrix tailored to the hub and the cycle vertices.

Realizing every rank

Each rank now has a connected unweighted example on the smallest possible number of vertices. Attaching leaves increases the order one vertex at a time while preserving the unique optimum and its rank.

Proof of Theorem 1.2. Let 1≤r≤rBP(n)1\le r\le r_{\mathrm{BP}}(n), so (r+12)≤n\binom{r+1}{2}\le n. For r=1r=1 start with K1K_1, and for r=2r=2 start with K3K_3; as observed in § 2, their optima are unique and have ranks one and two, respectively. For r=3r=3 use the six-vertex wheel of Theorem 4.1. For r≥4r\ge4 use K(r+1,2)K(r+1,2), whose unique optimum has rank rr by Theorem 1.1.

These starting graphs are connected. For the Kneser graph, disjoint pairs are adjacent, while two distinct intersecting pairs have a common neighbour: since r+1≥5r+1\ge5, a two-element set can be chosen outside their union. Each starting graph has (r+12)\binom{r+1}{2} vertices. Attach n−(r+12)n-\binom{r+1}{2} pendant vertices and apply Lemma 2.4 repeatedly. The resulting graph is connected and unweighted, and its optimum is unique and still has rank rr. ◻

Proof of Corollary 1.3. The upper bound (1) applies to every graph under consideration. Theorem 1.2 with r=rBP(n)r=r_{\mathrm{BP}}(n) attains it in the smallest of the three classes, the connected unweighted graphs. ◻

Can the bound ρ(G)=rBP(n)\rho(G)=r_{\mathrm{BP}}(n) be attained with a unique optimum by a 22-connected graph at every order n≥3n\ge3, or by a connected regular graph at every sufficiently large order?

Random graphs

The constructions above attain the largest possible optimal rank. We now ask what happens when the edges are chosen independently. The next result shows that a dense random graph forces every optimal representation to use a polynomially growing number of dimensions.

Theorem 6.1. There is an absolute constant c>0c>0 such that, for G∼G(n,12)G\sim G(n,\frac12), P ⁣{ρ(G)≥c(n(log⁡n)3)1/7}⟶1.\mathbb P\!\left\{\rho(G)\ge c\left(\frac{n}{(\log n)^3}\right)^{1/7}\right\}\longrightarrow1.

The idea is to separate objective values: if every representation in at most rr dimensions performs worse than one feasible matrix, then every optimum has rank greater than rr. After centering and scaling the adjacency matrix, we compare both values with the spectral edge 22. A Gaussian comparison produces a loss of order 1/r1/r at bounded rank, and a spectral construction comes closer to 22. The main work is to keep the errors small enough as rr grows.

Proof of Theorem 6.1. Let AA be the adjacency matrix and put

W=J−I−2An,Fn(X)=⟨W,X⟩−1⊤X1n.W=\frac{J-I-2A}{\sqrt n},\qquad F_n(X)=\langle W,X\rangle-\frac{\mathbf{1}^\top X\mathbf{1}}{\sqrt n}.

Centering removes the mean edge density: the off-diagonal entries of WW are independent symmetric signs divided by n\sqrt n, and Wii=0W_{ii}=0. The term involving 1\mathbf{1} in FnF_n accounts for the removed mean. The identity

⟨A,X⟩=12(1⊤X1−n−n⟨W,X⟩)\langle A,X\rangle=\tfrac12\bigl(\mathbf{1}^\top X\mathbf{1}-n-\sqrt n\langle W,X\rangle\bigr)

shows that maximizing FnF_n on En\mathcal{E}_n is equivalent to the Max-Cut relaxation. Define

Mr(W)=max⁡{⟨W,X⟩:X∈En, rankX≤r},cr=E∥g∥2r=2rΓ((r+1)/2)Γ(r/2),g∼N(0,Ir).\begin{aligned} M_r(W)&=\max\{\langle W,X\rangle:X\in\mathcal{E}_n,\ \mathop{\mathrm{rank}}X\le r\},\\ c_r&=\frac{\mathbb E\|g\|_2}{\sqrt r} =\sqrt{\frac2r}\frac{\Gamma((r+1)/2)}{\Gamma(r/2)},\quad g\sim N(0,I_r). \end{aligned}

The Gaussian norm ratio satisfies 2cr=2−1/(2r)+O(r−2)2c_r=2-1/(2r)+O(r^{-2}). Our two estimates are, with probability tending to one,

Mr(W)n≤2cr+C[rlog⁡nn+(rlog⁡n)3/4n1/4],1nmax⁡X∈EnFn(X)≥2−C0n−1/5.\begin{align} \begin{split} \frac{M_r(W)}n\le 2c_r+C\biggl[&r\sqrt{\frac{\log n}{n}}\\ &+\frac{(r\log n)^{3/4}}{n^{1/4}}\biggr], \end{split} \tag*{(2)}\\ \frac1n\max_{X\in\mathcal{E}_n}F_n(X)&\ge2-C_0n^{-1/5}. \tag*{(3)} \end{align}

The constants are absolute, and (2) holds for deterministic integer sequences 1≤r≤n1\le r\le\sqrt n. The first estimate bounds all rank-rr representations; the second supplies a feasible competitor. We establish them in three steps, then compare the errors with the gap 1/r1/r.

1. The low-rank gap for Gaussian entries. First replace WW by a matrix BB from the normalized Gaussian orthogonal ensemble (GOE), whose independent upper-triangular entries are centered Gaussian with variances 1/n1/n off the diagonal and 2/n2/n on it. For a matrix U∈Rn×rU\in\mathbb{R}^{n\times r} with unit rows ui⊤u_i^\top, set HU=⟨B,UU⊤⟩H_U=\langle B,UU^\top\rangle and QU=U⊤U/nQ_U=U^\top U/n. The matrix QUQ_U records how the row vectors are distributed among the rr coordinates. It satisfies QU⪰0Q_U\succeq0, tr⁡QU=1\operatorname{tr}Q_U=1, and

EHUHV=2n∥U⊤V∥F2.\mathbb E H_UH_V=\frac2n\|U^\top V\|_F^2.

The quadratic process HUH_U is easier to bound when compared with a process that is linear in the rows. Fix Q⪰0Q\succeq0 of trace one and independent gi∼N(0,Ir)g_i\sim N(0,I_r), and let YU=2∑igi⊤Q1/2uiY_U=2\sum_i g_i^\top Q^{1/2}u_i. Direct expansion gives

E(HU−HV)2−E(YU−YV)2=2n(∥U⊤U−nQ∥F2+∥V⊤V−nQ∥F2−2∥U⊤V−nQ∥F2).\begin{aligned} &\mathbb E(H_U-H_V)^2-\mathbb E(Y_U-Y_V)^2\\ &\quad=\frac2n\bigl(\|U^\top U-nQ\|_F^2+\|V^\top V-nQ\|_F^2\\ &\hspace{38mm}-2\|U^\top V-nQ\|_F^2\bigr). \end{aligned}

Thus the difference is at most 4nδ24n\delta^2 whenever QUQ_U and QVQ_V lie within Frobenius distance δ\delta of QQ.

To use this comparison, we discretize the row vectors and group configurations with nearby matrices QUQ_U. Use δ=n−3\delta=n^{-3} for both discretizations. A δ\delta-net of the unit sphere with at most (3/δ)r(3/\delta)^r points gives a row net N\mathcal N with log⁡∣N∣≤nrlog⁡(3/δ)\log|\mathcal N|\le nr\log(3/\delta). Cover the trace-one positive semidefinite matrices by at most K=(1+2/δ)r(r+1)/2K=(1+2/\delta)^{r(r+1)/2} Frobenius balls of radius δ\delta, centered in that set, and assign each U∈NU\in\mathcal N to one ball according to QUQ_U.

Within a cell centered at QQ, add to YUY_U independent Gaussian variables ZUZ_U of variance 2nδ22n\delta^2. The increments of YU+ZUY_U+Z_U dominate those of HUH_U, so the Gaussian comparison inequality [19 Theorem 7.2.11] gives

Emax⁡U in cellHU≤2nEg⊤Qg+2δnlog⁡∣N∣≤2ncr+Cδnrlog⁡(3/δ).\begin{aligned} \mathbb E\max_{U\text{ in cell}}H_U &\le2n\mathbb E\sqrt{g^\top Qg}+2\delta\sqrt{n\log|\mathcal N|}\\ &\le2nc_r+C\delta n\sqrt{r\log(3/\delta)}. \end{aligned}

Indeed, Eg⊤Qg\mathbb E\sqrt{g^\top Qg} is symmetric and concave in the eigenvalues of QQ, whose sum is one; it is maximized at Q=I/rQ=I/r. This is where the dimension-dependent gap enters.

Each cell maximum is 2n\sqrt{2n}-Lipschitz in the independent standard Gaussian coordinates generating BB: the squared coefficient norm of HUH_U is (2/n)∥UU⊤∥F2≤2n(2/n)\|UU^\top\|_F^2\le2n. Write ZkZ_k for the maximum over the kk-th nonempty cell. Gaussian concentration [19 Theorem 5.2.2] and a union bound give, for t≥0t\ge0,

P ⁣{max⁡k(Zk−EZk)>t}≤min⁡{1,Ke−c1t2/n}.\mathbb P\!\left\{\max_k(Z_k-\mathbb EZ_k)>t\right\} \le\min\{1,K e^{-c_1t^2/n}\}.

Here c1>0c_1>0 is absolute, and no independence between the cell maxima is required. Integrating this bound, splitting the integral at (n/c1)log⁡(2K)\sqrt{(n/c_1)\log(2K)}, yields

Emax⁡kZk≤max⁡kEZk+Cnlog⁡(2K).\mathbb E\max_k Z_k \le\max_k\mathbb EZ_k+C\sqrt{n\log(2K)}.

Here CC is absolute. Since log⁡(2K)≤Cr2log⁡n\log(2K)\le Cr^2\log n, the contribution after division by nn is at most Crlog⁡n/nCr\sqrt{\log n/n}. For any symmetric TT, approximating each unit row within δ\delta changes ⟨T,UU⊤⟩\langle T,UU^\top\rangle by at most 2nδ∥T∥op2n\delta\|T\|_{\rm op}. Since E∥B∥op=O(1)\mathbb E\|B\|_{\rm op}=O(1), we obtain

EMr(B)n≤2cr+Crlog⁡nn.\begin{equation} \frac{\mathbb E M_r(B)}n\le2c_r+C r\sqrt{\frac{\log n}{n}}. \tag*{(4)} \end{equation}

To compare with the zero-diagonal matrix WW, put B∘=B−Diag(B11,…,Bnn)B^\circ=B-\mathop{\mathrm{Diag}}(B_{11},\ldots,B_{nn}). Every feasible matrix has unit diagonal, so, pointwise,

Mr(B)=Mr(B∘)+tr⁡B.M_r(B)=M_r(B^\circ)+\operatorname{tr}B.

As Etr⁡B=0\mathbb E\operatorname{tr}B=0, these two maxima have the same expectation. The same identity holds when the maximum is restricted to the row net. Thus only the off-diagonal entries need to be replaced.

2. Replacing Gaussian entries by symmetric signs. We now transfer the estimate to the random graph. The maximum is not smooth in the matrix entries, so we first replace it by a logarithm of a sum of exponentials. This allows a Taylor expansion as entries are replaced one at a time, following the approach for random semidefinite programs in [18]. On the same row net, put

hU(ξ)=2n∑i<jξijui⊤uj,fβ(ξ)=1nβlog⁡∑U∈NeβhU(ξ).\begin{aligned} h_U(\xi)&=\frac2{\sqrt n}\sum_{i<j}\xi_{ij}u_i^\top u_j,\\ f_\beta(\xi)&=\frac1{n\beta}\log\sum_{U\in\mathcal N}e^{\beta h_U(\xi)}. \end{aligned}

The smooth maximum differs from n−1max⁡UhUn^{-1}\max_U h_U by a quantity between zero and log⁡∣N∣/(nβ)≤Crlog⁡n/β\log|\mathcal N|/(n\beta)\le Cr\log n/\beta. For one coordinate, ∣∂ijhU∣≤2/n|\partial_{ij}h_U|\le2/\sqrt n. The fourth derivative of fβf_\beta is β3/n\beta^3/n times the difference between the fourth centered moment and three times the squared variance of these slopes under the exponential weights. The bound on the slopes therefore gives

∣∂ij4fβ∣≤Cβ3/n3.|\partial_{ij}^4f_\beta|\le C\beta^3/n^3.

For completeness, fix one coordinate and condition on all the others in the current mixture of Gaussian and sign entries. Write ϕ(t)\phi(t) for the resulting smooth maximum. Taylor’s formula gives

ϕ(t)=∑j=03ϕ(j)(0)j!tj+R(t),∣R(t)∣≤Cβ3n3∣t∣4.\phi(t)=\sum_{j=0}^3\frac{\phi^{(j)}(0)}{j!}t^j+R(t), \qquad |R(t)|\le\frac{C\beta^3}{n^3}|t|^4.

The derivative bound is uniform in tt and in the conditioned entries. A standard Gaussian gg and a symmetric sign ε\varepsilon have the same moments through degree three, while Eg4=3\mathbb Eg^4=3 and Eε4=1\mathbb E\varepsilon^4=1. Their conditional expectations therefore cancel in the polynomial part, leaving

∣Egϕ(g)−Eεϕ(ε)∣≤Cβ3/n3.|\mathbb E_g\phi(g)-\mathbb E_\varepsilon\phi(\varepsilon)| \le C\beta^3/n^3.

Taking expectation over the other entries and telescoping over the (n2)\binom n2 replacements gives total error at most Cβ3/nC\beta^3/n, with a constant independent of rr. Adding the smoothing errors and the O(n−3)O(n^{-3}) expected net errors gives

∣EMr(W)−EMr(B)n∣≤C(rlog⁡nβ+β3n+n−3).\left|\frac{\mathbb E M_r(W)-\mathbb E M_r(B)}n\right| \le C\left(\frac{r\log n}{\beta}+\frac{\beta^3}{n}+n^{-3}\right).

Here both ensembles have bounded expected operator norm. The choice β=(nrlog⁡n)1/4\beta=(nr\log n)^{1/4} balances the smoothing and replacement errors; applying (4) now gives the desired expectation bound. To pass to a probability bound, observe that changing one sign changes Mr(W)/nM_r(W)/n by at most 4n−3/24n^{-3/2}. The bounded-differences inequality [19 Theorem 2.9.1] gives

P{Mr(W)−EMr(W)>nt}≤e−cnt2.\mathbb P\{M_r(W)-\mathbb E M_r(W)>nt\}\le e^{-cnt^2}.

Choosing t=Clog⁡n/nt=C\sqrt{\log n/n} proves (2), with failure probability any prescribed negative power of nn after increasing CC. Matching the third moments is essential to this error estimate and is available here because the graph density is 1/21/2.

3. A feasible matrix near the spectral bound. We seek a positive semidefinite matrix concentrated on eigenvectors whose eigenvalues are close to 22. Its diagonal must also be close to constant, so that enforcing unit diagonal changes the objective only slightly. The local semicircle law provides this control. Set d=n−1/5d=n^{-1/5} and z=2+dz=2+d. Spectral-edge rigidity [17 Theorem 2.9] gives λmax⁡(W)≤2+d/4\lambda_{\max}(W)\le2+d/4 with probability tending to one. On this event let

P=(zI−W)−4,D=Diag(P11,…,Pnn),X=D−1/2PD−1/2.\begin{align*} P & =(zI-W)^{-4},\quad D=\mathop{\mathrm{Diag}}(P_{11},\ldots,P_{nn}),\\ X & =D^{-1/2}PD^{-1/2}. \end{align*}

The matrix PP assigns weight (z−λ)−4(z-\lambda)^{-4} to an eigenvector with eigenvalue λ\lambda, favouring those near the upper spectral edge. Diagonal normalization gives X⪰0X\succeq0 and diagX=1\mathop{\mathrm{diag}}X=\mathbf{1}. We will check both its objective value and the mean penalty in FnF_n.

Write Zn=O≺(an)Z_n=O_\prec(a_n) when, for every fixed η,D0>0\eta,D_0>0, P{∣Zn∣>nηan}≤n−D0\mathbb P\{|Z_n|>n^\eta a_n\}\le n^{-D_0} for all sufficiently large nn, including maxima over the indicated indices. Put q(w)=∫(w−x)−1 dμsc(x)q(w)=\int(w-x)^{-1}\,d\mu_{\rm sc}(x), where μsc\mu_{\rm sc} is the semicircle law, with density 4−x2/(2π)\sqrt{4-x^2}/(2\pi) on [−2,2][-2,2]. We justify its application on the contour explicitly. The matrix WW satisfies [17 Definition 2.2]: its upper-triangular entries are independent and centered, the off-diagonal variances are 1/n1/n, and every moment of nWij\sqrt n W_{ij} is uniformly bounded. The variance condition there is E∣Wij∣2=n−1(1+O(δij))\mathbb E|W_{ij}|^2=n^{-1}(1+O(\delta_{ij})), where δij\delta_{ij} is the Kronecker delta; it permits zero diagonal variance.

Let Γ={w:∣w−z∣=d/4}\Gamma=\{w:|w-z|=d/4\}. On its upper semicircle, κ=ℜw−2∈[3d/4,5d/4]\kappa=\Re w-2\in[3d/4,5d/4] and 0<ℑw≤d/40<\Im w\le d/4. Taking, for example, τ=1/10\tau=1/10, we have 3d/4≥n−2/3+τ3d/4\ge n^{-2/3+\tau} for large nn. Thus these points belong to the domain {E+iη:∣E∣≥2+n−2/3+τ, η>0}\{E+i\eta:|E|\ge2+n^{-2/3+\tau},\ \eta>0\} of [17 Theorem 10.3]. This theorem imposes no positive lower cutoff on η\eta, so net points may approach the real endpoints arbitrarily closely. Its entrywise estimate, with κ+ℑw≍d\kappa+\Im w\asymp d, gives

[(wI−W)−1]ii=q(w)+O≺(n−1/2d−1/4)[(wI-W)^{-1}]_{ii}=q(w)+O_\prec(n^{-1/2}d^{-1/4})

uniformly in the deterministic upper-semicircle point ww and in ii. The source uses (W−wI)−1(W-wI)^{-1} and the opposite sign for the semicircle transform; changing both signs gives our convention.

To obtain a simultaneous bound, choose a deterministic n−3n^{-3}-net of the upper semicircle using points with positive imaginary part, also approximating its two real endpoints. It has at most Cn3Cn^3 points. A union bound over the net and the nn diagonal entries preserves stochastic domination, since the local law permits any prescribed polynomial failure exponent. On the rigidity event above, the closed disk bounded by Γ\Gamma lies at distance at least d/2d/2 from the spectrum of WW. For R(w)=(wI−W)−1R(w)=(wI-W)^{-1} and points w,vw,v in this disk, the resolvent identity gives

∥R(w)−R(v)∥op≤4d−2∣w−v∣.\|R(w)-R(v)\|_{\rm op}\le4d^{-2}|w-v|.

The integral defining qq gives the analogous bound ∣q(w)−q(v)∣≤Cd−2∣w−v∣|q(w)-q(v)|\le Cd^{-2}|w-v|. Interpolation from the net therefore costs at most Cn−3d−2=Cn−13/5Cn^{-3}d^{-2}=Cn^{-13/5}, smaller than n−1/2d−1/4=n−9/20n^{-1/2}d^{-1/4}=n^{-9/20}. This includes the real endpoints. Finally, R(w‾)=R(w)‾R(\overline w)=\overline{R(w)} and q(w‾)=q(w)‾q(\overline w)=\overline{q(w)} extend the same bound to the lower semicircle. The estimate consequently holds simultaneously on all of Γ\Gamma.

Both resolvents are analytic in a neighborhood of the closed disk on this event. Applying Cauchy’s formula to their difference multiplies its contour bound by at most Cjd−(j−1)C_jd^{-(j-1)} for the (j−1)(j-1)-st derivative.

Since the (j−1)(j-1)-st derivative of (zI−W)−1(zI-W)^{-1} is (−1)j−1(j−1)!(zI−W)−j(-1)^{j-1}(j-1)!(zI-W)^{-j}, we obtain, for j=3,4j=3,4,

[(zI−W)−j]ii=aj+O≺(n−1/2d3/4−j),aj=∫(z−x)−j dμsc(x)≍d3/2−j.\begin{aligned} [(zI-W)^{-j}]_{ii}&=a_j+O_\prec(n^{-1/2}d^{3/4-j}),\\ a_j&=\int(z-x)^{-j}\,d\mu_{\rm sc}(x)\asymp d^{3/2-j}. \end{aligned}

The last estimate follows by substituting 2−x=dt2-x=dt and using the square-root density at the edge. These formulas serve two purposes: the case j=4j=4 controls the diagonal normalization, while j=3j=3 controls the objective through WP=zP−(zI−W)−3WP=zP-(zI-W)^{-3}. Both have the same relative error. In particular,

u:=max⁡i∣Pii/a4−1∣=O≺(n−1/2d−3/4) ⁣=O≺(n−7/20).u:=\max_i|P_{ii}/a_4-1| =O_\prec(n^{-1/2}d^{-3/4})\!=O_\prec(n^{-7/20}).

The diagonal normalization is therefore a small perturbation. Let CD=(D/a4)−1/2C_D=(D/a_4)^{-1/2}. Since ∥CD−I∥op=O(u)\|C_D-I\|_{\rm op}=O(u) and P⪰0P\succeq0, the trace norm satisfies

∥X−P/a4∥tr=∥CD(P/a4)CD−P/a4∥tr≤O(u)tr⁡(P/a4)=O(nu).\begin{aligned} \|X-P/a_4\|_{\rm tr} &=\|C_D(P/a_4)C_D-P/a_4\|_{\rm tr}\\ &\le O(u)\operatorname{tr}(P/a_4)=O(nu). \end{aligned}

Using WP=zP−(zI−W)−3WP=zP-(zI-W)^{-3} and ∥W∥op=O(1)\|W\|_{\rm op}=O(1) with high probability, we conclude that

⟨W,X⟩n=z−a3a4+O≺(n−7/20)≥2−Cd+O≺(n−7/20).\frac{\langle W,X\rangle}n =z-\frac{a_3}{a_4}+O_\prec(n^{-7/20}) \ge2-Cd+O_\prec(n^{-7/20}).

Indeed, the estimates a3≍d−3/2a_3\asymp d^{-3/2} and a4≍d−5/2a_4\asymp d^{-5/2} give 0<a3/a4≤Cd0<a_3/a_4\le Cd; together with z=2+dz=2+d, this proves the last inequality. Moreover, ∥X∥op≤∥P∥op/min⁡iPii≤Cd−3/2\|X\|_{\rm op}\le\|P\|_{\rm op}/\min_iP_{ii}\le Cd^{-3/2}, and therefore

1⊤X1n3/2≤∥X∥opn≤Cn−1/5.\frac{\mathbf{1}^\top X\mathbf{1}}{n^{3/2}} \le\frac{\|X\|_{\rm op}}{\sqrt n}\le Cn^{-1/5}.

The stochastic error is o(n−1/5)o(n^{-1/5}) even after a sufficiently small fixed power loss. This proves (3).

Comparing the two values. It remains to make the errors smaller than the 1/r1/r loss in 2cr2c_r. Choose r=⌊c(n/(log⁡n)3)1/7⌋r=\lfloor c(n/(\log n)^3)^{1/7}\rfloor. Then

r2log⁡nn=o(1),rn−1/5=o(1),r n−1/4(rlog⁡n)3/4≤c7/4.\begin{gathered} r^2\sqrt{\frac{\log n}{n}}=o(1),\qquad rn^{-1/5}=o(1),\\ r\,n^{-1/4}(r\log n)^{3/4}\le c^{7/4}. \end{gathered}

Take c>0c>0 small enough that the constant in (2) times c7/4c^{7/4} is less than 1/81/8. Equations (2)–(3) then give, with probability tending to one,

max⁡X∈EnrankX≤rFn(X)≤Mr(W)≤n(2−14r)<max⁡X∈EnFn(X).\begin{aligned} \max_{\substack{X\in\mathcal{E}_n\\\mathop{\mathrm{rank}}X\le r}}F_n(X) &\le M_r(W)\le n\left(2-\frac1{4r}\right)\\ &<\max_{X\in\mathcal{E}_n}F_n(X). \end{aligned}

Every optimizer has rank greater than rr, proving the theorem. ◻

The exponent 1/71/7 comes from balancing the comparison errors against the 1/r1/r gap; it need not describe the actual growth rate.

There is a more specific prediction suggested by the Gaussian infinite-component spin glass. Hastings [15] derived a ground-state dimension of order n2/5n^{2/5}. Aspelmeier and Moore [16] supported this scaling numerically and gave an alternative argument balancing a finite-dimension energy correction of order 1/r1/r against a spectral correction of order (r/n)2/3(r/n)^{2/3}. Balancing these two terms gives rr of order n2/5n^{2/5}. Motivated by this prediction, we propose the following statement for unweighted random graphs.

Conjecture 6.2. If G∼G(n,12)G\sim G(n,\frac12), then

log⁡ρ(G)log⁡n→P25.\frac{\log\rho(G)}{\log n}\xrightarrow{\mathbb P}\frac25.

The spin-glass calculations motivate this conjecture but do not establish it for the graph model. In particular, agreement of leading optimal values does not imply agreement of exact optimal ranks. Theorem 6.1 supplies a polynomial lower bound; even an upper bound ρ(G)=o(n)\rho(G)=o(\sqrt n) with probability tending to one remains open here.

References

  1. [1]Goemans, M. X., & Williamson, D. P. (1995). Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM, 42, 1115–1145.
  2. [2]Bhardwaj, A. (2026). The complexity of recognizing SDP exactness for the maximum cut problem. In arXiv:2609.03508. https://arxiv.org/abs/2609.03508
  3. [3]Hong, D., Lee, H., & Wei, A. (2021). Optimal solutions and ranks in the max-cut SDP. In arXiv:2109.02238. https://arxiv.org/abs/2109.02238
  4. [4]Mirka, R., & Williamson, D. P. (2024). Max cut and semidefinite rank. Oper. Res. Lett., 53, Art.~107067.
  5. [5]Burer, S., Monteiro, R. D. C., & Zhang, Y. (2002). Rank-two relaxation heuristics for Max-Cut and other binary quadratic programs. SIAM J. Optim., 12, 503–521.
  6. [6]Barvinok, A. I. (1995). Problems of distance geometry and convex properties of quadratic maps. Discrete Comput. Geom., 13, 189–202.
  7. [7]Pataki, G. (1998). On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues. Math. Oper. Res., 23, 339–358.
  8. [8]Delorme, C., & Poljak, S. (1993). Laplacian eigenvalues and the maximum cut problem. Math. Programming, 62, 557–574.
  9. [9]Grone, R., Pierce, S., & Watkins, W. (1990). Extremal correlation matrices. Linear Algebra Appl., 134, 63–70.
  10. [10]Li, C.-K., & Tam, B.-S. (1994). A note on extreme correlation matrices. SIAM J. Matrix Anal. Appl., 15, 903–908.
  11. [11]Ramana, M., & Goldman, A. J. (1995). Some geometric results in semidefinite programming. J. Global Optim., 7, 33–50.
  12. [12]Godsil, C., Roberson, D. E., Rooney, B., Šámal, R., & Varvitsiotis, A. (2017). Universal completability, least eigenvalue frameworks, and vector colorings. Discrete Comput. Geom., 58(2), 265–292.
  13. [13]Eisenberg-Nagy, M., Laurent, M., & Varvitsiotis, A. (2014). Forbidden minor characterizations for low-rank optimal solutions to semidefinite programs over the elliptope. J. Combin. Theory Ser. B, 108, 40–80.
  14. [14]van Dam, E. R., & Sotirov, R. (2016). New bounds for the max-$k$-cut and chromatic number of a graph. Linear Algebra Appl., 488, 216–234.
  15. [15]Hastings, M. B. (2000). Ground state and spin glass phase of the large $N$ infinite range spin glass via supersymmetry. J. Stat. Phys., 99, 171–198.
  16. [16]Aspelmeier, T., & Moore, M. A. (2004). Generalized Bose--Einstein phase transition in large-$m$ component spin glasses. Phys. Rev. Lett., 92, 077201.
  17. [17]Benaych-Georges, F., & Knowles, A. (2016). Lectures on the local semicircle law for Wigner matrices. In arXiv:1601.04055. https://arxiv.org/abs/1601.04055
  18. [18]Montanari, A., & Sen, S. (2015). Semidefinite programs on sparse random graphs and their application to community detection. In arXiv:1504.05910. https://arxiv.org/abs/1504.05910
  19. [19]Vershynin, R. (2018). High-Dimensional Probability: An Introduction with Applications in Data Science (Vol. 47). Cambridge University Press.
  20. [20]Mohar, B., & Poljak, S. (1990). Eigenvalues and the max-cut problem. Czechoslovak Math. J., 40(2), 343–352.
  21. [21]Lovász, L. (1978). Kneser's conjecture, chromatic number, and homotopy. J. Combin. Theory Ser. A, 25(3), 319–324.

Paper details

vlnc:W_ftmnb8fw
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 22

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents