WorksMathematics
Optimal solution ranks in the Max-Cut semidefinite relaxation
Abstract
For every and with and , we construct a connected unweighted graph on vertices whose Max-Cut semidefinite relaxation has a unique optimal solution of rank . The main examples are the Kneser graphs , whose unique optima have rank . 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 be a graph on the vertex set with symmetric nonnegative weight matrix , zero diagonal, and Laplacian . We denote the Goemans–Williamson relaxation [1] by and its optimal value by :
where is the elliptope. A point of 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: has rank one exactly when with , a cut. Let be the set of optimal solutions of , which is a face of , and define the optimal rank
Thus measures the dimension needed by the best optimal representation, and 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 can be as a function of the number of vertices.
An upper bound on comes from general theory. is a nonempty compact face of , so it has an extreme point, which is an extreme point of ; and by the theorem of Barvinok [6] and Pataki [7], an extreme point of a spectrahedron defined by linear equations has rank with . Thus an optimal solution of attains a rank satisfying this bound, and hence
The question we answer is whether equality in (1) is attained for every , even by connected unweighted graphs.
The distinction between arbitrary objectives and graph objectives is essential here. Extreme points of 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 . Since diagonal terms contribute a constant on , 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 has the two-element subsets of as vertices, with two vertices adjacent exactly when the corresponding subsets are disjoint.
Theorem 1.1. Let and . Then the relaxation has a unique optimal solution , given by and . In particular .
Explicitly, is the Gram matrix obtained by assigning to the pair the unit vector proportional to the centred indicator vector , where is the -th standard basis vector. Disjoint pairs have inner product and distinct overlapping pairs have inner product . For this is the Petersen graph, whose unique optimal solution has rank .
The Kneser family skips rank three, because 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 and every integer , there is a connected unweighted graph on vertices whose Max-Cut semidefinite relaxation has a unique optimal solution of rank .
Corollary 1.3. For every , the maximum of over connected unweighted graphs on vertices equals . 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 , where each pair is an edge independently with probability , we prove
with probability tending to one, for an absolute constant (Theorem 6.1). Thus, with probability tending to one, every optimal representation of an Erdős–Rényi graph with edge probability 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: 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 , 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 . The identity matrix is strictly feasible for the primal problem, so strong duality holds and the dual optimum is attained. If is an optimal dual slack, complementary slackness confines every optimum to . A scalar diagonal choice gives the familiar eigenvalue bound.
Lemma 2.1 (Eigenvalue bound [20, 8]). Let and let be its eigenspace. For every we have , with equality if and only if . If some satisfies , then and
Proof. and give , that is . Equality holds if and only if , which for two positive semidefinite matrices means , that is . ◻
Lemma 2.2 (Parametrising the face). Let be a subspace of dimension , let have columns forming a basis of , and let be the -th row of . Then the map is a rank-preserving bijection from onto .
Proof. A symmetric has if and only if for a symmetric , which is unique because has full column rank; for the same reason if and only if , and . The condition reads . ◻
In these coordinates, uniqueness becomes a question about linear equations: do the conditions determine ? 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 , , span , and that contains a positive definite matrix . Then . If moreover is the top eigenspace of , then and .
Proof. The equations are linear in , and if the coefficient matrices span they have at most one solution. The second statement follows from Lemmas 2.1 and 2.2. ◻
The converse holds whenever : a nonzero symmetric matrix orthogonal to every gives sufficiently small feasible perturbations of both signs. Thus uniqueness is equivalent to the absence of such a perturbation. In particular, is necessary. Our constructions achieve equality before any pendant vertices are added.
We will use two small graphs to start the construction. The graph has the unique feasible matrix , of rank one. For the triangle , the objective of a Gram matrix of unit vectors is
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 . Hence the optimum for is unique and has rank two.
The following extension lets us add vertices without changing the optimal rank.
Lemma 2.4. Let be obtained from a graph by adding a new vertex and a single edge of weight one, where . Then If the optimal solution for is unique, then so is the optimal solution for .
Proof. For any unit-vector representation of , the old edges contribute at most and the new edge contributes . Conversely, an optimal representation of extends by setting , attaining without increasing the rank. Every optimum for must therefore restrict to an optimum for , which proves the equality of optimal ranks. Moreover, equality on the new edge forces . 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 , let and . We write vertices as pairs , and for the adjacency matrix. The graph is regular of degree , so and the top Laplacian eigenspace is the least adjacency eigenspace.
Let be the incidence matrix of pairs versus points, if . Then , where is the all-ones matrix, because a point lies in pairs and two distinct points lie in exactly one. Put
Since on , the map is injective there and .
Lemma 3.1. The Laplacian of has eigenvalue on , eigenvalue on , and eigenvalue on the orthogonal complement of . In particular and its eigenspace is exactly .
Proof. For with we have , and
because each lies in pairs disjoint from . So on . The space is the range of , since ; its orthogonal complement is . For such also , so
the last term correcting for the pair , which is subtracted twice. Finally . Hence has the stated eigenvalues, and . ◻
Proof of Theorem 1.1. Let be the orthogonal projector of onto . By Lemma 3.1 and the identity on , the orthogonal projector onto is , with entries
where is the indicator vector of . The matrix has entries ; its diagonal entries () are , it is positive semidefinite, and its range is . By Lemma 2.1, is optimal and .
It remains to show that every optimum equals . By Lemma 2.3, it suffices to prove that the matrices span the symmetric operators on . Indeed, the rows of restricted to this subspace are represented by , and the positive definite scalar operator gives .
Suppose a symmetric operator on is orthogonal to all these rank-one matrices. Extend it to a symmetric matrix on by setting . Orthogonality then reads
Let and . Summing over and using gives , that is for every . Summing over gives , so , and then for every because . The displayed relation now gives for , so . By Lemma 2.3, and .
Finally , so by (1). ◻
Remark 3.2. An alternative proof of the required nonsingularity follows from the entrywise square of . The Kneser construction uses exactly vectors, so the diagonal system is square. Indeed, for its unit Gram vectors . Thus is the Gram matrix of the coefficient matrices in the diagonal equations. With , the adjacency matrix of the triangular graph, it equals . On the three subspaces in Lemma 3.1, its eigenvalues are, respectively,
All are positive for . At the middle eigenvalue vanishes: is a perfect matching and has , explaining the missing rank in the Kneser family.
Remark 3.3. The optimal value is .
Rank three
The Kneser family leaves one rank to account for. The triangle supplies rank two, but 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 be the unweighted graph obtained by joining a new vertex to every vertex of . Then the Max-Cut semidefinite relaxation of has a unique optimal solution of rank three and optimal value , where .
Proof. Write for the hub, label the cycle vertices in cyclic order, and put
Assign the hub the unit vector and assign the cycle vertices
The five cycle vectors lie on a circle below the hub vector, with consecutive cycle vertices separated by an angle of around that circle. To see the choice of height, replace by in this representation. The sum of the edge inner products is , minimized at . We next certify that this representation is optimal among all feasible Gram matrices. Let have the displayed rows. Its columns are independent, so is feasible and has rank three.
Let be the adjacency matrix of and consider, in the vertex order , the matrix
The eigenvalues of are , . On the nonconstant cycle eigenspaces, therefore has eigenvalues and , each twice. On the remaining subspace, with the constant cycle vector normalized to unit length, it is represented by
This matrix has determinant zero and trace . Thus and .
The identity shows that annihilates the first two columns of . For the third column, the hub equation is and each cycle equation is . Hence and .
Let be the adjacency matrix of . Since and have the same off-diagonal entries, every satisfies
Equality holds for because . Minimizing is equivalent to maximizing the Max-Cut objective, so is optimal. For any optimum , equality gives , and therefore .
The graph has ten edges, so the optimal value is . Its maximum cut has value : if cycle vertices lie opposite the hub, at most edges cross the cut, and equality is attained by placing cycle vertices opposite the hub.
It remains to show that the diagonal equations allow no other optimum. By Lemma 2.2, write with positive semidefinite. The hub equation gives . The equation at each cycle vertex becomes
The five functions are linearly independent when evaluated at the five angles . Indeed, multiplying a vanishing linear combination by gives a polynomial of degree at most four with five distinct roots . All five coefficients in the displayed equation must therefore vanish. Since , this gives and . Hence , proving uniqueness. ◻
Remark 4.2. The wheel illustrates why it is useful to allow a general dual slack matrix. Its largest Laplacian eigenvalue is and is simple: an eigenvector has entry at the hub and entry at every cycle vertex. No Gram matrix with unit diagonal can have its range in this eigenspace. The matrix 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 , so . For start with , and for start with ; as observed in § 2, their optima are unique and have ranks one and two, respectively. For use the six-vertex wheel of Theorem 4.1. For use , whose unique optimum has rank 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 , a two-element set can be chosen outside their union. Each starting graph has vertices. Attach pendant vertices and apply Lemma 2.4 repeatedly. The resulting graph is connected and unweighted, and its optimum is unique and still has rank . ◻
Proof of Corollary 1.3. The upper bound (1) applies to every graph under consideration. Theorem 1.2 with attains it in the smallest of the three classes, the connected unweighted graphs. ◻
Can the bound be attained with a unique optimum by a -connected graph at every order , 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 such that, for ,
The idea is to separate objective values: if every representation in at most dimensions performs worse than one feasible matrix, then every optimum has rank greater than . After centering and scaling the adjacency matrix, we compare both values with the spectral edge . A Gaussian comparison produces a loss of order at bounded rank, and a spectral construction comes closer to . The main work is to keep the errors small enough as grows.
Proof of Theorem 6.1. Let be the adjacency matrix and put
Centering removes the mean edge density: the off-diagonal entries of are independent symmetric signs divided by , and . The term involving in accounts for the removed mean. The identity
shows that maximizing on is equivalent to the Max-Cut relaxation. Define
The Gaussian norm ratio satisfies . Our two estimates are, with probability tending to one,
The constants are absolute, and (2) holds for deterministic integer sequences . The first estimate bounds all rank- representations; the second supplies a feasible competitor. We establish them in three steps, then compare the errors with the gap .
1. The low-rank gap for Gaussian entries. First replace by a matrix from the normalized Gaussian orthogonal ensemble (GOE), whose independent upper-triangular entries are centered Gaussian with variances off the diagonal and on it. For a matrix with unit rows , set and . The matrix records how the row vectors are distributed among the coordinates. It satisfies , , and
The quadratic process is easier to bound when compared with a process that is linear in the rows. Fix of trace one and independent , and let . Direct expansion gives
Thus the difference is at most whenever and lie within Frobenius distance of .
To use this comparison, we discretize the row vectors and group configurations with nearby matrices . Use for both discretizations. A -net of the unit sphere with at most points gives a row net with . Cover the trace-one positive semidefinite matrices by at most Frobenius balls of radius , centered in that set, and assign each to one ball according to .
Within a cell centered at , add to independent Gaussian variables of variance . The increments of dominate those of , so the Gaussian comparison inequality [19 Theorem 7.2.11] gives
Indeed, is symmetric and concave in the eigenvalues of , whose sum is one; it is maximized at . This is where the dimension-dependent gap enters.
Each cell maximum is -Lipschitz in the independent standard Gaussian coordinates generating : the squared coefficient norm of is . Write for the maximum over the -th nonempty cell. Gaussian concentration [19 Theorem 5.2.2] and a union bound give, for ,
Here is absolute, and no independence between the cell maxima is required. Integrating this bound, splitting the integral at , yields
Here is absolute. Since , the contribution after division by is at most . For any symmetric , approximating each unit row within changes by at most . Since , we obtain
To compare with the zero-diagonal matrix , put . Every feasible matrix has unit diagonal, so, pointwise,
As , 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
The smooth maximum differs from by a quantity between zero and . For one coordinate, . The fourth derivative of is 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
For completeness, fix one coordinate and condition on all the others in the current mixture of Gaussian and sign entries. Write for the resulting smooth maximum. Taylor’s formula gives
The derivative bound is uniform in and in the conditioned entries. A standard Gaussian and a symmetric sign have the same moments through degree three, while and . Their conditional expectations therefore cancel in the polynomial part, leaving
Taking expectation over the other entries and telescoping over the replacements gives total error at most , with a constant independent of . Adding the smoothing errors and the expected net errors gives
Here both ensembles have bounded expected operator norm. The choice 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 by at most . The bounded-differences inequality [19 Theorem 2.9.1] gives
Choosing proves (2), with failure probability any prescribed negative power of after increasing . Matching the third moments is essential to this error estimate and is available here because the graph density is .
3. A feasible matrix near the spectral bound. We seek a positive semidefinite matrix concentrated on eigenvectors whose eigenvalues are close to . 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 and . Spectral-edge rigidity [17 Theorem 2.9] gives with probability tending to one. On this event let
The matrix assigns weight to an eigenvector with eigenvalue , favouring those near the upper spectral edge. Diagonal normalization gives and . We will check both its objective value and the mean penalty in .
Write when, for every fixed , for all sufficiently large , including maxima over the indicated indices. Put , where is the semicircle law, with density on . We justify its application on the contour explicitly. The matrix satisfies [17 Definition 2.2]: its upper-triangular entries are independent and centered, the off-diagonal variances are , and every moment of is uniformly bounded. The variance condition there is , where is the Kronecker delta; it permits zero diagonal variance.
Let . On its upper semicircle, and . Taking, for example, , we have for large . Thus these points belong to the domain of [17 Theorem 10.3]. This theorem imposes no positive lower cutoff on , so net points may approach the real endpoints arbitrarily closely. Its entrywise estimate, with , gives
uniformly in the deterministic upper-semicircle point and in . The source uses and the opposite sign for the semicircle transform; changing both signs gives our convention.
To obtain a simultaneous bound, choose a deterministic -net of the upper semicircle using points with positive imaginary part, also approximating its two real endpoints. It has at most points. A union bound over the net and the 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 lies at distance at least from the spectrum of . For and points in this disk, the resolvent identity gives
The integral defining gives the analogous bound . Interpolation from the net therefore costs at most , smaller than . This includes the real endpoints. Finally, and extend the same bound to the lower semicircle. The estimate consequently holds simultaneously on all of .
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 for the -st derivative.
Since the -st derivative of is , we obtain, for ,
The last estimate follows by substituting and using the square-root density at the edge. These formulas serve two purposes: the case controls the diagonal normalization, while controls the objective through . Both have the same relative error. In particular,
The diagonal normalization is therefore a small perturbation. Let . Since and , the trace norm satisfies
Using and with high probability, we conclude that
Indeed, the estimates and give ; together with , this proves the last inequality. Moreover, , and therefore
The stochastic error is even after a sufficiently small fixed power loss. This proves (3).
Comparing the two values. It remains to make the errors smaller than the loss in . Choose . Then
Take small enough that the constant in (2) times is less than . Equations (2)–(3) then give, with probability tending to one,
Every optimizer has rank greater than , proving the theorem. ◻
The exponent comes from balancing the comparison errors against the 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 . Aspelmeier and Moore [16] supported this scaling numerically and gave an alternative argument balancing a finite-dimension energy correction of order against a spectral correction of order . Balancing these two terms gives of order . Motivated by this prediction, we propose the following statement for unweighted random graphs.
Conjecture 6.2. If , then
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 with probability tending to one remains open here.
References
- [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]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]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]Mirka, R., & Williamson, D. P. (2024). Max cut and semidefinite rank. Oper. Res. Lett., 53, Art.~107067.
- [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]Barvinok, A. I. (1995). Problems of distance geometry and convex properties of quadratic maps. Discrete Comput. Geom., 13, 189–202.
- [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]Delorme, C., & Poljak, S. (1993). Laplacian eigenvalues and the maximum cut problem. Math. Programming, 62, 557–574.
- [9]Grone, R., Pierce, S., & Watkins, W. (1990). Extremal correlation matrices. Linear Algebra Appl., 134, 63–70.
- [10]Li, C.-K., & Tam, B.-S. (1994). A note on extreme correlation matrices. SIAM J. Matrix Anal. Appl., 15, 903–908.
- [11]Ramana, M., & Goldman, A. J. (1995). Some geometric results in semidefinite programming. J. Global Optim., 7, 33–50.
- [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]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]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]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]Aspelmeier, T., & Moore, M. A. (2004). Generalized Bose--Einstein phase transition in large-$m$ component spin glasses. Phys. Rev. Lett., 92, 077201.
- [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]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]Vershynin, R. (2018). High-Dimensional Probability: An Introduction with Applications in Data Science (Vol. 47). Cambridge University Press.
- [20]Mohar, B., & Poljak, S. (1990). Eigenvalues and the max-cut problem. Czechoslovak Math. J., 40(2), 343–352.
- [21]Lovász, L. (1978). Kneser's conjecture, chromatic number, and homotopy. J. Combin. Theory Ser. A, 25(3), 319–324.