PaperlayerView exact revision on arXiv

Source-linked AI summary

Sharp Lovasz-Theta Bounds on Random Graphs

Aaron Potechin, Jeff Xu

arXiv:2609.30064v1cs.CCcs.DMmath.CO

TL;DR

The leading constant of the Lovász-Theta function for G(n, 1/2) remained unresolved despite known bounds and evidence pointing to √n. This paper introduces an iterative witness-construction scheme and proves that, with high probability, the value is √n up to vanishing relative error.

Abstract

from arXiv · show

It is well known that the \Lovasz-Theta function of a random graph $G(n,\tfrac{1}{2})$ is $\Theta(\sqrt{n})$. More precisely, it is tightly concentrated in the interval \( [\sqrt{n},\, 2\sqrt{n}], \) where the upper bound follows from an explicit dual witness for the associated semidefinite program. Numerical evidence and heuristic arguments suggest that the true value is $(1+o(1))\sqrt{n}$. However, closing this gap has remained a longstanding challenge, resisting existing techniques even in light of recent progress on sharp algorithmic thresholds and non-asymptotic free probability. In this work, we resolve this question by proving that the \Lovasz-Theta function of $G(n,\tfrac{1}{2})$ is $(1+o_n(1))\sqrt{n}$ with high probability, determining its asymptotic value up to vanishing relative error.

1 Introduction

The introduction asks for the leading constant of the Lovász-Theta function on G(n, 1/2) and presents an iterative graph-matrix construction that yields a sharp bound. The result also connects this degree-2 SoS question to the study of higher-degree algorithms.

1 Introduction

  • The exact leading constant remained open despite known Θ(√n) bounds and the factor-two interval √n ≤ ϑ(G) ≤ 2√n.The introduction identifies the leading constant for G(n, 1/2) as the open question.Source: §1 · p. 4
  • Because the theta function is the base level of the SoS hierarchy, resolving this question is described as a natural prerequisite for sharp phase transitions at higher degrees.The paper situates the question within fine-grained understanding of higher-degree SoS algorithms on average-case problems.Source: §1 · p. 5

A Sharp Bound for the Lov´asz-Theta Function on G(n, 1/2)

  • With high probability, √n ≤ ϑ(G) ≤ (1 + o_n(1)) · √n, pinning its value to an interval of width o_n(√n).This determines the asymptotic value up to vanishing relative error.Source: A Sharp Bound for the Lov´asz-Theta… · p. 5
  • A novel iterative scheme constructs an explicit dual witness, addressing the lack of a canonical candidate and differing substantially from pseudo-calibration.The paper identifies explicit construction and amenability to analysis as central challenges.Source: A Sharp Bound for the Lov´asz-Theta… · pp. 5–6
  • The construction uses F(Q) plus a small correction, with Q formed from graph matrices of backbone-correction shapes that are freely independent.The paper notes a technical condition for the behavior of Mα and its transpose.Source: A Sharp Bound for the Lov´asz-Theta… · p. 6
  • Prior precise analyses of graph-matrix spectra or norms covered only a handful of restricted families, rather than general graph matrices.The cited examples include multi-Z-shaped matrices, scalar matrices, and restricted Gaussian-input or sparse-graph settings.Source: A Sharp Bound for the Lov´asz-Theta… · p. 6
  • The graph matrices share underlying randomness, and the adjacency matrix as a summand leaves no entropy in the remaining matrices, so applicability of black-box free probability remains open.Determining whether those techniques can be adapted is identified as an open question.Source: A Sharp Bound for the Lov´asz-Theta… · p. 6
  • The framework was subsequently applied to the related ellipsoid fitting problem, where it established a sharp threshold at d²/4.The paper also notes concurrent independent results using different techniques.Source: A Sharp Bound for the Lov´asz-Theta… · p. 7

2 Preliminaries and Technical Overview

The overview uses the dual SDP to frame the upper-bound problem and explains why the standard witness cannot reach the desired scale. It then defines a target matrix whose value should approach 1 while satisfying non-edge and positive-semidefinite constraints.

2.1 Folklore Bound of 2√n

  • Any dual-feasible pair (λ, M_G) certifies ϑ(G) ≤ λ by weak duality.The overview uses this relation to connect a constructed dual witness to an upper bound on the primal SDP.Source: §2.1 · p. 7
  • 2√n is the high-probability upper bound from the folklore dual witness based on the ±1 adjacency matrix.The witness is M_G = I_n − A_G; the adjacency-matrix norm supplies the bound.Source: §2.1 · p. 8
  • The standard witness is essentially tight because its spectrum has large positive eigenvalues around 2√n, so improving it requires a different construction.The replacement must preserve the non-edge constraints while offsetting those eigenvalues.Source: §2.1 · p. 8
  • A target matrix W must satisfy the non-edge constraints and be positive semidefinite; maximizing its coefficient c_k toward 1 yields the desired sharp scale.The target-matrix formulation is equivalent to the dual SDP up to rescaling and a simple manipulation.Source: §2.1 · pp. 8–9

A Snapshot of Our Construction

This section develops a dual-witness construction for the Lovász–Theta upper bound, progressing from preliminary witnesses to a truncated recursive Wigner-like matrix construction. It describes the graph-matrix and Chebyshev-shape tools used to analyze the construction and obtain an upper bound of \((1+o_n(1))\sqrt{n}\) on \(\vartheta(G)\).

A Snapshot of Our Construction

  • The construction targets a dual witness built from a non-negative function F of an inner matrix Q, with a low-order correction, approximate constraints, and objective √n.The stated challenge is to make F's image non-negative while nearly satisfying the edge constraints; spectral estimates are used to support the witness.Source: A Snapshot of Our Construction · p. 9

2.2 Graph Matrices: Our Trusty Hammer

  • Graph matrices encode shapes as matrices of polynomials in the graph's ±1 adjacency entries, and precise norm analysis is needed for sharp bounds on ϑ(G).The work focuses on shapes with one boundary vertex on each side, yielding n × n matrices indexed by graph vertices.Source: §2.2 · p. 10
  • For non-edge constraints, correction shapes pair with backbone shapes so higher-order terms carry a factor 1 + AG[i, j], which vanishes on non-edges.The target matrix is required to be positive semidefinite, and the goal is to maximize the leading coefficient.Source: §2.2 · pp. 11–12

2.3 Graph Matrix Multiplication: Shape Concatenation and Intersection Terms

  • Graph-matrix products decompose into proper shape concatenation plus intersection terms from unintended vertex identifications; backtracking intersections are a central part of the analysis.The authors define intersection patterns to capture these identifications and the resulting shapes.Source: §2.3 · pp. 13–15
  • With high probability, eMPj eMP1 approximates eMPj+1 + eMPj−1 with error norm o_n(1).The backtracking intersection contributes the lower-order term in this recurrence.Source: §2.3 · p. 15

2.4 Initial Attempts with Constant Improvement

  • Initial attempts improved the bound over 2√n but fell well short of √n.The authors present these attempts as intuition for the problem.Source: §2.4 · p. 16
  • Initial constant-factor constructions improve the 2√n baseline to upper-bound values 1.732 and 1.388, but do not provide a systematic route to a constant near 1.The construction is a modification of the polynomial-approximation attempt, inspired by sparse-regime work.Source: §2.4 · pp. 17–18

2.5 Our Construction of a Witness Matrix

  • With high probability, the construction gives a witness showing the Lovász-Theta number is at most (1 + o_n(1))√n.It replaces F(eMP1) with F(Q), choosing Q so F(Q) supplies its own correction terms and has matching coefficients for In and eMP1.Source: §2.5 · p. 18
  • The recursively built Q has Wigner-type spectral behavior, while its variance normalization yields a controlled scale and a correct-order spectral norm bound.The limiting spectrum is described as semicircular with radius 2; the formal analysis establishes sharp leading-constant matrix norm bounds.Source: §2.5 · pp. 22–23

2.6 Graph Matrices Meet Chebyshev Polynomials

  • For linear combinations of backbone-correction matrices, applying Pj yields a graph-matrix representation from j-way concatenations of base shapes.The section connects these rescaled Chebyshev polynomials to non-backtracking walks and defines backtracking intersection patterns as a generalization of the pattern producing eMPj−1.Source: §2.6 · pp. 23–24
  • Properly normalized linear combinations of backbone-correction matrices have Chebyshev-polynomial behavior matching the corresponding concatenated shapes, up to small-norm terms and corrections.Products are governed by the null intersection and, when it exists, the backtracking intersection; terms with small norm or small-norm corrections remain controlled under further multiplication.Source: §2.6 · pp. 25–26

2.7 Norm Bounds for Linear Combinations of Backbone-Correction Shapes

  • Dominant trace walks are tree-like F/L walks whose shape-steps pair noncrossingly, with paired shapes transposes of one another and using the same underlying edges.This pairing ensures that each underlying graph edge appears an even number of times in the walk.Source: §2.7 · pp. 29–30
  • For fixed q, dominant trace moments follow Catalan-number behavior, yielding semicircular limiting eigenvalue distributions for symmetric linear combinations and right-half-semicircle singular-value distributions otherwise.The same tree-like dominant walks give individual backbone-correction shapes semicircular limiting spectra, and the analysis identifies a free-independence phenomenon among the underlying constituents.Source: §2.7 · pp. 26, 28, 30
  • With high probability, each backbone-correction matrix has norm 2±o_n(1), using an analysis that controls the choices of boundary vertices in large-q trace walks.A nontrivial shape's outerplanar structure limits the next boundary vertex to at most two choices, and the F/L step type and boundary-vertex choice can be encoded together with a factor of 2.Source: §2.7 · p. 31
  • Theorem 2.40 gives sharp norm bounds for linear combinations of backbone-correction shapes, with an explicit lower-order contribution in its formal version.Source: §2.7 · p. 32

2.8 Putting Everything Together

  • A positive-semidefinite target matrix built from Q and F yields an upper bound of (1+o_n(1))√n on ϑ(G).The argument uses ||Q||≈2 and F(x)≥0 on [−2, 2].Source: §2.8 · p. 33
  • The construction addresses finite termination, shape-size truncation, and evaluation beyond the spectral edge by focusing on low-degree terms expected to decay.Source: §2.8 · p. 33
  • Finite iteration and Chebyshev truncation leave variance 1−o_{D,t*}(1), while a choice cγ=o_{t*,D}(1) restores inner-matrix variance 1 and enables a high-probability spectral estimate.The inner matrices are constructed through level t*, retaining P_j only for j≤D at each level.Source: §2.8 · pp. 33–34
  • Outer truncation forms F_D(eQ), and Lemma 2.45 addresses its approximate positive semidefiniteness when spec(eQ)⊆[−2−δ, 2+δ].Source: §2.8 · p. 34

(See also proposition D.3.)

The section completes an explicit witness construction, obtaining an upper bound of (1+o_n(1))√n on ϑ(G); the main theorem follows using duality and a folklore lower bound.

Bounds on Final Correction Terms

  • EarlyTerm corrects errors from terminating the recursive construction at level t*, while Chebyshev corrections address errors in approximating F_D.The early-termination correction is bounded in norm; the Chebyshev correction is treated in the correction-bounds result.Source: (See also proposition D.3.) · p. 34

Wrapping Up the Proof

  • Slowly growing the truncation parameter D allows the construction to achieve a value of (1+o_n(1))√n.The final parameter choice sets D=t*; taking D=ω(1) makes the stated Õ(1/D) error vanish.Source: (See also proposition D.3.) · pp. 35–36
  • The final matrix satisfies positive semidefiniteness and the non-edge constraints after normalization, making it a valid target matrix.The diagonal is normalized after adding the spectral correction, and the constraints are preserved under rescaling.Source: (See also proposition D.3.) · pp. 34–36
  • The main theorem for the Lovász–Theta function follows as a corollary; the primal SDP upper bound follows by duality, while its lower bound follows from the folklore result.Source: (See also proposition D.3.) · p. 36
  • The result also provides an explicit matrix whose value lower-bounds the primal SDP up to o_n(1) slack.The paper contrasts this explicit construction with the folklore lower bound used in the theorem proof.Source: (See also proposition D.3.) · p. 36

3 Spectral Norm Bounds for Backbone-Correction Shapes

This section develops trace-power and block-walk methods to study backbone-correction shapes, encoding block intersections as walks and controlling slack-block contributions. It uses these tools for precise spectral control, including identifying the limiting spectrum and a free-independence phenomenon among graph-matrix constituents.

3.1 The Trace Power Method

  • The trace-power expansion is organized as labeled trace walks, and only walks whose merged multigraph has every edge of even multiplicity contribute.Intersection patterns record which vertices share labels and characterize when the even-multiplicity condition holds.Source: §3.1 · p. 37

3.2 Blocks, Vertex Assignment Factors, and Vertex Separators for Blocks

  • First and last vertex appearances each receive a factor of √n, while middle appearances—separator vertices—receive no polynomial factor.For an interior block, its canonical separator consists of vertices appearing both earlier and later; the first and last blocks use their respective boundary vertices.Source: §3.2 · pp. 38–39

3.3 Forward Blocks, Return Blocks, and Slack Blocks

  • With a size-one separator, a block either has all vertices appear later and only its start appear earlier, or the reverse pattern with its end appearing later.The two cases correspond to separator {uτi} and {vτi}, respectively.Source: §3.3 · p. 40
  • Slack blocks have overlapping but nonidentical edge sets with another block, or at least two slack-witness vertices; non-slack blocks with separator Uτi or Vτi are forward or return blocks, respectively.The lemma says slack can be extracted from each slack block.Source: §3.3 · p. 42
  • At most 12DV slack blocks map to each pair (v, k), yielding a total bound of 24DV times the sum of |SI(τi)| - 1.Source: §3.3 · pp. 42–43

3.4 Block Walks

  • A trace block walk with sBW slack steps determines at most (jDV)^sBW(DV - 1) intersection patterns.Forward, return, and slack steps encode blocks; trace walks end at their starting vertex with no hyperedges remaining.Source: §3.4 · pp. 44–45

3.5 Trace Power Analysis via Block Walks

  • With no slack steps, trace block walks contribute NF/R(τ1, ..., τj)n - O_{j,DV}(1), while patterns with slack blocks contribute O_{j,DV}(1).For odd j, NF/R is zero.Source: §3.5 · p. 46
  • Counting trace block walks by their number of slack steps gives a sharper bound on slack-pattern contributions, needed for probabilistic norm bounds.The walk count uses at most 2^(j-s)(jDV)^s choices for j steps with s slack steps.Source: §3.5 · pp. 46–48
  • For a slack step, any backbone-correction shape τ may be chosen, yielding a BVar(M) factor.The displayed expression for the factor is truncated in the supplied passage.Source: §3.5 · p. 48

4 Chebyshev Polynomials via Shape Concatenation

This section develops a shape-concatenation approximation connecting Chebyshev polynomials of graph-matrix linear combinations and backbone-correction matrices to concatenated shapes. It bounds errors from nontrivial intersections, handles corrections with small-norm bounds, and bounds contributions from disconnected shapes not captured by the polynomials.

4.1 Intuition From Block Walks

  • Constant-norm products are compositions of backbone-correction shapes, or two disconnected compositions anchored at the starting and ending vertices; block walks without slack use F, R, and R′ steps.Such walks maintain either one path from the starting vertex to the current vertex or multiple disjoint paths, with the first beginning at the start and the most recent ending at the current vertex.Source: §4.1 · pp. 50–51

4.2 Products of Backbone-Correction Shapes

  • Theorem 4.7 gives approximations for products of backbone-correction matrices by specified shape concatenations.The theorem states that the differences between the two sides are bounded with high probability.Source: §4.2 · p. 52
  • Non-main intersection patterns are controlled by trace-power bounds: consistency forces slack blocks, which yield small-norm error terms.In particular, when the reduced shape has a connected component detached from both endpoints, consistency requires at least 2q slack blocks.Source: §4.2 · pp. 52, 54, 55
  • Disconnected shapes have small-norm corrections for constant-norm terms not captured by the Chebyshev polynomials.The claim concerns shapes α formed from concatenated components with |V(α)| ≤ D_V.Source: §4.2 · pp. 55–56

4.3 Equivalence of Chebyshev Polynomials and Concatenated Shapes

  • For every j ≥ 1, P_j(M) is formally equivalent to concatenated shapes up to Error(j), which admits a small-norm correction satisfying the RW constraints.The result assumes M is a symmetric linear combination of backbone-correction shapes with normalized variance 1.Source: §4.3 · p. 56
  • The connected constant-norm terms that do not cancel are precisely the j-wise concatenations, and their coefficient magnitudes in P_j(M) sum to at most (4B)^j.The proof establishes the coefficient bound inductively using the Chebyshev recurrence and the fact that multiplication by M creates at most three constant-norm terms per term.Source: §4.3 · p. 56
  • With high probability, ||M|| is (2+o_n(1)).This norm bound is used to control how multiplication by M increases the norm of lower-order error terms.Source: §4.3 · p. 57
  • The proof considers at most (D_V)^(4D_V) pairs of concatenation prefixes and next shapes when union-bounding the probabilities of norm-bound failures.Source: §4.3 · p. 57

A Equivalence of Lower and Upper Bounds for the Theta Function on G(n, 1

The appendix converts a dual-feasible matrix with objective λ into a degree-2 SoS pseudo-expectation of value n/λ, yielding a lower bound on the Lovász-Theta function. The construction uses uniform vertex weights, a symmetry condition that general solutions need not satisfy.

A Equivalence of Lower and Upper Bounds for the Theta Function on G(n, 1

  • The constructed pseudo-expectation assigns uniform weights across vertices, a symmetry condition that general degree-2 SoS moment matrices need not satisfy when converted to theta dual witnesses.The passage notes that a known lower bound of √n does not ensure this symmetry, motivating an explicit construction that can also yield an upper-bound witness.Source: A Equivalence of Lower and Upper… · p. 62
  • A dual-feasible matrix with objective λ yields a valid degree-2 SoS pseudo-expectation for Maximum Clique with value n/λ.The construction verifies positive semidefiniteness, Booleanity, symmetry, and the clique constraints.Source: A Equivalence of Lower and Upper… · pp. 62–64
  • With high probability, this construction implies ϑ(G) ≥ n/λ for G sampled from G(n, 1/2), using the equivalent degree-2 SoS formulation for independent set.The argument transfers the clique pseudo-expectation to the complement graph, whose samples have the same distribution.Source: A Equivalence of Lower and Upper… · p. 64

B Formal Verification of the Dual Witness Matrix

The formal verification constructs a corrected matrix whose diagonal can be normalized to satisfy the non-edge constraints. It accounts separately for corrections from the iterative process, Chebyshev expansion, and early termination.

B Formal Verification of the Dual Witness Matrix

  • After normalization, the corrected matrix satisfies the non-edge constraints.The matrix has diagonal C_F + ϵ, so division by C_F + ϵ gives the required constraints.Source: B Formal Verification of the Dual… · pp. 64–65
  • The correction sum combines Chebyshev-expansion errors with an early-termination correction, whose norm is bounded separately.The early-termination correction handles terms involving the final update, while the Chebyshev correction cancels the expansion error on the diagonal and nonedges.Source: B Formal Verification of the Dual… · pp. 64–65
  • Terms from earlier iterations satisfy the non-edge constraint because they are backbone-correction shapes for concatenations using pre-update shapes.The proof separates these terms from those involving the final update.Source: B Formal Verification of the Dual… · pp. 64–65

Picking the Final Parameters

The parameter choice sets the termination level to D and uses truncation to bound the sizes of shapes and corrections through degree D. Separately, the variance recurrence is shown to converge to 1 without truncation.

Picking the Final Parameters

  • Setting t*=D and ϵ=n^-1 makes the truncation bound base-shape sizes by D^D + 1 vertices, controlling products and corrections through degree D.The passage states that variance normalization and a cited lemma provide a further estimate, but its value is not recoverable from the supplied text.Source: Picking the Final Parameters · p. 66

C.1 Evolution of the Variance of Qi

  • The recurrence is obtained by summing the squared mass of newly added concatenations, then shown to contract toward 1.The proof derives a contraction constant from the coefficients and uses a partial-fraction identity in the convergence argument.Source: §C.1 · pp. 67–68

C.2 Quantitative Convergence of the Variance of Qi

The variance process converges exponentially fast to 1. The outer truncation is analyzed through approximate positive semidefiniteness when the spectrum lies in a slightly enlarged interval.

C.2 Quantitative Convergence of the Variance of Qi

  • The variance process satisfies S_t → 1 exponentially fast, with γ chosen as β = 16/π^2 − 1 < 1.The proof also uses 1 − x^j ≤ j(1 − x).Source: §C.2 · pp. 69–70

D.1 Spectral Impact of Outer Truncation of FD

  • For spec(Q̃) ⊆ [−2 − δ, 2 + δ], Proposition D.3 establishes approximate positive semidefiniteness of F_D(Q̃).The proof combines a lower bound for F_D within [−2, 2] with a bound on deviations beyond the endpoints, then applies functional calculus.Source: §D.1 · p. 70
  • Within [−2, 2], the proof bounds F_D(x) below by −Õ(1/D), while controlling its deviation from the boundary values outside that interval.The outside deviation is bounded in terms of δ, a polynomial in D, and an exponential factor.Source: §D.1 · p. 70

D.2 Truncation Error within the Support

The truncation analysis establishes uniform convergence of the polynomial partial sums to F and develops bounds within the support and at its edges. It also treats tails of squared coefficients.

D.2 Truncation Error within the Support

  • The polynomial partial sums converge uniformly to F, and the proof gives an O(1/D) bound within the support.The coefficients satisfy b_2k = (−1)^(k−1)a_k, a_k = 8/[π(2k−1)(2k+3)], and b_2k+1 = 0.Source: §D.2 · p. 71

D.3 Deviation at the Edge

  • The edge-deviation proof uses Parseval’s identity for the second-kind polynomials, which are orthonormal under the semicircle measure.The positive-edge bound is established first; the negative edge is reduced to it using U_j(−x) = (−1)^jU_j(x).Source: §D.3 · p. 72

D.4 Tail Bound for Correction Terms

  • Lemma D.5 gives a tail bound on squared coefficients, derived by changing variables to x = 2 cos θ and evaluating the resulting integral.The proof uses P_j(2 cos θ) = sin((j + 1)θ) and the piecewise definition of F.Source: §D.4 · pp. 73–74

D.5 ℓ1 Bound for Normalized Coefficients

The section bounds the number of backbone-correction shapes exponentially in their size and relates that count to the normalized-coefficient analysis. It also gives a growth condition under which the resulting count is at most n^δ.

D.5 ℓ1 Bound for Normalized Coefficients

  • C^DD ≤ n^δ when D = O_C,δ(log log n · log log log n), for any δ > 0.The remark states this growth condition for the shape-count bound.Source: §D.5 · p. 74
  • The number of backbone-correction shapes on at most T vertices is at most C^T for an absolute constant C > 1.The counting argument encodes shapes as noncrossing arc sets and bounds their number using Catalan numbers.Source: §D.5 · pp. 74–75
  • For C = 9, the total number of backbone-correction shapes on at most T vertices is at most C^T.The shape count is used in the section’s normalized-coefficient analysis.Source: §D.5 · pp. 74–75

D.6 Truncated Variance

The truncated recursion is parameterized by its initial variance so it reaches variance 1 at a prescribed level. The section also studies monotonicity and the squared coefficient mass omitted by early termination.

D.6 Truncated Variance

  • For the chosen initial variance, S_t*(a_t*,D) = 1, and the variance process is nondecreasing in i.The recursion is degree-D truncated and initialized for c_γ ≥ 0.Source: §D.6 · pp. 75, 77
  • The section separately bounds the squared coefficient mass of the update omitted by terminating at level t*.The proof invokes R_D = O(D^−3) and β^i = O(i^−3).Source: §D.6 · pp. 75–76
  • For fixed i, S_i(a) is continuous and strictly increasing in its initial-variance parameter, yielding a unique choice that reaches variance 1 at t*.The proof establishes this using the recurrence for the variance increments restricted to degrees j ≤ D.Source: §D.6 · pp. 76–77

E Initial Attempt with a Constant Improvement

The initial construction uses freely independent correction shapes to control the correction norm and achieve an upper bound of approximately 1.388 by numerical optimization.

E Initial Attempt with a Constant Improvement

  • The clique constraints require an added correction whose shapes are freely independent.The main theorem estimates its norm as approximately twice the square root of the sum of squared shape coefficients.Source: E Initial Attempt with a Constant… · p. 78
  • Making the overall matrix positive semidefinite requires adding an approximate identity-matrix term with a squared-coefficient expression.The expression is (b^2 + c^2 + 2ac − 2ad)^2 + 4b^2c^2 + 2b^2d^2 + 2c^2d^2 + d^4.Source: E Initial Attempt with a Constant… · p. 78
  • 0.7204 by numerical optimization corresponds to an upper bound of approximately 1.388.The maximizing direction achieves the same value.Source: E Initial Attempt with a Constant… · p. 78

F Equivalence of Lov´asz-Theta and Degree 2 Sum of Squares for Independent Set

Appendix F shows that the Lovász-Theta SDP and the degree-2 sum-of-squares relaxation for independent set have the same value. It also establishes that fixing the independent-set size at k gives the same maximum k as maximizing the size directly.

F Equivalence of Lováz-Theta and Degree 2 Sum of Squares for Independent Set

Related papers

Loading 2609.30064v1…