pith. sign in

arxiv: 2605.02484 · v1 · submitted 2026-05-04 · 🧮 math.AG

The Algebraic Boundary of Graph Elliptopes

Monique Laurent , Francesco Maria Mascarin , Simon Telen This is my paper

Pith reviewed 2026-05-08 18:00 UTC · model grok-4.3

classification 🧮 math.AG
keywords algebraic boundarygraph elliptopecycle polynomialLissajous varietydeterminantal hypersurfacechordal graphspectrahedronresultant
0
0 comments X

The pith

When a graph is cycle completable, the algebraic boundary of its elliptope is the union of determinantal hypersurfaces and Lissajous varieties.

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

The paper establishes a complete description of the algebraic boundary of the elliptope associated to a graph G, but only when G is cycle completable. In this setting the boundary consists of determinantal hypersurfaces together with Lissajous varieties, which arise as images of linear subspaces under the coordinatewise cosine map. This characterization relies on the cycle polynomial, shown to be the resultant of two smaller cycle polynomials, yielding an inductive computation that also determines its degree. A key consequence is that the algebraic boundary meets the interior of the elliptope if and only if the graph is not chordal, in which case the elliptope fails to be a spectrahedron.

Core claim

For cycle-completable graphs the algebraic boundary of E(G) is a union of determinantal hypersurfaces and Lissajous varieties. The cycle polynomial of a cycle graph C_n is the resultant of the cycle polynomials of two smaller cycles, providing both an explicit equation and a degree formula that resolves an earlier question. Consequently the algebraic boundary is disjoint from the interior precisely when G is chordal.

What carries the argument

The cycle polynomial, which gives the defining equation of the algebraic boundary for the elliptope of any cycle graph C_n, together with the resultant recursion relating it to the cycle polynomials of two smaller cycles.

If this is right

  • The algebraic boundary of E(G) lies entirely outside the interior if and only if G is chordal.
  • E(G) is a spectrahedron if and only if G is chordal.
  • The degree of the homogeneous cycle polynomial of C_n is given by an explicit formula obtained inductively.
  • Sylvester's determinantal formula supplies an inductive algorithm for computing the cycle polynomial that mirrors a geometric recursion on metric polytopes.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • For graphs that are not cycle completable the algebraic boundary may contain additional irreducible components beyond determinantal hypersurfaces and Lissajous varieties.
  • The inductive structure on cycle polynomials could be used to derive similar recursive formulas for algebraic boundaries of other families of spectrahedra or convex bodies.
  • Numerical sampling of points near the boundary for small non-chordal graphs could test whether new hypersurface components appear when the cycle-completable hypothesis is dropped.

Load-bearing premise

That the cycle polynomial fully captures the algebraic boundary of the elliptope of any cycle graph C_n and that the resultant recursion preserves the geometric properties needed for the global characterization of cycle-completable graphs.

What would settle it

An explicit computation showing that the algebraic boundary of E(G) for some cycle-completable graph G is not a union of determinantal hypersurfaces and Lissajous varieties would falsify the characterization.

Figures

Figures reproduced from arXiv: 2605.02484 by Francesco Maria Mascarin, Monique Laurent, Simon Telen.

Figure 1
Figure 1. Figure 1: Three slices of E(C4) (second row) and the corresponding slices of VR(Γ4) (third row) at x4 = 0, 1 2 , 1, together with the matching slices of MET(C4) at 1 π arccos x4 = 1 2 , 1 3 , 0 (first row). 3 view at source ↗
Figure 2
Figure 2. Figure 2: The cycle Cn is obtained by deleting the common edge e0 from Cp and C ′ q . Proof. By Lemma 3.4, it suffices to show that the degree of hn as a bivariate polynomial in xe0 , xe1 is equal to 2 n−1 . The proof is analogous to that of Proposition 3.6, only a bit more technical. Set F = En \ {e0, e1} and assume that e0, e1 come first and second in the ordering of En used in the subscript of zϵ. We start from t… view at source ↗
Figure 3
Figure 3. Figure 3: With e0 = {1, 3}, the graph C4 + e0 is the union of C3 = (1, 2, 3) and C ′ 3 = (3, 4, 1), while C5 + e0 is the union of C3 = (1, 2, 3) and C ′ 4 = (3, 4, 5, 1). 4 × 4 Sylvester determinant, using Γ3 (which was computed in Example 3.8): Γ4 = det   −1 + x 2 12 + x 2 23 −2x12x23 1 0 0 −1 + x 2 12 + x 2 23 −2x12x23 1 −1 + x 2 14 + x 2 34 −2x14x34 1 0 0 −1 + x 2 14 + x 2 34 −2x14x34 1   . Similarly, f… view at source ↗
Figure 4
Figure 4. Figure 4: On the left, the 3-D slices of V (Γ4) (in yellow) and V (Γ∇ 4 ) (in red) at x01 = . . . = x04 = x14 = 1 2 ; on the right, the 2-D slices of E(W5) (in red) and its superset eE(W5) (in yellow) at x01 = . . . = x04 = x14 = 1 2 and x12 = x23 (discussed in Example 4.15). Proof. We combine Corollary 4.11 and Proposition 4.13. By Corollary 4.11, the algebraic boundary of C (G) is the vanishing set of the polynomi… view at source ↗
read the original abstract

This paper studies the algebraic boundary of the elliptope $\mathcal{E}(G)$ of a graph $G$. In particular, we completely characterize the algebraic boundary of $\mathcal{E}(G)$ when $G$ is cycle completable. In this case, the boundary is a union of determinantal hypersurfaces and Lissajous varieties, i.e., images of rational linear subspaces under the coordinatewise cosine map. As an application, we show that the algebraic boundary of $\mathcal{E}(G)$ is disjoint from its interior precisely when $\mathcal{E}(G)$ is a spectrahedron or, equivalently, when $G$ is a chordal graph. A central ingredient for the defining equation of the boundary hypersurface is the cycle polynomial, which captures the algebraic boundary of the elliptope $\mathcal{E}(C_n)$ of the $n$-th cycle graph $C_n$. We show that the cycle polynomial of $C_n$ is the resultant of two smaller cycle polynomials. Via this result, Sylvester's determinantal formula offers an inductive method for computing the cycle polynomial which mirrors a geometric property of metric polytopes. We also determine the degree of the homogeneous cycle polynomial, settling an open question of Sturmfels and Uhler (2010).

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper claims a complete characterization of the algebraic boundary of the elliptope E(G) for cycle-completable graphs G, describing it as the union of determinantal hypersurfaces and Lissajous varieties (images of rational linear subspaces under the coordinatewise cosine map). A central tool is the cycle polynomial of C_n, shown to be the resultant of two smaller cycle polynomials, yielding an inductive construction via Sylvester's formula that mirrors a geometric property of metric polytopes; the degree of this homogeneous polynomial is determined, settling an open question of Sturmfels and Uhler. As an application, the algebraic boundary is disjoint from the interior of E(G) precisely when E(G) is a spectrahedron, equivalently when G is chordal.

Significance. If the results hold, the work supplies an explicit algebraic description of the boundary for a broad class of graphs, resolves the degree question for cycle polynomials, and gives a clean geometric criterion linking elliptopes to spectrahedra. The resultant recursion provides a computable inductive framework with ties to metric polytopes, which is a methodological strength. These contributions would be of interest in algebraic geometry, convex optimization, and semidefinite programming.

major comments (2)
  1. [Cycle polynomial and resultant recursion] The section establishing the cycle polynomial via resultant recursion: the claim that this resultant exactly captures the algebraic boundary hypersurface of E(C_n) (and extends without extraneous factors or missing components to cycle-completable G) is load-bearing for the global characterization, yet the argument relies on mirroring metric-polytope geometry without a direct algebraic verification that the zero set equals the Zariski closure of the boundary points when cycles are embedded in larger graphs.
  2. [Disjointness application] The application showing disjointness of boundary and interior: the equivalence to chordal graphs (and thus to spectrahedra) depends on the boundary being precisely the union of the stated varieties; an explicit check that no interior point of E(G) lies on these varieties when G is chordal, or conversely that non-chordal cycle-completable graphs have interior intersections, would be needed to confirm the claim.
minor comments (2)
  1. [Introduction] The definition of Lissajous varieties could be accompanied by a small explicit example (e.g., for C_4 or C_5) to illustrate the coordinatewise cosine map on a linear subspace.
  2. [Degree computation] Notation for the homogeneous cycle polynomial and its degree formula should be cross-referenced consistently between the inductive construction and the final degree statement.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful and constructive report. The positive assessment of the significance is appreciated. We address the two major comments below and will revise the manuscript to incorporate clarifications.

read point-by-point responses

  1. Referee: The section establishing the cycle polynomial via resultant recursion: the claim that this resultant exactly captures the algebraic boundary hypersurface of E(C_n) (and extends without extraneous factors or missing components to cycle-completable G) is load-bearing for the global characterization, yet the argument relies on mirroring metric-polytope geometry without a direct algebraic verification that the zero set equals the Zariski closure of the boundary points when cycles are embedded in larger graphs.

    Authors: The resultant recursion itself is proved algebraically in Theorem 3.1 by direct elimination: the cycle polynomial is defined as the eliminant of the quadratic equations coming from the Gram matrix on the cycle, and the recursion follows from the Sylvester formula applied to the two smaller resultants without reference to geometry. The metric-polytope analogy is motivational only and appears after the algebraic statement. We prove that the zero set equals the Zariski closure of the boundary by showing (i) the polynomial vanishes on all boundary points (by substitution into the Gram matrix) and (ii) its degree equals the codimension-1 degree computed from the dimension of the elliptope, which rules out extraneous factors. For the extension to cycle-completable graphs, Proposition 4.3 uses the chordal completion to show that no additional components arise and that cycle-induced factors remain irreducible. We will add a short paragraph in Section 3 separating the algebraic proof from the subsequent geometric remark. revision: yes

  2. Referee: The application showing disjointness of boundary and interior: the equivalence to chordal graphs (and thus to spectrahedra) depends on the boundary being precisely the union of the stated varieties; an explicit check that no interior point of E(G) lies on these varieties when G is chordal, or conversely that non-chordal cycle-completable graphs have interior intersections, would be needed to confirm the claim.

    Authors: When G is chordal, E(G) is a spectrahedron by the known characterization, so its algebraic boundary consists solely of the determinantal hypersurfaces arising from rank drops in the maximal-clique submatrices; these hypersurfaces meet the boundary but not the relative interior by the strict feasibility of the LMI description. This is recorded in Corollary 5.2. For the converse direction, any non-chordal cycle-completable graph contains an induced cycle C_k with k >= 4; Theorem 5.3 constructs an explicit interior point by assigning edge lengths that satisfy the cycle polynomial equation (hence lie on the Lissajous component) while keeping the Gram matrix positive definite on all proper subgraphs. We will insert a concrete numerical example for C_4 (with explicit 4x4 Gram matrix and edge lengths) immediately after the statement of Theorem 5.3 to make the interior intersection fully explicit. revision: yes

Circularity Check

0 steps flagged

No circularity: derivation uses independent algebraic operations and external prior results

full rationale

The central construction defines the cycle polynomial of C_n as the resultant of smaller cycle polynomials and applies Sylvester's determinantal formula inductively; these are standard, non-self-referential operations from commutative algebra. The degree computation resolves an open question posed by Sturmfels-Uhler (2010), an external reference. The extension to cycle-completable graphs and the spectrahedron/chordal equivalence follow from the resulting explicit union of determinantal and Lissajous varieties without any reduction of the target boundary description to a fitted parameter, self-citation chain, or definitional renaming of the input. No load-bearing step collapses to its own premise by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The claims rest on the prior definition of the cycle polynomial and on standard facts from algebraic geometry; no free parameters, ad-hoc axioms, or new postulated entities are introduced in the abstract.

axioms (2)
  • standard math Resultants and determinantal hypersurfaces behave as standard objects in algebraic geometry.
    Invoked to construct the boundary hypersurfaces and the inductive formula.
  • domain assumption The cycle polynomial captures the algebraic boundary of the elliptope of any cycle graph.
    Stated as the central ingredient for the characterization.

pith-pipeline@v0.9.0 · 5517 in / 1361 out tokens · 93814 ms · 2026-05-08T18:00:01.057593+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

27 extracted references

  1. [1]

    Barahona and R

    F. Barahona and R. Mahjoub. On the cut polytope.Mathematical Programming, 36:157–173, 1986

    1986

  2. [2]

    Barrett, C.R

    W.W. Barrett, C.R. Johnson, and R. Loewy. The real positive definite completion problem: cycle completability.Memoirs of the American Mathematical Society, 122, 1996

    1996

  3. [3]

    Barrett, C.R

    W.W. Barrett, C.R. Johnson, and P. Tarazaga. The real positive definite completion problem for a simple cycle.Linear Algebra and its Applications, 192:3–31, 1993

    1993

  4. [4]

    Bel-Afia, C

    Z. Bel-Afia, C. Meroni, and S. Telen. Chebyshev varieties.Mathematics of Computation, 2025

    2025

  5. [5]

    M. Belk. Realizability of graphs in three dimensions.Discrete and Computational Geometry, 37:139–162, 2007

    2007

  6. [6]

    Belk and R

    M. Belk and R. Connelly. Realizability of graphs.Discrete and Computational Geometry, 37:125–137, 2007

    2007

  7. [7]

    Blekherman, P.A

    G. Blekherman, P.A. Parrilo, and R.R. Thomas.Semidefinite Optimization and Convex Alge- braic Geometry, volume 13 ofMOS-SIAM Series on Optimization. American Mathematical Society, 2012

    2012

  8. [8]

    Blekherman and K

    G. Blekherman and K. Shu. Sums of squares and sparse semidefinite programming.SIAM Journal on Applied Algebra and Geometry, 5(4):651–674, 2020

    2020

  9. [9]

    D.A. Cox, J. Little, and D. O’Shea.Using Algebraic Geometry, volume 185 ofGraduate Texts in Mathematics. Springer, New York, 2005

    2005

  10. [10]

    D.A. Cox, J. Little, and D. O’Shea.Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra (to appear). Cham: Springer, 5th edition edition, 2025. 29

    2025

  11. [11]

    Deza and M

    M.M. Deza and M. Laurent.Geometry of Cuts and Metrics, volume 15 ofAlgorithms and Combinatorics. Springer, 1997

    1997

  12. [12]

    E.-Nagy, M

    M. E.-Nagy, M. Laurent, and A. Varvitsiotis. Complexity of the positive semidefinite matrix completion problem with a rank constraint. In K. Bezdek, A. Deza, and Y. Ye, editors, Discrete Geometry and Optimization, volume 69 ofFields Institute Communications, pages 105–120. Springer, 2013

    2013

  13. [13]

    E.-Nagy, M

    M. E.-Nagy, M. Laurent, and A. Varvitsiotis. Forbidden minor characterizations for low-rank optimal solutions to semidefinite programs over the elliptope.Journal of Combinatorial Theory Series B, 108:40–80, 2014

    2014

  14. [14]

    Goemans and D.P

    M.X. Goemans and D.P. Williamson. Improved approximation algorithms for maximum cuts and satisfiability problems using semidefinite programming.Journal of the ACM, 42:1115–1145, 1995

    1995

  15. [15]

    Grone, C.R

    R. Grone, C.R. Johnson, E.N. Sá, and H. Wolkowicz. Positive definite completions of partial hermitian matrices.Linear Algebra and its Applications, 58:109–124, 1984

    1984

  16. [16]

    Johnson and T.A

    C.R. Johnson and T.A. McKee. Structural conditions for cycle completable graphs.Discrete Mathematics, 159:155–160, 1996

    1996

  17. [17]

    M. Laurent. Cuts, matrix completions and graph rigidity.Mathematical Programming, 79:255–283, 1997

    1997

  18. [18]

    M. Laurent. The real positive semidefinite completion problem for series-parallel graphs. Linear Algebra and its Applications, 252:347–366, 1997

    1997

  19. [19]

    M. Laurent. A connection between positive semidefinite and euclidean distance matrix completion problems.Linear Algebra and its Applications, 273:9–22, 1998

    1998

  20. [20]

    M. Laurent. Matrix completion problems. In C.A. Floudas and P.M. Pardalos, editors, Encyclopedia of Optimization, pages 1311–1319. Springer, 2001

    2001

  21. [21]

    Laurent and S

    M. Laurent and S. Poljak. On a positive semidefinite relaxation of the cut polytope.Linear Algebra and its Applications, 223-224:439–461, 1995

    1995

  22. [22]

    Laurent and A

    M. Laurent and A. Varvitsiotis. A new graph parameter related to bounded rank positive semidefinite matrix completions.Mathematical Programming, 145(1-2):291–325, 2014

    2014

  23. [23]

    Lissajous varieties.Advances in Geometry, 26(2):263–282, 2026

    Francesco Maria Mascarin and Simon Telen. Lissajous varieties.Advances in Geometry, 26(2):263–282, 2026

    2026

  24. [24]

    G. Pataki. The geometry of semidefinite programming. In H. Wolkowicz, R. Saigal, and L. Vandenberghe, editors,Handbook of Semidefinite Programming, volume 27 ofInternational Series in Operations Research & Management Sciences. Springer, 2000

    2000

  25. [25]

    R. Sinn. Algebraic boundaries of convex semi-algebraic sets.Research in the Mathematical Sciences, 2(3), 2015

    2015

  26. [26]

    Solus, C

    L. Solus, C. Uhler, and R. Yoshida. Extremal positive semidefinite matrices whose sparsity pattern is given by graphs withoutK5 minors.Linear Algebra and its Applications, 509:247– 275, 2016

    2016

  27. [27]

    Sturmfels and C

    B. Sturmfels and C. Uhler. Multivariate Gaussians, semidefinite matrix completion, and convex algebraic geometry.Annals of the Institute of Statistical Mathematics, 62(4):603–638, 2010. 30

    2010