Building the free uniform spanning forest from independent randomness

← All digests

Family 231 · Probability and statistical mechanics
Importance 4/5 · Provisional editorial rating
Sources consulted 2026-10-11

1. The question

A uniform spanning tree is a global random object: every vertex is included, cycles are forbidden, and distant edge choices can affect one another. On an infinite graph, its free-boundary limit may be a forest with several components.

Can that forest nevertheless be generated from independent random labels placed at the vertices, using a rule that respects every graph symmetry and chooses no special root?

This is the factor-of-IID question. It asks whether the apparent global coordination can be encoded measurably in independent local randomness. The rule may inspect infinitely far, so it is a structural question about random processes rather than automatically an efficient distributed algorithm.

Family 231 contains a manuscript claiming one such rule for every infinite connected locally finite simple unweighted graph. It also gives a broader factor theorem for translation-invariant strongly Rayleigh processes on countable groups, including a class of determinantal processes.

2. Background and essential definitions

Free and wired spanning forests

A spanning tree of a finite connected graph includes every vertex, is connected, and contains no cycle. The uniform spanning-tree measure gives each such tree equal probability.

For an infinite graph $G$, choose an increasing sequence of finite connected subgraphs exhausting all edges. Sample a uniform spanning tree in each and examine probabilities involving any fixed finite set of edges. The free uniform spanning forest, or FUSF, is the limiting law when no boundary vertices are identified. This limit exists and does not depend on the chosen exhaustion.

The wired construction instead identifies the outer boundary before taking the limit. Free and wired forests can differ, so a sampling result for one is not automatically a result for the other.

A graph is locally finite if each vertex has finite degree. Degrees need not have one common upper bound. Simplicity excludes loops and multiple edges; unweighted means all graph edges have the same original weight.

Factors of independent labels

Give every vertex $v$ an independent uniform random variable $U_v\in[0,1]$. A factor rule decides whether an edge $e$ is present through a measurable function

$$\Phi(G,U,e)\in\{0,1\}.$$

Equivariance means that relabeling the graph by an isomorphism and transporting its random labels transports the output in exactly the same way. Root independence means that the construction uses no distinguished vertex. Borel measurability is the standard regularity requirement ensuring that this deterministic map defines a random process.

The output coordinates need not be independent. Their dependencies are created by applying the rule to overlapping portions of the input. For example, an edge rule can depend on random labels shared with nearby edge rules.

A finitary factor has an additional property: each output can be determined from an almost surely finite random neighborhood. An ordinary Borel factor need not have this property. A uniform real label also contains an unlimited sequence of random bits, unlike a fixed finite-alphabet label.

Negative dependence and determinant laws

For a finite binary process $X=(X_i)_{i\in F}$, its generating polynomial is

$$g(z)=\mathbb E\prod_{i\in F}z_i^{X_i}.$$

The law is strongly Rayleigh if this polynomial is nonzero whenever every $z_i$ has positive imaginary part. On a countable set, this is required for every finite-coordinate marginal. The algebraic condition implies robust forms of negative dependence: selecting one coordinate tends to discourage selecting others, and the relevant properties survive certain changes of weights.

A determinantal random subset with kernel $K$ is specified by

$$\mathbb P(A\subseteq X)=\det(K_{g,h})_{g,h\in A}$$

for every finite set $A$. If $K$ is a Hermitian positive contraction, meaning $0\leq K\leq I$ as an operator on square-summable functions, such a law exists and is strongly Rayleigh. The determinant controls joint inclusion probabilities.

3. Development history and previous partial results

Pemantle constructed infinite-volume spanning-tree limits on the integer lattice. Benjamini, Lyons, Peres, and Schramm developed the general theory of uniform spanning forests, including the distinction between free and wired limits.

For wired forests on transient graphs, cycle popping and Wilson’s algorithm rooted at infinity already provide an IID construction. Transience means a random walk can escape rather than returning indefinitely. That construction did not settle the free-forest problem on arbitrary graphs.

Determinantal structure supplied another route in group settings. Lyons and Thom proved a stronger Bernoulli-isomorphism conclusion for the relevant invariant determinantal measures on amenable groups. Amenability permits averaging through finite sets whose boundary is small relative to their size. The unrestricted factor problem also includes nonamenable settings where that method of approximation is unavailable.

Timár established free-forest factor results for recurrent unimodular random graphs and, more generally, invariantly amenable unimodular random graphs, with stronger finitary conclusions in the stated amenable setting. The cited December 2025 version still lists the general FUSF factor question as open.

The new construction also has an information-theoretic ancestry. Eldan introduced stochastic localization; El Alaoui and Montanari described its Gaussian observation and innovation formulation. Nam, Sly, and Zhang used Brownian-driven posterior equations for factor constructions of free Ising measures on regular trees. The current manuscript adapts that observation mechanism to a countable collection of negatively dependent binary variables.

4. What the new manuscripts claim

One rule for every graph in the class

The main theorem claims a single Borel, root-independent, equivariant rule $\Phi$ such that, for every infinite connected locally finite simple undirected unweighted graph,

$$\{e\in E(G):\Phi(G,U,e)=1\} \quad\text{has law }\operatorname{FUSF}_G.$$

The quantifier is graphwise: one rule works across the whole class. It does not first choose a random-graph distribution and tailor the construction to that law.

No amenability, transience, uniform degree bound, or degree-moment assumption is imposed. The output has the joint forest law, rather than merely the correct probability for each individual edge.

As a consequence, the FUSF is a graph factor of IID under every unimodular random-graph law supported on this class. Unimodularity is the mass-transport balance saying that expected total mass sent from a randomly rooted vertex equals expected total mass received, for every invariant nonnegative transport rule. The source does not need this balance for its stronger graphwise construction.

The conclusion is an ordinary Borel factor. It does not state a finite coding radius or a finite input alphabet.

Strongly Rayleigh laws under group translations

Let $\Gamma$ be a countable group, and index a binary process by its elements. Left translation acts by

$$(\tau_gx)_h=x_{g^{-1}h}.$$

For every strongly Rayleigh law $\nu$ invariant under these translations, the manuscript claims a Borel map from independent uniform labels to $\nu$, commuting with every translation on every label input.

The group need not be amenable or finitely generated, and finite groups are allowed. In this theorem the map may depend on $\Gamma$ and $\nu$, unlike the single graphwise rule in the forest theorem.

The determinantal corollary applies whenever a Hermitian positive-contraction kernel on $\ell^2(\Gamma)$ defines a translation-invariant law. A sufficient condition is that $K$ commute with left translations. Projection kernels and complex Hermitian kernels are included; no trace-class assumption is imposed on the full operator.

This statement concerns the regular action on the group itself. It is not asserted for every action of a group on every other index set, and a factor map need not be an invertible Bernoulli isomorphism.

5. Why the advance matters

Importance: 4/5. The free uniform spanning forest is a canonical infinite random structure. A universal graphwise IID representation would answer a substantial factor question while removing the geometric restrictions present in previous constructions.

The group theorem broadens the significance beyond spanning forests. It would connect a robust algebraic negative-dependence condition with equivariant generation from independent randomness, without relying on amenability.

The result also separates two notions often conflated in informal discussion. A process can be generated measurably from independent labels without admitting a bounded-time or finite-neighborhood sampling algorithm. The structural conclusion is strong even when no such computational guarantee is supplied.

The rating reflects broad consequences within probability on graphs and invariant random processes, while retaining the theorem’s precise distinction between graph isomorphisms and regular group translations.

6. The main idea

Reveal a target sample through Brownian noise

Temporarily suppose a sample $X_e\in\{0,1\}$ from the desired forest law already exists. Observe each coordinate through

$$Y_e(t)=tX_e+B_e(t),$$

with independent Brownian motions $B_e$. As time grows, the signal dominates the noise: the long-time slope reveals $X_e$.

Given the observations, the conditional mean $b_e(t,Y)$ is a drift. Subtracting its accumulated contribution produces innovations,

$$\widehat W_e(t)=Y_e(t)-\int_0^t b_e(s,Y(s))\,ds,$$

which form independent Brownian inputs under the observation law. If the relation can be inverted deterministically, these independent inputs can generate the original correlated sample.

Negative dependence controls the inverse

For a finite weighted spanning tree, let $p_e$ be the inclusion probability of edge $e$, and let $h_f$ be the logarithm of edge $f$‘s weight. Differentiating gives

$$\frac{\partial p_e}{\partial h_f}=\operatorname{Cov}(X_e,X_f), \qquad \sum_f\left|\frac{\partial p_e}{\partial h_f}\right| =2p_e(1-p_e)\leq\frac12.$$

Different edges have nonpositive covariance, while every spanning tree has the same number of edges. Together these facts bound the entire response of one inclusion probability, uniformly in graph size and weights.

The manuscript passes this response bound to a countable-coordinate drift and solves

$$Z_e(t)=w_e(t)+\int_0^t b_e(s,Z(s))\,ds$$

by deterministic successive approximation. Only differences between successive approximations need a uniform bound. This matters because infinitely many independent Brownian paths are not uniformly bounded over all coordinates.

Feeding independent Brownian paths into the inverse recovers the observation process, and integer-time slopes recover the forest. Intrinsic edge-centered neighborhoods preserve graph symmetry; independent vertex labels provide independent edge paths by allocating disjoint random coordinates.

For strongly Rayleigh laws, the same covariance-row estimate holds as an inequality after suitable finite extensions. Translates of finite subsets of the group supply compatible coordinate exhaustions. They need not have small boundary, which is why the stated regular-action result requires no amenability.

7. Scope, limitations, and open questions

The graph theorem is stated for simple unweighted locally finite graphs. Weighted finite trees appear inside the proof, but that does not automatically extend the final graphwise claim to arbitrary infinite conductance networks or multiple edges.

The construction has no stated finitary radius, runtime, or finite-bit budget. Measurability and exact equivariance are the conclusions; practical sampling complexity is a separate question. Stronger finitary results already known in special amenable settings remain stronger in that particular respect.

The group theorem allows its factor to depend on the target law and treats only the regular left action. The existence of compatible finite exhaustions is used in that form. General actions and broader negatively dependent processes require additional analysis.

The companion free-Ising factor threshold discussed in family 236 uses a related observation viewpoint with a different recovery mechanism. It is a separate theorem, not an automatic consequence of the forest result. All claims here are reported as stated by the source.

8. Sources and further reading

The uniform-spanning-forest paper and Timár’s work give the main graph-theoretic background. Lyons–Thom explains the earlier amenable-group determinantal result. For the algebraic condition used in the extension, see Borcea, Brändén, and Liggett, Negative dependence and the geometry of polynomials.

The source manuscript below states the graphwise and group-action theorems separately and develops the Brownian observation inverse that connects them.

Source manuscripts

• M1. OpenAI, The free uniform spanning forest is a factor of IID (September 25, 2026).

Sources consulted on 11 October 2026 at repository revision fd4aeeb. Download the manuscript citations.