REVIEW 4 minor 20 references
A Lov\'asz Theta Parameter and Theta Body for Signed Graphs
T0 review · 0 major / 4 minor · reviewed 2026-08-04 · deepseek-v4-flash
Pith's one-line read The paper proves that balanced colouring of signed graphs has its own theta parameter, equal to half the theta number of the conflict graph, and that the full theta-body hierarchy transfers to this setting.
desk verdict A clean, well-executed signed analogue of Lovász theta and its body; the positive-loop convention is load-bearing but explicit, and the core results hold up. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the signed spherical graph S_t(H,R): a unit sphere split into fixed and anti-fixed subspaces of an orthogonal involution R, restricted to the latitude ⟨x,Rx⟩=γ_t=1/(1-2t). Negative adjacency is ⟨x,y⟩=γ_t, positive adjacency is ⟨x,Ry⟩=γ_t; applying R to one endpoint swaps the relations, realizing switching. The parameter's SDP form is (P_Σ): two positive semidefinite matrices X,Y with diagonals t-1 and t and edge constraint X_uv-σ(uv)Y_uv=-1. The identity ϑ_b=1/2 ϑ(C(Σ)) comes from the block matrix [[X+Y,X-Y],[X-Y,X+Y]], which block-diagonalizes to 2X⊕2Y and is feasible for the ordinary theta program of C(Σ). The body machinery is the projection p from conflict-graph ver
What would settle it
Solve the primal SDP (P_Σ) numerically for the all-negative triangle (K_3,−), for which the paper predicts ϑ_b=3/2; check whether the optimum is 3/2 and whether the optimal matrices X,Y average to a feasible ordinary theta matrix for the triangular prism C(Σ) at value 3. A different optimum, or a primal-dual gap despite strict feasibility, would falsify the two-matrix formulation and the identity ϑ_b=1/2 ϑ(C(Σ)).
Extended reading notes
Core claim
Central claim: balanced colouring of signed graphs has a semidefinite analogue of the theta hierarchy. ϑ_b(Σ) is the least t for which Σ maps to a sphere S_t(H,R) with an orthogonal involution R, where negative adjacency is ⟨x,y⟩=γ_t, positive adjacency is ⟨x,Ry⟩=γ_t, and applying R to one endpoint realizes switching. The main identity is ϑ_b(Σ)=1/2 ϑ(C(Σ)), with C(Σ) the conflict graph of local switching states (v,±). On the body level, BTH(Σ)=p(TH(C(Σ))) has an intrinsic two-matrix semidefinite description, and the paper proves BSTAB⊆BTH⊆BQSTAB with all-ones gauge exactly ϑ_b. In the all-negative case this bounds the maximum induced bipartite subgraph; on digon graphs it recovers the ordin
Load-bearing premise
The paper assumes every signed graph is tacitly given a positive loop at every vertex, and the main identities depend on those loops creating the vertical edges of the conflict graph; without that convention the equality ϑ_b(Σ)=1/2 ϑ(C(Σ)) and the body descriptions would not hold as stated.
Editorial extensions
If this is right
- Every signed graph receives a polynomial-time computable parameter ϑ_b(Σ) sandwiched between half the largest antibalanced clique and the fractional balanced chromatic number, so it can serve as an SDP lower bound for balanced colouring.
- The theta body BTH(Σ) gives a semidefinite relaxation of the maximum-weight balanced induced subgraph problem, with the all-ones gauge of the body precisely ϑ_b(Σ); feasible SDP solutions provide separating inequalities for that polytope.
- On signed digon graphs the signed hierarchy reproduces the ordinary STAB, TH, and QSTAB bodies exactly, so the construction is a genuine extension rather than an analogous-but-different gadget.
- For all-negative signatures, BTH(-G) relaxes the maximum induced bipartite subgraph polytope and its maximum over the cube equals ϑ(K_2 □ G), placing the construction next to the generalized theta number for maximum k-colourable induced subgraphs.
- Balanced perfectness is strictly weaker than perfectness of the conflict graph: the paper exhibits a four-vertex signed graph whose signed theta body is already its balanced subgraph polytope even though its conflict graph contains an induced odd hole.
Reading between the lines
- My inference: because ϑ_b(Σ)=1/2 ϑ(C(Σ)) identifies the signed parameter with an ordinary theta number, ϑ_b inherits homomorphism monotonicity and the disjoint-union max rule; a natural next test is whether ϑ_b also satisfies a signed analogue of the Shannon-capacity-type bound for the balanced chromatic number.
- My inference: the scalar optimum forgets the ranks of the fixed and anti-fixed Gram blocks, which are exactly the degrees of freedom used in signed Kneser, Schrijver, and Borsuk-type arguments; a rank-aware refinement of BTH could give strictly stronger bounds for those graphs.
- My inference: the theorem that perfectness of C(Σ) is sufficient but not necessary suggests the projection p can erase odd holes; chordal signed graphs or signed graphs with no odd balanced cycles might form classes where BTH is polyhedral even when C(Σ) is imperfect.
- My inference: since the positive-loop completion generates the vertical conflict edges, a loopless variant of the theory would change the conflict graph and likely change ϑ_b; testing the SDP on signatures without the loop convention would delimit exactly how much of the hierarchy depends on that convention.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces a signed analogue of the Lovász theta parameter and theta body. The parameter ϑ_b(Σ) is defined homomorphically via a signed spherical graph S_t(H,R) carrying an orthogonal involution, and is characterized by a two-matrix SDP (PΣ) with a symmetric dual (DΣ). The central structural result is Theorem 6.1, ϑ_b(Σ) = 1/2 ϑ(C(Σ)), where C(Σ) is the conflict graph constructed from the negative edges of the double switching graph, taken after the explicitly stated positive-loop completion. The paper then defines the balanced theta body BTH(Σ) as the projection of TH(C(Σ)) onto the original vertex space, gives an intrinsic two-matrix description (Theorem 7.2), proves the signed sandwich theorem BSTAB ⊆ BTH ⊆ BQSTAB, and shows the all-ones gauge of BTH equals ϑ_b(Σ). It recovers the classical STAB/TH/QSTAB hierarchy on digon graphs, specializes the all-negative case to a relaxation of maximum induced bipartite subgraph with bound ϑ(K2 □ G), and proposes a notion of balanced perfectness, showing it is strictly weaker than perfectness of C(Σ) by an explicit four-vertex example.
Significance. If correct, this is a substantial and well-motivated extension of classical theta theory to signed graphs. The paper provides a complete homomorphic/SDP framework with strong duality, an exact block-diagonalization identification with an ordinary theta number, and a body-level hierarchy that recovers the ordinary one under digon specialization. The proofs are self-contained and checkable; I verified the core derivations in Theorems 3.6, 4.1–4.2, 6.1, and 7.2 and found them sound. The paper is careful about its conventions, especially the positive-loop completion (Section 2.1), which is load-bearing for the conflict graph construction but explicitly stated and consistently applied. The all-negative specialization and the balanced-perfectness example provide concrete, falsifiable tests of the framework. The manuscript is a strong contribution to signed graph theory and semidefinite optimization.
minor comments (4)
- [Section 2.3] The sentence 'We write ϑ(G) := ϑ(G)' is a tautology and appears to be a typo. Please clarify that ϑ(G) denotes the strict vector chromatic number, which is known to equal the Lovász theta number.
- [Theorem 6.1 proof] The proof says 'order the vertices of C(Σ) by the two fibres.' To make the block form of M unambiguous, specify the ordering explicitly, e.g., all '+' states first, then all '−' states.
- [Theorem 8.2] The proof quantifies over all induced subgraphs U when showing that perfectness of C(Σ) implies balanced-perfectness. Since balanced-perfectness is defined only for the whole graph, taking U = V suffices; the current wording may suggest an unstated hereditary property.
- [Proposition 7.4] The equivalence between 1/λ ∈ BTH(Σ) and 1/(2λ)1 ∈ TH(C(Σ)) is stated tersely. A one-sentence justification—namely, averaging the lifting vector under the fibre involution—would improve readability.
Circularity Check
No significant circularity
full rationale
The paper's central objects are defined independently of the claims made about them. The balanced theta parameter ϑ_b(Σ) is introduced as a signed-homomorphism invariant to a spherical target with an orthogonal involution (Section 3), and it is given a standalone two-matrix SDP formulation (Theorem 4.1). The conflict graph C(Σ) is defined independently as the negative-edge graph of the double switching graph (Section 5). Theorem 6.1, ϑ_b(Σ)=1/2ϑ(C(Σ)), is proved by an explicit block-diagonalization argument relating the two SDPs, not by fitting constants to a target value. The theta body BTH(Σ) is defined as the projection of the ordinary theta body TH(C(Σ)), and its intrinsic two-matrix description (Theorem 7.2) is derived from that definition rather than assumed. The recovery results for digon graphs and the all-negative specialization compare against external, previously established Lovász theta facts; they are benchmarks, not circular inputs. The positive-loop completion convention is explicitly stated in Section 2.1 and is used consistently, but it is a stated convention rather than a hidden premise that makes the conclusions equivalent to the definitions. No load-bearing self-citations occur: the citations to [14] and other prior work are external and independent of the present author's claims. No fitted input is renamed as a prediction, and no uniqueness theorem from the author's own work is invoked. The claimed derivation chain is therefore self-contained and non-circular.
Assumptions & free parameters
assumptions (5)
- standard math Harary's characterization of balance: a signed graph is balanced iff switchable to all-positive (Thm 2.1, §2.1).
- standard math Balanced p-colouring iff signed homomorphism to B_p (Prop 2.2, §2.2).
- standard math Standard facts about the Lovász theta function: sandwich theorem, SDP primal-dual pair (1)-(2), gauge identity ϑ(G)=γ_TH(1), and ϑ(G ∪ H)=max(ϑ(G),ϑ(H)) (§2.3, used in Cor 6.4).
- domain assumption Positive-loop completion convention: every signed graph is replaced by Σ+ℓ, with positive loops not affecting balance (§2.1).
- standard math Standard SDP strong duality for the primal-dual pair (P_Σ)/(D_Σ) (Thm 4.2).
invented entities (3)
-
signed spherical graph S_t(H,R)
independent evidence
-
balanced Lovász theta parameter ϑ_b(Σ)
independent evidence
-
balanced theta body BTH(Σ) and associated bodies BSTAB, BQSTAB
independent evidence
Cite this review
Pith. "Pith review of A Lov\'asz Theta Parameter and Theta Body for Signed Graphs." pith.science (2026). https://pith.science/paper/PLU6Y5YL
@misc{pith2026260801716,
author = {Pith},
title = {Pith review of: A Lov\'asz Theta Parameter and Theta Body for Signed Graphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/PLU6Y5YL}},
note = {Machine review of arXiv:2608.01716}
}
read the original abstract
We introduce a Lov\'asz-type semidefinite parameter for balanced colouring of signed graphs. Its homomorphism target is a unit sphere equipped with an orthogonal involution: the fixed and anti-fixed components play different roles, while applying the involution to one endpoint realizes switching. The resulting parameter admits a symmetric formulation with two positive semidefinite matrices and an equally symmetric dual. It is also one half of the strict vector chromatic number of the ordinary graph formed by the negative edges of the double switching graph. Our second main contribution is a hierarchy of convex corners. Starting from the balanced induced subgraph polytope, we define signed analogues of the stable-set, theta, and clique-inequalities relaxations in the original vertex space. The signed theta body has an intrinsic two-matrix description, its all-ones gauge is the new scalar parameter, and the ordinary stable-set hierarchy is recovered exactly from signed digon graphs. For all-negative signatures, the construction becomes a relaxation of the maximum induced bipartite subgraph problem and is related to the generalized theta number. Finally, we propose a notion of balanced perfectness and show that it is strictly weaker than perfectness of the associated double-cover graph.
Reference graph
Works this paper leans on
-
[1]
Francisco Barahona and Ali Ridha Mahjoub. Facets of the balanced (acyclic) induced subgraph polytope.Mathematical Programming, 45(1–3):21–33, 1989
work page 1989
-
[2]
Francisco Barahona and Ali Ridha Mahjoub. Compositions of graphs and polyhedra I: Balanced induced subgraphs and acyclic subgraphs.SIAM Journal on Discrete Mathematics, 7(3):344–358, 1994
work page 1994
-
[3]
Improved semidefinite programming bounds for the maximum $k$-colorable subgraph problem
Mathijs Barkel and Renata Sotirov. Improved semidefinite programming bounds for the maximumk-colorable subgraph problem, 2026. Preprint, arXiv:2605.02456
work page Pith review arXiv 2026
-
[4]
Brewster, Florent Foucaud, Pavol Hell, and Reza Naserasr
Richard C. Brewster, Florent Foucaud, Pavol Hell, and Reza Naserasr. The complexity of signed graph and edge-coloured graph homomorphisms.Discrete Mathematics, 340(2):223–235, 2017
work page 2017
-
[5]
Richard C. Brewster and Timothy Graves. Edge-switching homomorphisms of edge-coloured graphs.Discrete Mathematics, 309(18):5540–5546, 2009
work page 2009
-
[6]
Roberson, Brendan Rooney, Robert Šámal, and Antonios Varvitsiotis
Chris Godsil, David E. Roberson, Brendan Rooney, Robert Šámal, and Antonios Varvitsiotis. Graph homomorphisms via vector colorings.European Journal of Combinatorics, 79:244–261, 2019
work page 2019
-
[7]
Martin Grötschel, László Lovász, and Alexander Schrijver.Geometric Algorithms and Combi- natorial Optimization. Springer, Berlin, 1988
work page 1988
-
[8]
On the notion of balance of a signed graph.Michigan Mathematical Journal, 2:143–146, 1953–1954
Frank Harary. On the notion of balance of a signed graph.Michigan Mathematical Journal, 2:143–146, 1953–1954. 17
work page 1953
Show all 20 references
-
[9]
Fractional balanced chromatic number of signed subcubic graphs.Discrete Mathematics, 349(9):115112, 2026
Xiaolan Hu, Luis Kuffner, Jiaao Li, Reza Naserasr, Lujia Wang, Zhouningxin Wang, and Xiaowei Yu. Fractional balanced chromatic number of signed subcubic graphs.Discrete Mathematics, 349(9):115112, 2026
2026
-
[10]
Andrea Jiménez, Jessica McDonald, Reza Naserasr, Kathryn Nurse, and Daniel A. Quiroz. Balanced Chromatic Number and Hadwiger-Like Conjectures.Discrete Applied Mathematics, 389:135–143, 2026
2026
-
[11]
Approximate graph coloring by semidefinite programming.Journal of the ACM, 45(2):246–265, 1998
David Karger, Rajeev Motwani, and Madhu Sudan. Approximate graph coloring by semidefinite programming.Journal of the ACM, 45(2):246–265, 1998
1998
-
[12]
Donald E. Knuth. The sandwich theorem.Electronic Journal of Combinatorics, 1:Research Paper 1, 1994
1994
-
[13]
Colouring Signed Analogues of Kneser, Schrijver, and Borsuk Graphs, 2025
Luis Kuffner, Reza Naserasr, Lujia Wang, Xiaowei Yu, Huan Zhou, and Xuding Zhu. Colouring Signed Analogues of Kneser, Schrijver, and Borsuk Graphs, 2025. Preprint, arXiv:2412.20001, revised 2025
2025 arXiv
-
[14]
Fractional balanced coloring of signed graphs, 2026
Luis Kuffner, Reza Naserasr, Lujia Wang, Xiaowei Yu, Huan Zhou, and Xuding Zhu. Fractional balanced coloring of signed graphs, 2026. Preprint, HAL: hal-05648556
2026
-
[15]
Olga Kuryatnikova, Renata Sotirov, and Juan C. Vera. The maximumk-colorable subgraph problem and related problems.INFORMS Journal on Computing, 34(1):656–669, 2022
2022
-
[16]
On the Shannon Capacity of a Graph.IEEE Transactions on Information Theory, 25(1):1–7, 1979
László Lovász. On the Shannon Capacity of a Graph.IEEE Transactions on Information Theory, 25(1):1–7, 1979
1979
-
[17]
Homomorphisms of signed graphs.Journal of Graph Theory, 79(3):178–212, 2015
Reza Naserasr, Edita Rollová, and Éric Sopena. Homomorphisms of signed graphs.Journal of Graph Theory, 79(3):178–212, 2015
2015
-
[18]
Homomorphisms of signed graphs: An update.European Journal of Combinatorics, 91:103222, 2021
Reza Naserasr, Éric Sopena, and Thomas Zaslavsky. Homomorphisms of signed graphs: An update.European Journal of Combinatorics, 91:103222, 2021
2021
-
[19]
On the generalizedϑ-number and related problems for highly symmetric graphs.SIAM Journal on Optimization, 32(2):1344–1378, 2022
Lennart Sinjorgo and Renata Sotirov. On the generalizedϑ-number and related problems for highly symmetric graphs.SIAM Journal on Optimization, 32(2):1344–1378, 2022
2022
-
[20]
Signed graphs.Discrete Applied Mathematics, 4(1):47–74, 1982
Thomas Zaslavsky. Signed graphs.Discrete Applied Mathematics, 4(1):47–74, 1982. 18
1982
Reviewed August 4, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.