Models of random spanning trees

This paper develops quantitative tools to study random minimum spanning trees (MST) generated by assigning independent edge weights from arbitrary distributions, addressing the gap in mathematical understanding between these practical algorithms and the more extensively studied uniform spanning trees.

The Gist

Imagine you have a map of a city with many roads connecting different neighborhoods. Your goal is to build a network of roads that connects every neighborhood together without any loops, using the least amount of asphalt possible. In math and computer science, this is called a Spanning Tree.

There are two main ways to decide which roads to build:

1. The "Fair Dice" Method (Uniform Spanning Tree): You roll a die for every single road to see how likely it is to be picked. You do this in a way that ensures every possible valid network has an exactly equal chance of being chosen. This is the "gold standard" for fairness, but it's computationally heavy and hard to do in real life.
2. The "Greedy Shopper" Method (Minimum Spanning Tree - MST): This is what computers actually use. You assign a random "price" to every road (like drawing a number between 0 and 1). Then, you act like a greedy shopper: you buy the cheapest roads first, skipping any road that would create a loop, until everyone is connected.

The Big Question:
The authors of this paper ask: If we use the "Greedy Shopper" method with random prices, do we get the same "fair" result as the "Fair Dice" method?

The short answer is no. The greedy method is biased. It tends to pick certain shapes of networks (like star-shaped hubs) more often than others (like long, winding paths).

Here is a breakdown of their journey to understand this bias, using simple analogies:

1. The "Square with a Diagonal" Problem

Imagine a square room with a diagonal line drawn across it. There are 5 walls/lines total.

• Fair Dice: Every way to connect the corners is equally likely.
• Greedy Shopper: If you assign random prices, the diagonal line is surprisingly likely to be included. Why? Because it's often the "cheapest" way to connect two corners that are far apart, beating out the longer path around the square.

The authors realized that if you want the Greedy Shopper to act like the Fair Dice, you can't just use random numbers from the same bag for every road. You have to "rig" the bags. For example, you might put slightly higher prices in the bag for the diagonal line so it's less likely to be picked, balancing the odds.

2. The "Shifted Interval" Experiment

The paper explores a middle ground. Instead of giving every road a price from the exact same range (0 to 1), what if we shift the ranges?

• Analogy: Imagine you are assigning prices to roads.
  • Roads inside a specific neighborhood get prices between $0 and $1.
  • Roads between neighborhoods get prices between $0.50 and $1.50.
• The Result: This simple "shift" changes the outcome. It makes it less likely to cut through the neighborhood boundaries. This is actually used in real life for political redistricting. If you want to keep counties together when drawing new voting districts, you can "surcharge" (add a tiny extra cost to) the roads that cross county lines. The greedy algorithm will naturally try to avoid those expensive cross-county roads, keeping the counties intact.

However, the authors proved that for complex maps (like a complete map of a city where every point connects to every other point), simply shifting the price ranges isn't enough to make the greedy method perfectly fair. You need something more complex.

3. The "Word" Magic (Arbitrary Measures)

To understand the full picture, the authors went even further. They asked: What is the absolute limit of what we can achieve by rigging the prices?

They developed a clever way to think about this using "Words."

• Imagine you have a word made of letters, like "A-B-A-B".
• You assign weights to the letters.
• The order in which the letters appear in the word determines the probability of different outcomes.

They discovered that any possible pattern of bias you could create with random prices can be perfectly mimicked by a specific "Word" with the right weights. It's like saying: "No matter how weird the bias is, there is a secret recipe (a word) that produces it."

4. The "Star" vs. The "Snake"

One of their coolest findings is about the shape of the network the greedy method prefers.

• The Star: A network where one central hub connects to everyone else (like a spider web).
• The Snake: A long, winding path connecting everyone in a line.

In a complete city map, the Star shape is the most likely to be chosen by the greedy algorithm, while the Snake is the least likely.

• Why? Think of it like a race. To build a Star, you only need to find a few very cheap roads connecting to the center. To build a Snake, you need a long chain of cheap roads in a specific order. The greedy algorithm finds the "Star" much easier because it has more "shortcuts" (broken cycles) to choose from.

5. The "Dimension" Mystery

Finally, they tried to measure the "size" of the universe of possible outcomes.

• If you have 3 roads, there are 6 possible orders they could be picked.
• If you have 10 roads, there are millions of orders.
• The authors calculated that the "Greedy Shopper" can only reach a tiny fraction of these possibilities. It's like trying to fill a swimming pool with a thimble; you can only reach a specific, limited shape of water level, no matter how you tilt the thimble.

Summary

This paper is a deep dive into the hidden biases of a very common computer algorithm.

• The Problem: The "greedy" way of building networks (Minimum Spanning Tree) is not fair; it favors certain shapes (Stars) over others (Snakes).
• The Application: We can use this knowledge to tweak the algorithm. By slightly adjusting the "prices" of connections (like adding a surcharge to cross-county roads), we can force the algorithm to respect boundaries, which is huge for creating fair political maps.
• The Theory: They proved that while we can't make the greedy method perfectly fair for complex maps, we can describe exactly how biased it is using a new mathematical language of "words" and "shifts."

In short: Randomness isn't always random. Even when you pick numbers at random, the way you pick them (greedily, one by one) creates a hidden preference for certain structures. This paper maps out exactly what those preferences are and how to control them.

Technical Summary

Here is a detailed technical summary of the paper "Models of Random Spanning Trees" by Babson et al.

1. Problem Statement

The paper addresses the gap in mathematical understanding between two primary methods for generating random spanning trees in a graph $G$:

1. Uniform Spanning Trees (UST): Trees sampled uniformly from the set of all spanning trees. These are well-studied and can be generated via random walks (Wilson's algorithm) or matroid-based Markov chains.
2. Minimum Spanning Trees (MST): Trees generated by assigning random weights to edges and selecting the tree with the minimum total weight (typically via Kruskal's algorithm). While ubiquitous in applications (e.g., network design, political districting recombination algorithms), the statistical properties of MSTs with random weights are poorly understood compared to USTs.

The authors investigate the distribution induced on spanning trees when edge weights are drawn from product measures (independent random variables). They explore three specific regimes:

• Ordinary MST ($MST_0$): Weights are i.i.d. from a single distribution (e.g., Uniform$[0,1]$).
• Shifted-Interval MST: Weights are drawn from shifted unit intervals $[s_i, s_i+1]$.
• Arbitrary Product Measures: Weights are drawn from arbitrary independent distributions (non-colliding).

The core question is: What distributions on spanning trees (or permutations of edge weights) can be realized by these different models?

2. Methodology

The authors employ a blend of combinatorial probability, graph theory, and algebraic geometry:

• Broken Cycles and Cycle Relations: They utilize the concept of "broken cycles" (a non-tree edge plus the unique path in the tree connecting its endpoints) to characterize when a specific tree is the MST. A tree $T$ is the MST if and only if for every non-tree edge $e'$, its weight is greater than all edges in the broken cycle $P_{T, e'}$.
• Inductive and Global Formulas: They derive exact probability formulas for $MST_0$ using both Kruskal's algorithm (building up) and the Reverse-Delete algorithm (tearing down). These involve sums over permutations of edges.
• Rotation Moves: To compare probabilities of different tree structures, they introduce "rotation" operations (triangle-edge rotation and path rotation). These moves transform one tree into another while analyzing how the "cycle-expanding" property affects the probability weight.
• Weighted Words and Quadrature: For arbitrary product measures, they abstract the problem into "weighted words" (sequences of symbols with associated weights). They leverage classical quadrature schemes (numerical integration methods like Gauss-Radau and Gauss-Lobatto) to construct specific words that induce uniform distributions on permutations.
• Dimensional Analysis: They treat the space of achievable distributions as a semi-algebraic set. They use Lie shuffle algebras and gradient analysis of independence constraints to bound the dimension of this space.

3. Key Contributions and Results

A. Ordinary MST ($MST_0$) on Complete Graphs

• Exact Formulas: The authors provide exact formulas for the probability of any labeled spanning tree in a complete graph $K_n$ under $MST_0$.
• Extremal Structures: They prove that among all labeled spanning trees in $K_n$:
  • Stars (trees with one central node connected to all others) have the highest probability.
  • Paths (linear chains) have the lowest probability.
  • Specifically, $P_{MST_0}(\text{Star}) = \frac{1}{(2n-3)!!}$, which is significantly higher than the uniform probability $\frac{1}{n^{n-2}}$.
• Random Graphs: They show that for Erdős-Rényi random graphs $G(n, p)$ with $p = c \log n / n$, the distribution $MST_0$ is almost surely distinct from the Uniform Spanning Tree (UST) distribution.

B. Shifted-Interval MST

• Shiftahedron: They define a parameter space called the "shiftahedron" to study measures where edge weights are uniform on shifted intervals $[s_i, s_i+1]$.
• Impossibility of Uniformity: They prove that for complete graphs $K_n$ with $n \ge 4$, no choice of shifted intervals can recover the Uniform Spanning Tree distribution. This highlights a fundamental limitation of using simple weight shifts to correct the bias of MST algorithms.
• Application to Districting: They discuss the practical application of shifted intervals in "recombination" algorithms for political redistricting. By shifting the weights of edges crossing county boundaries, one can bias the MST process to keep counties intact, a technique used in practice but previously lacking rigorous theoretical characterization.

C. Arbitrary Product Measures and Permutation Loci

• Weighted Words Representation: They prove that any non-colliding product measure on $m$ variables can be represented by a weighted word of bounded length (specifically, length $\le m(m!+1)$). This reduces the study of continuous distributions to discrete combinatorial objects.
• Universal Words: They construct "universal words" that, with appropriate weights, can generate any distribution in the permutation locus $P_m$.
• Efficient Uniform Generation: Using quadrature theory, they construct short words (e.g., length 8 for $m=3$) that induce the uniform distribution on permutations, offering a more efficient alternative to naive constructions.
• Dimension of the Permutation Locus ($P_m$):
  • They define $P_m$ as the image of the map from product measures to distributions on permutations $S_m$.
  • They establish an upper bound for the dimension of $P_m$: $\dim(P_m) \le C(m)$, where $C(m)$ is the number of permutations in $S_m$ with exactly one non-trivial cycle (pure cycles).
  • $C(m) \sim e(m-1)!$, which is asymptotically much smaller than the full simplex dimension $m! - 1$.
  • They verify computationally that this bound is tight for $m \le 7$.

4. Significance

• Theoretical Insight: The paper provides the first systematic quantitative comparison between UST and MST, revealing that MSTs are heavily biased toward high-degree structures (stars) and against linear structures (paths) in complete graphs.
• Algorithmic Implications: It clarifies the limitations of using simple weight perturbations (shifted intervals) to achieve uniformity in spanning tree generation, suggesting that more complex, non-i.i.d. weight distributions are necessary for certain applications.
• New Mathematical Tools: The introduction of "weighted words" and the connection to quadrature theory provides a powerful new framework for analyzing random spanning trees and intransitive dice problems.
• Practical Relevance: The findings directly inform the design of recombination algorithms for political districting and other graph partitioning tasks where controlling the topology of the resulting trees is crucial.

In summary, the paper moves beyond the assumption that random MSTs are a "good enough" proxy for uniform sampling, providing rigorous tools to quantify their deviation and establishing the mathematical boundaries of what distributions can be achieved through independent edge weighting.