pith. sign in

arxiv: 2407.20226 · v2 · submitted 2024-07-29 · 💻 cs.DM · math.CO· math.PR

Models of random spanning trees

Eric Babson , Moon Duchin , Annina Iseli , Pietro Poggi-Corradini , Dylan Thurston , Jamie Tucker-Foltz This is my paper

Pith reviewed 2026-05-23 22:43 UTC · model grok-4.3

classification 💻 cs.DM math.COmath.PR
keywords random spanning treesminimum spanning treeproduct measuresi.i.d. weightsuniform spanning treegraph algorithmsrandomized algorithms
0
0 comments X

The pith

Tools are developed to quantitatively study random minimum spanning trees via i.i.d. weights and product measures.

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

The paper sets out to create mathematical tools that let researchers analyze the properties of random minimum spanning trees, which arise in practice when edges receive random weights and a greedy algorithm selects the minimum. Uniform spanning trees have received far more mathematical attention, yet many algorithms rely on the weight-based MST construction instead. The authors treat the standard case of identical independent distributions on all edges and then extend the setting to product measures that allow each edge its own distribution.

Core claim

Models based on i.i.d. weights drawn from a single distribution, together with their generalization to product measures in which weights are drawn independently from arbitrary distributions, supply a workable framework for the quantitative study of random MSTs.

What carries the argument

Product measures on edge weights, in which each edge draws its weight independently from its own distribution.

If this is right

  • Quantitative comparisons become possible between MSTs generated from different weight distributions.
  • Properties such as expected total weight or diameter can be tracked as the underlying distributions vary.
  • Algorithms that sample random MSTs can be analyzed with distribution-specific guarantees.

Where Pith is reading between the lines

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

  • The same product-measure construction might be applied to directed graphs or to matroids beyond the graphic case.
  • One could test whether the models recover known limits for MSTs on complete graphs with exponential weights.
  • Connections to percolation or random media might become visible once the measures are used to compute tail probabilities.

Load-bearing premise

Studying i.i.d. weights and product measures will produce quantitative insights into random MSTs that matter for applications.

What would settle it

An explicit calculation or simulation on a concrete graph family showing that the distribution of tree properties under these product measures is identical to the uniform case or yields no new closed-form expressions.

Figures

Figures reproduced from arXiv: 2407.20226 by Annina Iseli, Dylan Thurston, Eric Babson, Jamie Tucker-Foltz, Moon Duchin, Pietro Poggi-Corradini.

Figure 1
Figure 1. Figure 1: In [9], a “recombination” Markov chain is run to draw random partitions of the state into 150 legislative districts. The Markov chain combines and re-splits two districts at a time by drawing and bisecting a random spanning tree. These figures show heatmaps from three different runs, with the ∼9000 precincts of Texas colored on a scale from dark blue (reassigned rarely) to yellow (reassigned frequently). W… view at source ↗
Figure 2
Figure 2. Figure 2: The Trybu la region T3. Given independent random variables X1, X2, X3 that are the components of a non-colliding product measure D, the three coordinate axes are x = PD(X1 > X2), y = PD(X2 > X3), and z = PD(X3 > X1). The vertices of the cube that are hit by T3 correspond to the pure permutations (for example, (1, 1, 0) comes from X1 > X2 > X3), whereas (0, 0, 0) and (1, 1, 1) are not hit. On general princi… view at source ↗
Figure 3
Figure 3. Figure 3: A tree on five vertices, regarded as belonging to an ambient [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Three examples of triangle-edge rotation, where the ambient graphs are a square with a [PITH_FULL_IMAGE:figures/full_fig_p010_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: A path rotation operation from T to T ′ that rotates a path P from v1 to v5. Theorem 3.12 (Path rotation in complete graphs). Let T = L ∪ P ∪ R and T ′ = L ′ ∪ P ′ ∪ R′ be spanning trees of Kn obtained by rotating a path P of ℓ ≥ 2 vertices as depicted in [PITH_FULL_IMAGE:figures/full_fig_p012_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Moves that interpolate from arbitrary trees to stars and paths, strictly monotonic with [PITH_FULL_IMAGE:figures/full_fig_p013_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: A simple example of processing a folded permutation; the green numbering on folded [PITH_FULL_IMAGE:figures/full_fig_p016_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: The shiftahedra Sh(3) and Sh(4). Definition 4.2 (Shiftahedron). For fixed m, let R = n (r1, . . . , rm) ∈ R m : Xri = m 2  and ri ≤ ri+1 ≤ ri + 1 for each i o . 18 [PITH_FULL_IMAGE:figures/full_fig_p018_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Probabilities for all forest shapes in K5. Edges show inclusions F ′ ⊂ F obtained by deleting one edge, with multiplicity according to the number of ways to delete the edge. We can improve the running time of Kruskal’s algorithm by combining some ingredients already assem￾bled. Specifically, for a graph G and a forest F ⊂ G, consider the probability P(F) that F appears at some point in Kruskal’s algorithm … view at source ↗
Figure 10
Figure 10. Figure 10: Above, a tree T ′ containing a path P ′ of length ℓ = 14, giving r = 7 and six sets of paired edges. The state vector s has seven entries. Below, a possible state s midway through the inner for-loop of Algorithm 3.1. Solid black edges have been confirmed to be added to the tree, dashed black edges have been added with probability 1 2 , and gray edges have been confirmed to be excluded. The colored, curved… view at source ↗
Figure 11
Figure 11. Figure 11: We can define shifted interval MST on theta graphs by using the same shifts on the edges of each type: Sh(r, s, t) = {(α, . . . , α, β, . . . , β, γ, . . . , γ) : (α, β, γ) ∈ Sh(3)} . We note that every spanning tree of θ(r, s, t) must be missing exactly two edges: one edge each from two of the three paths in G. A tree of R type contains all of the R path but is missing one S-edge and one T-edge; likewise… view at source ↗
Figure 12
Figure 12. Figure 12: Left: The snowman graph θ(7, 1, 5). Right: the θ-surgery graph G built from the cycle G0 of length 6 and the θ-graph θ = θ(2, 2, 2) (that is, r = 2, k = 3). Proposition C.4 (Snowman-free graphs). For a snowman-free graph G, MST0 = UST. Proof. First, observe that every snowman-free graph G is either a tree or a finite collection of generalized theta graphs θ(r, r, r, ..., r) (for various r) that are connec… view at source ↗
Figure 13
Figure 13. Figure 13: Condition no new loops arise. The left-hand side shows the snowman-free graph G consisting of four theta graphs (black), connected by paths (green), and two additional leaves (blue). The right-hand side shows the tree obtained from G by collapsing the theta graphs into points. However, the converse of Proposition C.4 is false. To see this, consider the following construction: Let G0 be a graph for which M… view at source ↗
read the original abstract

There are numerous randomized algorithms to generate spanning trees in a given ambient graph; several target the uniform distribution on trees (UST), while in practice the fastest and most frequently used draw random weights on the edges and then employ a greedy algorithm to choose the minimum-weight spanning tree (MST). Though MST is a workhorse in applications, the mathematical properties of random MST are far less explored than those of UST. In this paper we develop tools for the quantitative study of random MST. We consider the standard case that the weights are drawn i.i.d. from a single distribution on the real numbers, as well as successive generalizations that lead to \emph{product measures}, where the weights are independently drawn from arbitrary distributions.

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

0 major / 3 minor

Summary. The paper develops tools for the quantitative study of random minimum spanning trees (MST), beginning with the standard model of i.i.d. edge weights drawn from a single distribution on the reals and then extending successively to product measures in which edge weights are drawn independently from arbitrary (possibly distinct) distributions. It positions this work against the more extensively studied uniform spanning trees (UST) and emphasizes the practical prevalence of MST-based algorithms.

Significance. If the constructions are carried through rigorously, the framework could fill a notable gap by supplying quantitative tools for random MST, a setting that is algorithmically central yet mathematically less developed than UST. The explicit progression from i.i.d. to product measures is a clear organizational strength and could support later applications in network analysis or randomized algorithms.

minor comments (3)
  1. The abstract and title use 'random spanning trees' while the body focuses exclusively on MST; a brief clarifying sentence in the introduction would prevent reader confusion.
  2. Notation for the product-measure extension (e.g., how the family of distributions is indexed) should be introduced explicitly in the first section that defines the model.
  3. The manuscript would benefit from a short table or diagram contrasting the i.i.d. case, the product-measure case, and the uniform spanning-tree measure.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the supportive summary of our work on quantitative tools for random MSTs under i.i.d. and product measures, and for the recommendation of minor revision. No specific major comments were listed in the report.

Circularity Check

0 steps flagged

No significant circularity; modeling setup is self-contained

full rationale

The paper's abstract and description focus on developing tools to study random MST under i.i.d. edge weights from a single distribution, then generalizing to product measures with independent but arbitrary distributions. No equations, predictions, or derivations are exhibited in the provided text. No self-citations, fitted parameters renamed as predictions, or self-definitional steps are present. The central activity is defining and analyzing models from standard measure-theoretic assumptions, which does not reduce to its own inputs by construction. This is a standard non-circular foundational modeling paper.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract only provides no identifiable free parameters, axioms, or invented entities.

pith-pipeline@v0.9.0 · 5658 in / 948 out tokens · 32124 ms · 2026-05-23T22:43:34.383372+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

26 extracted references · 26 canonical work pages

  1. [1]

    Addario-Berry, N

    L. Addario-Berry, N. Broutin, and B. Reed. Critical random graphs and the structure of a minimum spanning tree. Random Structures Algorithms, 35(3):323–347, 2009

    work page 2009

  2. [2]

    David J. Aldous. The random walk construction of uniform spanning trees and uniform labelled trees. SIAM Journal of Discrete Mathematics , 3(4):450–465, 1990

    work page 1990

  3. [3]

    Log-concave polynomials, I: Entropy and a deterministic approximation algorithm for counting bases of matroids

    Nima Anari, Shayan Oveis Gharan, and Cynthia Vinzant. Log-concave polynomials, I: Entropy and a deterministic approximation algorithm for counting bases of matroids. Duke Mathematical Journal , 170(16):3459 – 3504, 2021

    work page 2021

  4. [4]

    Log-concave polynomials II: High- dimensional walks and an FPRAS for counting bases of a matroid

    Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant. Log-concave polynomials II: High- dimensional walks and an FPRAS for counting bases of a matroid. Annals of Mathematics , 199(1):259 – 299, 2024

    work page 2024

  5. [5]

    Andrei Z. Broder. Generating random spanning trees. In 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October - 1 November 1989, pages 442–447. IEEE Computer Society, 1989

    work page 1989

  6. [6]

    On the spanning tree polyhedron

    Sunil Chopra. On the spanning tree polyhedron. Oper. Res. Lett., 8(1):25–29, 1989. 30

    work page 1989

  7. [7]

    Recombination: A Family of Markov Chains for Redistricting

    Daryl DeFord, Moon Duchin, and Justin Solomon. Recombination: A Family of Markov Chains for Redistricting. Harvard Data Science Review , 3(1), mar 31 2021. https://hdsr.mitpress.mit.edu/pub/1ds8ptxu

    work page 2021

  8. [8]

    Graph Theory

    Reinhard Diestel. Graph Theory. Graduate Texts in Mathematics. Springer Berlin, Heidelberg, 5 edition, 2017

    work page 2017

  9. [9]

    Moon Duchin and Douglas M. Spencer. Models, Race, and the Law. The Yale Law Journal Forum , 130:744–797, 2021

    work page 2021

  10. [10]

    The scaling limits of the minimal spanning tree and invasion percolation in the plane

    Christophe Garban, G´ abor Pete, and Oded Schramm. The scaling limits of the minimal spanning tree and invasion percolation in the plane. Ann. Probab., 46(6):3501–3557, 2018

    work page 2018

  11. [11]

    Kirchhoff

    G. Kirchhoff. On the solution of the equations obtained from the investigation of the linear distribution of galvanic currents. IRE Transactions on Circuit Theory , 5(1):4–7, 1958

    work page 1958

  12. [12]

    Nontransitive random variables and nontransitive dice

    Andrzej Komisarski. Nontransitive random variables and nontransitive dice. Amer. Math. Monthly , 128(5):423–434, 2021

    work page 2021

  13. [13]

    Kruskal, Jr

    Joseph B. Kruskal, Jr. On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Amer. Math. Soc., 7:48–50, 1956

    work page 1956

  14. [14]

    Probability on trees and networks , volume 42 of Cambridge Series in Statistical and Probabilistic Mathematics

    Russell Lyons and Yuval Peres. Probability on trees and networks , volume 42 of Cambridge Series in Statistical and Probabilistic Mathematics . Cambridge University Press, New York, 2016

    work page 2016

  15. [15]

    Lyndon words, free algebras and shuffles.Canad

    Guy Melan¸ con and Christophe Reutenauer. Lyndon words, free algebras and shuffles.Canad. J. Math., 41(4):577–591, 1989

    work page 1989

  16. [16]

    The on-line encyclopedia of integer sequences, 2024

    OEIS Foundation, Inc. The on-line encyclopedia of integer sequences, 2024. http://oeis.org/

    work page 2024

  17. [17]

    Press, Saul A

    William H. Press, Saul A. Teukolsky, William T. Vetterling, and Brian P. Flannery. Numerical Recipes 3rd Edition: The Art of Scientific Computing . Cambridge University Press, USA, 3 edition, 2007

    work page 2007

  18. [18]

    Free Lie algebras, volume 7 of London Mathematical Society Monographs

    Christophe Reutenauer. Free Lie algebras, volume 7 of London Mathematical Society Monographs. New Series. The Clarendon Press, Oxford University Press, New York, 1993. Oxford Science Publications

    work page 1993

  19. [19]

    Tyrrell Rockafellar

    R. Tyrrell Rockafellar. Convex analysis . Princeton Landmarks in Mathematics. Princeton University Press, Princeton, NJ, 1997. Reprint of the 1970 original, Princeton Paperbacks

    work page 1997

  20. [20]

    Savage, Jr

    Richard P. Savage, Jr. The paradox of nontransitive dice. Amer. Math. Monthly, 101(5):429–436, 1994

    work page 1994

  21. [21]

    Independent random utility representations

    Reinhard Suck. Independent random utility representations. Math. Social Sci. , 43(3):371–389, 2002

    work page 2002

  22. [22]

    On the minimum spanning tree distribution in grids

    Kristopher Tapp. On the minimum spanning tree distribution in grids. arXiv preprint arXiv:2401.17947, 2024

    work page arXiv 2024

  23. [23]

    On the paradox of three random variables

    Stanis law Trybu la. On the paradox of three random variables. Applicationes Mathematicae, 4(5):321– 332, 1961

    work page 1961

  24. [24]

    On the paradox of n random variables

    Stanis law Trybu la. On the paradox of n random variables. Zastos. Mat., 8:143–156, 1965

    work page 1965

  25. [25]

    MST Distribution

    Jamie Tucker-Foltz and Peter Rock. MST Distribution. Replication repository. https://github.com/ mggg/MST-Distribution

    work page

  26. [26]

    Generating random spanning trees more quickly than the cover time

    David Bruce Wilson. Generating random spanning trees more quickly than the cover time. InProceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing , STOC, page 296–303, 1996. 31 A Probability and runtime We can make a few additional observations about computing the probability of spanning trees using internal and external formulas. For ...

    work page 1996