arxiv: 2604.16735 · v1 · submitted 2026-04-17 · 💻 cs.DM · cs.CG

Recognition: unknown

On the volume of the elliptope and related metric polytopes

David Avis , Luc Devroye

Authors on Pith no claims yet

Pith reviewed 2026-05-10 07:30 UTC · model grok-4.3

classification 💻 cs.DM cs.CG

keywords cut polytopemetric polytopeelliptopevolume ratiosconvex bodiesgraph optimizationrelaxationsmaximum cut

0 comments

The pith

The rooted metric polytope over the complete graph has much greater volume than the elliptope, while the metric polytope volume is smaller than the elliptope for small n but larger for large n.

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

This paper compares the volumes of four convex bodies on n-vertex graphs: the cut polytope, the metric polytope, the rooted metric polytope, and the elliptope. These bodies act as successive relaxations for combinatorial optimization problems such as maximum cut, where the cut polytope is the most exact but computationally hardest. Volume ratios supply global measures of relaxation looseness that complement known worst-case bounds on objective values. The central results establish that the rooted metric polytope volume greatly exceeds the elliptope volume, and that the metric polytope is smaller in volume than the elliptope at small n yet overtakes it at large n according to asymptotic estimates. Exact volume formulas are also supplied for the cut polytope on selected sparse graphs.

Core claim

For the complete graph the volume of the rooted metric polytope is much greater than that of the elliptope. For the metric polytope the volume is smaller than that of the elliptope when n is small, yet volume estimates indicate that the metric polytope volume exceeds the elliptope volume when n is large. Exact volume formulas are derived for the cut polytope on certain families of sparse graphs.

What carries the argument

Volume ratios of the cut polytope, metric polytope, rooted metric polytope, and elliptope, which quantify the global tightness of linear and semidefinite relaxations for graph optimization problems.

If this is right

For large complete graphs the rooted metric polytope supplies a substantially looser relaxation than the elliptope in terms of feasible-set measure.
For small n the metric polytope is a tighter relaxation than the elliptope by volume, but this ordering reverses for large n.
Exact cut-polytope volumes on sparse graphs permit precise comparison of relaxation quality on those families.
Volume ratios give global bounds on relaxation quality independent of the sign pattern of the objective coefficients.
These comparisons can be used to select among polynomial-time relaxations according to graph size.

Where Pith is reading between the lines

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

The volume-based comparison method could be applied to other pairs of polytopes arising in combinatorial optimization to rank their global tightness.
If the large-n reversal holds, hybrid solvers might switch from elliptope to metric-polytope formulations once n exceeds a computable threshold.
Sparse-graph exact formulas may extend to additional graph classes where symmetry or decomposition reduces the integration dimension.
The results suggest that volume growth rates could serve as a diagnostic for when a relaxation begins to include many infeasible points that affect average-case performance.

Load-bearing premise

The asymptotic volume estimates for the metric polytope at large n accurately reflect its true volume relative to the elliptope without substantial approximation error.

What would settle it

An exact volume computation for the metric polytope at some n greater than 10 that remains strictly smaller than the corresponding elliptope volume would disprove the suggested reversal.

Figures

Figures reproduced from arXiv: 2604.16735 by David Avis, Luc Devroye.

**Figure 1.** Figure 1: Cut3 = Met3 Elliptope I3 The general worst-case ratio bounds with a non-negative objective function are 2 − ϵ when Q = Metn (Poljak and Tulza [23]) versus 1.139 when Q = In (Goemans and Williamson [15]). We will be considering how to obtain volumes for these two bodies in this paper to obtain general volume bounds. The use of volumes to compare combinatorial polytopes, test the strength of constraints, an… view at source ↗

**Figure 2.** Figure 2: The cycle C5 and its suspension ∇(C5) = W6. The cut and correlation polytopes are related by the covariance map: xi,n+1 = yii 1 ≤ i ≤ n, xij = yii + yjj − 2yij 1 ≤ i < j ≤ n. (6) It is easy to show (e.g., see [11], Section 5.2) that Cor(G) ∼= Cut(∇(G)). 7 [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗

**Figure 3.** Figure 3: Cactus (Eppstein [12]). Proposition 6. Let G be a cactus containing cycles C i ni , i = 1, . . . , m for m ≥ 1. Then vol(G) = Ym i=1 vol(C i ni ). Proof. A cactus can be decomposed by repeatedly deleting a pendant vertex or cycle until a single cycle C remains. Reversing this process, we can reconstruct the cactus, updating the volume at each step. The initial volume is vol(C). Repeatedly using Proposition… view at source ↗

**Figure 4.** Figure 4: 8-necklace: neck8 (Lee &Skipper [19]). Proposition 7. Let G be a necklace based on Cn. vol(G) = vol(Cn) Yn i=1 vol(C i ). Proof. The proof is similar to Proposition 6. G can be composed by deleting the cycles C i , i = 1, ..., n resulting in Cn. Reversing the process and updating the volume, the proposition follows. To illustrate, the volume of the necklace given in [PITH_FULL_IMAGE:figures/full_fig_p011_4.png] view at source ↗

**Figure 5.** Figure 5: Log plots of vol(RMetn), vol(Metn) (estimate dashed) and vol(In) 19 [PITH_FULL_IMAGE:figures/full_fig_p019_5.png] view at source ↗

read the original abstract

In this paper, we investigate the relationships between the volumes of four convex bodies: the cut polytope, metric polytope, rooted metric polytope, and elliptope, defined on graphs with $n$ vertices. The cut polytope is contained in each of the other three, which, for optimization purposes, provide polynomial-time relaxations. It is therefore of interest to see how tight these relaxations are. Worst-case ratio bounds are well known, but these are limited to objective functions with non-negative coefficients. Volume ratios, pioneered by Jon Lee with several co-authors, give global bounds and are the subject of this paper. For the rooted metric polytope over the complete graph, we show that its volume is much greater than that of the elliptope. For the metric polytope, for small values of $n$, we show that its volume is smaller than that of the elliptope; however, for large values, volume estimates suggest the converse is true. We also give exact formulae for the volume of the cut polytope for some families of sparse graphs.

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.

Desk Editor's Note private letter to a colleague

The paper gives exact cut-polytope volumes on sparse graphs and a clear volume comparison for the rooted metric polytope versus the elliptope, but the large-n crossover for the metric polytope rests on estimates whose accuracy is not yet shown.

read the letter

The paper computes exact volumes for the cut polytope on certain sparse graphs and shows that the rooted metric polytope on the complete graph has substantially larger volume than the elliptope. Those exact formulas are the clearest new contribution and should be straightforward to verify. The small-n comparison for the metric polytope versus the elliptope is also exact and useful for seeing how the relaxations differ in a global sense rather than just on worst-case objectives. The work builds directly on the volume-ratio approach from Jon Lee and co-authors, which is a reasonable extension. The central soft spot is the large-n claim that the metric polytope volume overtakes the elliptope. This rests on estimates, and the abstract gives no information on sampling method, variance control, or validation against the exact small-n cases. In high dimensions even modest relative error can reverse an inequality if the true ratio sits near one, so the crossover direction needs tighter evidence before it can be treated as settled. The rest of the paper stays within standard polyhedral combinatorics and does not appear to introduce circular arguments or unfalsifiable claims. This is a paper for people already working on cut and metric polytopes who want quantitative global bounds on relaxation tightness. A specialist in the area would get value from the exact sparse-graph formulas and the rooted-metric comparison. It deserves peer review because the exact results are concrete and the estimates, while preliminary, raise a question worth checking with better error analysis.

Referee Report

1 major / 1 minor

Summary. The manuscript investigates volume relationships among the cut polytope, metric polytope, rooted metric polytope, and elliptope on graphs with n vertices. It proves that the rooted metric polytope over the complete graph has substantially larger volume than the elliptope. For the metric polytope it gives exact computations showing smaller volume than the elliptope for small n, while volume estimates suggest the inequality reverses for large n. Exact volume formulas are also derived for the cut polytope on selected families of sparse graphs.

Significance. If the large-n estimates are reliable, the work supplies global volume-ratio bounds on the tightness of these polynomial-time relaxations, complementing known worst-case ratio results. The exact small-n comparisons and the closed-form cut-polytope volumes on sparse graphs are rigorous, verifiable contributions that strengthen the paper. The suggested asymptotic crossover for the metric polytope would be a noteworthy observation on the relative sizes of these bodies, but its validity hinges on the accuracy of the numerical estimates.

major comments (1)

The section presenting volume estimates for the metric polytope at large n does not specify the approximation technique, sampling procedure, error bounds, variance estimates, or any cross-validation against the exact small-n volumes already computed in the paper. Because the central claim of a volume reversal (metric polytope larger than elliptope for large n) rests on these estimates being accurate enough to fix the inequality direction, the absence of such controls is load-bearing and must be addressed.

minor comments (1)

The abstract refers to 'volume estimates' for large n without indicating the underlying graphs or methods; a brief clarifying sentence would improve readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of our manuscript and for highlighting the need for greater transparency in our numerical methods. We address the major comment below.

read point-by-point responses

Referee: The section presenting volume estimates for the metric polytope at large n does not specify the approximation technique, sampling procedure, error bounds, variance estimates, or any cross-validation against the exact small-n volumes already computed in the paper. Because the central claim of a volume reversal (metric polytope larger than elliptope for large n) rests on these estimates being accurate enough to fix the inequality direction, the absence of such controls is load-bearing and must be addressed.

Authors: We agree with the referee that additional details are necessary to support the volume estimates for large n. In the revised manuscript, we will provide a complete description of the approximation technique used, the sampling procedure, error bounds, variance estimates, and cross-validation against the exact small-n volumes. This will allow readers to assess the reliability of the suggested volume reversal. revision: yes

Circularity Check

0 steps flagged

No circularity: volumes derived from direct computation and independent estimates

full rationale

The paper computes exact volumes for the cut polytope on sparse graphs via explicit formulas and performs direct volume comparisons for small n using enumeration or integration. For large n it reports Monte Carlo-style estimates of the metric polytope volume relative to the elliptope. None of these steps reduce by construction to a fitted parameter, self-citation chain, or ansatz imported from the authors' prior work; the estimates are presented as numerical approximations whose accuracy is a separate statistical question, not a definitional equivalence. The central claims therefore remain independent of the inputs they compare.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on standard definitions of the four polytopes from prior literature and on unspecified techniques for exact volume computation or asymptotic estimation.

axioms (1)

domain assumption The cut polytope, metric polytope, rooted metric polytope, and elliptope are defined via their standard convex-hull or inequality descriptions as established in the literature.
Invoked to relate the four bodies and to justify volume comparisons.

pith-pipeline@v0.9.0 · 5481 in / 1267 out tokens · 84894 ms · 2026-05-10T07:30:59.656200+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

28 extracted references · 1 canonical work pages

[1]

V. S. Adamchik. Contributions to the theory of the Barnes function.arXiv, math/0308086v1, 2003

work page arXiv 2003
[2]

V. S. Adamchik. Symbolic and numeric computations of the Barnes function. Computer Physics Communications, 157(3):161–190, 2004. 20

2004
[3]

H. Alzer. On some inequalities for the gamma and psi functions.Mathematics of Computation, 66(217):373–389, 1997

1997
[4]

D. André. Mémoire sur les permutations alternées.Journal de Mathématiques Pures et Appliquées, 7:167–184, 1881
[5]

Chalkis, I

A. Chalkis, I. Z. Emiris, and V. Fisikopoulos. A practical algorithm for volume estimation based on billiard trajectories and simulated annealing.ACM Journal of Experimental Algorithmics, 28, 2023

2023
[6]

Chalkis and V

A. Chalkis and V. Fisikopoulos. Volesti: Volume approximation and sampling for convex polytopes in R.R Journal, 13(2):561, 2021

2021
[7]

Choi and H

J. Choi and H. M. Srivastava. A note on a multiplication formula for the multiple gamma functionγ(n).Journal of Pure and Applied Mathematics, 23:179–188, 2008

2008
[8]

Choi and H

J. Choi and H. M. Srivastava. Integral representations for the gamma function, the beta function, and the double gamma function.Integral Transforms Special Functions, 20(11-12):859–869, 2009

2009
[9]

J. Choi, H. M. Srivastava, and V. S. Adamchik. Multiple gamma and related functions.Applied Mathematics and Computing, 134(2-3):515–533, 2003

2003
[10]

Onskeletons, diametersandvolumesofmetric polyhedra

A.Deza, M.Deza, andK.Fukuda. Onskeletons, diametersandvolumesofmetric polyhedra. In M. Deza, R. Euler, and Y. Manoussakis, editors,Combinatorics and Computer Science, 8th Franco-Japanese and 4th Franco-Chinese Conference, Brest, France, July 3-5, 1995, Selected Papers, volume 1120 ofLecture Notes in Computer Science, pages 112–128. Springer, 1995

1995
[11]

Deza and M

M. Deza and M. Laurent.Geometry of Cuts and Metrics. Number 15 in Algo- rithms and Combinatorics. Springer, Germany, 1997

1997
[12]

Eppstein

D. Eppstein. Cactus graph svg.https://commons.wikimedia.org/wiki/File: Cactus_graph.svg, 2026. Accessed: 2026-04-15. 21

2026
[13]

Ferreira and J

C. Ferreira and J. L. López. An asymptotic expansion of the double gamma function.Journal of Approximation Theory, 111:298–314, 2001

2001
[14]

S. R. Finch.Mathematical Constants. Cambridge University Press, 2003

2003
[15]

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

1995
[16]

H. Joe. Generating random correlation matrices based on partial correlations. Journal of Multivariate Analysis, 97(10):2177–2189, 2006

2006
[17]

C. Ko, J. Lee, and E. Steingrímsson. The volume of relaxed boolean-quadric and cut polytopes.Discrete Mathematics, 163(1-3):293–298, 1997

1997
[18]

Lee and W

J. Lee and W. D. J. Morris. Geometric comparison of combinatorial polytopes. Discrete Applied Mathematics, 55(2):163–182, 1994

1994
[19]

Lee and D

J. Lee and D. E. Skipper. Volume computation for sparse boolean quadric re- laxations.Discrete Applied Mathematics, 275:79–94, 2020

2020
[20]

J. Lee, D. E. Skipper, and E. Speakman. Algorithmic and modeling insights via volumetric comparison of polyhedral relaxations.Mathematical Programming, 170(1):121–140, 2018

2018
[21]

G. Nemes. Error bounds and exponential improvement for the asymptotic ex- pansion of the barnes g-function.Proceedings of the Royal Society of London Series A, 470(2172), 2014

2014
[22]

OEIS Foundation Inc. and N. J. A. Sloane. The On-Line Encyclopedia of Integer Sequences, 2024. Sequence A000111

2024
[23]

Poljak and Z

S. Poljak and Z. Tuza. The expected relative error of the polyhedral approx- imation of the max-cut problem.Operations Research Letters, 16(4):191–198, 1994. 22

1994
[24]

H. M. Srivastava and J. Choi.Series Associated with the Zeta and Related Func- tions. Kluwer Academic Publishers, 2001

2001
[25]

H. M. Srivastava and J. Choi.Zeta and q-Zeta Functions and Associated Series and Integrals. Elsevier, 2012

2012
[26]

A. Voros. Spectral functions, special functions and the selberg zeta function. Communications in Mathematical Physics, 110:439–465, 1987

1987
[27]

E. T. Whittaker and G. N. Watson.A Course of Modern Analysis, Fourth Edition. Cambridge University Press, 1963

1963
[28]

Xu and W

Z. Xu and W. Wang. More asymptotic expansions for the Barnes G-function. Journal of Number Theory, 174:505–517, 2017. 23 Appendices A Results of volume estimation forvol(Met n) Table 4: Estimates forvol(Metn)vs truncated exact values ofvol(In). n Min. 1st Qu. Median Mean 3rd Qu. Max. vol(In) vol(In) Mean(Metn) 8 9.86e-10 1.05e-09 1.13e-09 1.15e-09 1.18e-0...

2017