Pith. sign in

REVIEW 2 minor 17 references

Bounded Treewidth and Complete Monotonicity for Scott-Sokal Spanning-Tree Polynomials

T0 review · 0 major / 2 minor · reviewed 2026-06-26 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read If a graph has treewidth at most k then its spanning-tree polynomial to the power -β is completely monotone for every β greater than (k-1)/2.

desk verdict The paper proves a treewidth bound that settles the Scott-Sokal property for all partial 3-trees and similar graphs. read the letter →

arxiv 2606.26275 v1 pith:4FMUOEIS submitted 2026-06-24 math.CO

Domingos S. P. Salazar This is my paper · ORCID
classification math.CO
keywords spanning-treepolynomialcompletemonotonicitytreewidthchordalcompletionstar-mesheliminationScott-Sokalproblem
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 proves a criterion linking graph treewidth to the complete monotonicity of inverse powers of the spanning-tree polynomial. For any finite connected simple graph with treewidth bounded by k, the property holds for all real exponents β exceeding (k-1)/2. This covers every partial 3-tree throughout the interval 1 < β < 3/2 and includes concrete families such as finite Apollonian networks, K5 minus one edge, and the four-spoke wheel. The argument resolves part of the structural question posed by Scott and Sokal on which graphs make T_G^{-β} completely monotone. Readers care because the result supplies an explicit, checkable graph parameter that guarantees the monotonicity property.

What carries the argument

The bounded-treewidth criterion obtained by combining the real Riesz/Wishart integral, star-mesh elimination of simplicial vertices, Gaussian Laplace kernel for stars, and chordal completion with monotone deletion.

What would settle it

A concrete counterexample would be any specific chordal graph of treewidth k together with a value β slightly larger than (k-1)/2 at which T_G^{-β} fails to be completely monotone.

Watch

Extended reading notes

Core claim

If G is a finite connected simple graph with tw(G) ≤ k, then T_G^{-β} is completely monotone for every β > (k-1)/2. The proof first treats chordal graphs by combining the real Riesz/Wishart integral representation of determinants, star-mesh elimination of simplicial vertices, and a Gaussian Laplace kernel for degree-d stars; general bounded-treewidth graphs are then obtained by chordal completion followed by monotone deletion of the added edges. Consequently every partial 3-tree satisfies the property for all β in (1, 3/2).

Load-bearing premise

The real Riesz/Wishart integral representation, star-mesh elimination of simplicial vertices, and Gaussian Laplace kernel for degree-d stars can be validly combined and extended via chordal completion to establish the monotonicity claim for all bounded-treewidth graphs.

Editorial extensions

If this is right

  • Every partial 3-tree is covered by the monotonicity property throughout the open interval 1 < β < 3/2.
  • The result applies directly to finite Apollonian networks, the graph K_5 minus an edge, and the four-spoke wheel W_4.
  • Any bounded-treewidth graph is handled by first forming a chordal completion and then deleting the extra edges while preserving monotonicity.
  • The threshold (k-1)/2 is the explicit lower bound delivered by the combination of the integral representation and the elimination steps.

Reading between the lines

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

  • Treewidth may serve as the natural parameter that determines the full range of β for which T_G^{-β} is completely monotone across all graphs.
  • The chordal-completion technique could be tested on other graph polynomials whose monotonicity properties are currently open.
  • For graphs whose treewidth grows with size, the critical exponent may be expected to increase accordingly.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 2 minor

Summary. The paper proves that if G is a finite connected simple graph with treewidth tw(G) ≤ k, then the inverse power T_G^{-β} of its spanning-tree polynomial is completely monotone on the positive orthant for every real β > (k-1)/2. The argument proceeds by combining the real Riesz/Wishart integral representation of the determinant, star-mesh elimination of simplicial vertices, a Gaussian Laplace kernel for degree-d stars, chordal completion to a k-tree, and monotone deletion of the added edges. As a corollary, the result covers all partial 3-trees throughout the open interval 1 < β < 3/2, including Apollonian networks, K_5 minus an edge, and the four-spoke wheel.

Significance. If the central claim holds, the work supplies the first explicit structural criterion (bounded treewidth) that guarantees complete monotonicity of T_G^{-β} for a positive range of β, thereby settling the Scott-Sokal question for an infinite family of graphs that includes all series-parallel graphs and all partial 3-trees. The proof re-uses only standard analytic and combinatorial ingredients (Riesz measures, simplicial elimination, chordal supergraphs) without introducing fitted parameters or self-referential constructions, and the threshold (k-1)/2 matches the expected dimension of maximal cliques in a chordal completion of treewidth k.

minor comments (2)
  1. [§1] §1, paragraph after Definition 1.2: the sentence 'the deletion step is presented as preserving the property' would benefit from an explicit citation to the standard fact that complete monotonicity extends continuously to coordinate hyperplanes when the function remains positive.
  2. [§2] The notation T_G for the spanning-tree polynomial is introduced without an explicit formula; adding the standard Kirchhoff-matrix expression (or a reference to it) in the first paragraph of §2 would improve readability for readers outside the immediate area.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment, accurate summary of the main theorem, and the recommendation to accept the manuscript.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity identified

full rationale

The paper's derivation proceeds from the Riesz/Wishart integral representation of the determinant, combined with star-mesh elimination for simplicial vertices, a Gaussian Laplace kernel on degree-d stars, chordal completion to bound treewidth, and monotone deletion of added edges. These steps are presented as independent analytic and combinatorial ingredients applied to the spanning-tree polynomial; the resulting β-threshold (k-1)/2 follows directly from the clique dimension in the chordal supergraph and is not obtained by fitting or redefinition. No load-bearing premise reduces to a self-citation, fitted parameter renamed as prediction, or ansatz smuggled from prior work by the same author. The argument is therefore self-contained against external benchmarks.

Assumptions & free parameters 0 free parameters · 2 assumptions · 0 invented entities

Based on the abstract alone, the central claim rests on the standard definitions of the spanning-tree polynomial and complete monotonicity together with the validity of the three named analytic-combinatorial techniques; no free parameters or invented entities are mentioned.

assumptions (2)
  • standard math The spanning-tree polynomial T_G is the standard multivariate Kirchhoff polynomial whose coefficients count spanning trees
    The object whose monotonicity properties are studied.
  • standard math Complete monotonicity for multivariate functions is the standard sign-alternation condition on all partial derivatives
    The property being proved.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Bounded Treewidth and Complete Monotonicity for Scott-Sokal Spanning-Tree Polynomials." pith.science (2026). https://pith.science/paper/4FMUOEIS

@misc{pith2026260626275,
  author       = {Pith},
  title        = {Pith review of: Bounded Treewidth and Complete Monotonicity for Scott-Sokal Spanning-Tree Polynomials},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4FMUOEIS}},
  note         = {Machine review of arXiv:2606.26275}
}
abstract

Scott and Sokal asked for a structural description of the finite graphs \(G\) for which inverse powers \(T_G^{-\beta}\) of the spanning-tree polynomial are completely monotone. We prove the following bounded-treewidth criterion: if \(G\) is a finite connected simple graph with \(\operatorname{tw}(G)\le k\), then \(T_G^{-\beta}\) is completely monotone for every \(\beta>(k-1)/2\). Consequently, every partial \(3\)-tree is covered throughout the first Scott--Sokal open interval \(1<\beta<3/2\), including finite Apollonian networks, \(K_5-e\), and the four-spoke wheel \(W_4\). The proof combines the real Riesz/Wishart integral for determinants, star--mesh elimination of simplicial vertices, and a Gaussian Laplace kernel for the degree-\(d\) star. General bounded-treewidth graphs follow by chordal completion and monotone deletion of completion edges.

Figures

Figures reproduced from arXiv: 2606.26275 by the authors.

Figure 1
Figure 1. The two Scott–Sokal test graphs in the notation used below. Both are partial [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. A second-generation finite Apollonian network. Each new vertex is inserted into [PITH_FULL_IMAGE:figures/full_fig_p015_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

17 extracted references · 3 canonical work pages

  1. [1]

    J. S. Andrade Jr., H. J. Herrmann, R. F. S. Andrade, and L. R. da Silva, Apollonian networks: simultaneously scale-free, small world, Euclidean, space filling, and with matching graphs, Physical Review Letters 94 (2005), 018702

    2005

  2. [2]

    R. B. Bapat, Graphs and Matrices, Universitext, Springer, London, 2010

    2010

  3. [3]

    C. Berg, J. P. R. Christensen, and P. Ressel, Harmonic Analysis on Semigroups: Theory of Positive Definite and Related Functions, Graduate Texts in Mathematics 100, Springer, 1984

    1984

  4. [4]

    Bergold, V

    H. Bergold, V. Irsic, R. Lauff, J. Orthaber, M. Scheucher, and A. Wesolek, Book embeddings of stacked triangulations, arXiv:2409.01678, 2024

    work page arXiv 2024

  5. [5]

    Bollobas, Modern Graph Theory, Graduate Texts in Mathematics 184, Springer, New York, 1998

    B. Bollobas, Modern Graph Theory, Graduate Texts in Mathematics 184, Springer, New York, 1998

    1998

  6. [6]

    H. L. Bodlaender, A partial \(k\)-arboretum of graphs with bounded treewidth, Theoretical Computer Science 209 (1998), 1--45

    1998

  7. [7]

    E. B. Curtis, D. Ingerman, and J. A. Morrow, Circular planar graphs and resistor networks, Linear Algebra and its Applications 283 (1998), 115--150

    1998

  8. [8]

    P. G. Doyle and J. L. Snell, Random Walks and Electric Networks, Mathematical Association of America, 1984. Also available as arXiv:math/0001057

    work page Pith review arXiv 1984

Show all 17 references
  1. [9]

    Faraut and A

    J. Faraut and A. Koranyi, Analysis on Symmetric Cones, Oxford Mathematical Monographs, Oxford University Press, 1994

    1994

  2. [10]

    D. R. Fulkerson and O. A. Gross, Incidence matrices and interval graphs, Pacific Journal of Mathematics 15 (1965), 835--855

    1965

  3. [11]

    R. A. Horn and C. R. Johnson, Matrix Analysis, second edition, Cambridge University Press, 2013

    2013

  4. [12]

    G. Kirchhoff, Ueber die Aufloesung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Stroeme gefuehrt wird, Annalen der Physik und Chemie 72 (1847), 497--508

  5. [13]

    Le Jan, Markov Paths, Loops and Fields, Lecture Notes in Mathematics 2026, Springer, 2011

    Y. Le Jan, Markov Paths, Loops and Fields, Lecture Notes in Mathematics 2026, Springer, 2011

    2026

  6. [14]

    R. J. Muirhead, Aspects of Multivariate Statistical Theory, Wiley Series in Probability and Mathematical Statistics, John Wiley & Sons, 1982

    1982

  7. [15]

    A. D. Scott and A. D. Sokal, Complete monotonicity for inverse powers of some combinatorially defined polynomials, Acta Mathematica 213 (2014), 323--392. Also available as arXiv:1301.2449

    2014 arXiv

  8. [16]

    A. D. Sokal, The multivariate Tutte polynomial (alias Potts model) for graphs and matroids, Surveys in Combinatorics 2005, London Mathematical Society Lecture Note Series 327, Cambridge University Press, 2005, 173--226

    2005

  9. [17]

    D. V. Widder, The Laplace Transform, Princeton Mathematical Series 6, Princeton University Press, 1941

    1941

Pith tools

Reviewed June 26, 2026 · model on record in the stance chip above.