Pith. sign in

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 →

arxiv 2608.01716 v1 pith:PLU6Y5YL submitted 2026-08-03 math.CO

classification math.CO MSC 05C1505C2205C5090C22
keywords signedgraphsbalancedcolouringthetafunctionbodysemidefiniteprogrammingconflictgraphperfectnessmaximuminducedbipartitesubgraph
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper extends the theta function of ordinary graphs to signed graphs, where the relevant object is no longer a stable set but a balanced set: a vertex set whose induced signed graph has no negative cycle. The scalar parameter ϑ_b(Σ) is defined by mapping vertices to a sphere with an orthogonal involution, so that switching at a vertex becomes reflecting one endpoint; the paper proves ϑ_b(Σ)=1/2 ϑ(C(Σ)), where C(Σ) is the ordinary conflict graph of negative edges of the double switching graph. On the body level, the paper defines BTH(Σ) as the projection of the ordinary theta body TH(C(Σ)) back onto the original signed vertex space, gives it an intrinsic two-matrix semidefinite description, and shows it sits between the balanced induced subgraph polytope and a projected clique relaxation. This gives a signed sandwich theorem, recovers the classical stable-set-theta-clique hierarchy on digon graphs, and specializes to a semidefinite bound for the maximum induced bipartite subgraph in the all-negative case. A reader should care because the paper supplies a unified, computable convex-geometric framework for balanced colouring, parallel to the role the theta function plays for ordinary colouring.

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(Σ)).

Watch

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

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 4 minor

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)
  1. [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.
  2. [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.
  3. [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.
  4. [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

0 steps flagged · score 0.0 of 10

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 0 free parameters · 5 assumptions · 3 invented entities

The paper introduces no fitted parameters: t is the optimization variable of the SDP, and the target dimension H is existential. The constructions rest on standard published results (Harary balance, ordinary theta theory, SDP duality) plus the explicit positive-loop convention. Invented objects (S_t, ϑ_b, BTH) are validated by exact identities against the external theta theory.

assumptions (5)
  • standard math Harary's characterization of balance: a signed graph is balanced iff switchable to all-positive (Thm 2.1, §2.1).
    Used in Prop 3.3 and Prop 5.1 to convert balanced sets into sign labelings.
  • standard math Balanced p-colouring iff signed homomorphism to B_p (Prop 2.2, §2.2).
    Justifies the chromatic-side interpretation of ϑ_b; proof given in the paper.
  • 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).
    External benchmarks used to prove the identities.
  • domain assumption Positive-loop completion convention: every signed graph is replaced by Σ+ℓ, with positive loops not affecting balance (§2.1).
    Load-bearing: creates the vertical edges in C(Σ), used in Prop 5.1, Thm 6.1, and Thm 7.2.
  • standard math Standard SDP strong duality for the primal-dual pair (P_Σ)/(D_Σ) (Thm 4.2).
    Used to assert equality and attainment; strict feasibility of the dual is exhibited in the proof.
invented entities (3)
  • signed spherical graph S_t(H,R) independent evidence
    purpose: homomorphism target realizing switching via an orthogonal involution
    The object is new to this paper and is validated by the two-vector reformulation (Thm 3.6) and the SDP duality (Thms 4.1-4.2) against the standard theta framework.
  • balanced Lovász theta parameter ϑ_b(Σ) independent evidence
    purpose: SDP bound for balanced colouring
    Shown to equal half the theta of the external conflict graph C(Σ) (Thm 6.1), giving an independent, computable handle.
  • balanced theta body BTH(Σ) and associated bodies BSTAB, BQSTAB independent evidence
    purpose: signed analogue of the theta-body hierarchy
    Has an intrinsic two-Gram description (Thm 7.2), satisfies the signed sandwich theorem, and recovers STAB/TH/QSTAB on digon graphs (Thm 7.5).

how reviews work

0 comments
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.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

  1. [1]

    Facets of the balanced (acyclic) induced subgraph polytope.Mathematical Programming, 45(1–3):21–33, 1989

    Francisco Barahona and Ali Ridha Mahjoub. Facets of the balanced (acyclic) induced subgraph polytope.Mathematical Programming, 45(1–3):21–33, 1989

  2. [2]

    Compositions of graphs and polyhedra I: Balanced induced subgraphs and acyclic subgraphs.SIAM Journal on Discrete Mathematics, 7(3):344–358, 1994

    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

  3. [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

  4. [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

  5. [5]

    Brewster and Timothy Graves

    Richard C. Brewster and Timothy Graves. Edge-switching homomorphisms of edge-coloured graphs.Discrete Mathematics, 309(18):5540–5546, 2009

  6. [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

  7. [7]

    Springer, Berlin, 1988

    Martin Grötschel, László Lovász, and Alexander Schrijver.Geometric Algorithms and Combi- natorial Optimization. Springer, Berlin, 1988

  8. [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

Show all 20 references
  1. [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

  2. [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

  3. [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

  4. [12]

    Donald E. Knuth. The sandwich theorem.Electronic Journal of Combinatorics, 1:Research Paper 1, 1994

  5. [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

  6. [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

  7. [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

  8. [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

  9. [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

  10. [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

  11. [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

  12. [20]

    Signed graphs.Discrete Applied Mathematics, 4(1):47–74, 1982

    Thomas Zaslavsky. Signed graphs.Discrete Applied Mathematics, 4(1):47–74, 1982. 18

Pith tools

Reviewed August 4, 2026 · model on record in the stance chip above.