Free spanning-forest degree can decrease under squaring

Abstract

The expected root degree of the free uniform spanning forest need not be invariant under squaring an infinite connected locally finite simple vertex-transitive graph. For the binary grandparent graph G, of degree 8, two explicit free-exhaustion reductions give E deg_FUSF(G)(o) = (24 − √2)/7 > 3.22. For its simple square G², of degree 40, a finite rational-current certificate proves E deg_FUSF(G²)(o) ≤ 3208526010913748780/10¹⁸ < 3.21. All currents, divergences and energies are verified with integer arithmetic; the passage to the infinite free forest is justified by finite-support flows and free exhaustion. With the explicitly adopted normalization b_F(X) = ½ E deg_FUSF(X)(o) − 1, this gives b_F(G) − b_F(G²) > 1/200, a negative answer to the unrestricted vertex-transitive assertion in Abért’s Question 24. The graph and electrical/forest principles are established background; no new general forest mechanism or exhaustive priority claim is made.

The idea in plain English

Start with an infinite network that looks the same from every vertex. Its “square” adds a direct connection wherever two vertices were previously two steps apart. In this example, each vertex goes from having 8 neighbors to having 40.

Now consider a random forest obtained by taking uniform random spanning trees on larger and larger finite pieces, leaving their boundaries free. Count how many forest edges touch a fixed vertex, and average over the randomness. Even with all those extra available connections, this expected count decreases.

The original value is exact: (24 − √2)/7. The square’s displayed value comes from a proved upper bound; its exact expected degree is not computed.

The surprise is a failure of invariance for this infinite free-forest statistic. It is not a claim about the average degree of a finite spanning tree, or a general rule that adding edges always lowers forest degree.

The precise result

Take the 3-regular tree, choose an end, and let p(v) be the neighbor of v toward that end. The binary grandparent graph joins each vertex to its parent and grandparent. Every edge has unit conductance.

Both graphs are infinite and vertex-transitive. The original graph is nonunimodular: its symmetries distinguish the unique parent from the two children. The result makes no claim of failure in the unimodular or Cayley-graph subclasses.

Abért’s 2010 Question 24 asks about squaring arbitrary vertex-transitive graphs. The paper proves unequal expected degrees directly and states its forest-derived normalization explicitly. Its contribution is this specific comparison; the grandparent graph and the electrical-network tools are established prior work.

Why the comparison holds

1. Calculate the original value. Two finite-network reductions, with explicit convergence arguments, give the exact free effective resistances in G. Summing the edge-inclusion probabilities gives (24 − √2)/7.
2. Certify an upper bound for the square. A finite network contains all 40 edges incident to the root. Explicit rational currents satisfy the required unit-flow equations, and their total energy is checked exactly.
3. Pass to the infinite free forest. The currents have finite support and extend by zero to larger finite free networks. Thomson’s principle and the free limit transfer the energy bound to the expected root degree.

This last step is essential. An unrestricted infinite-network flow calculation would generally concern wired resistance and would not establish the free-forest bound used here.

Status and AI use

This is an unrefereed preprint. AI tools were used extensively in the research, proof development, computation, literature review, and writing. The source package includes the manuscript, exact certificate, and verification code.

A question worth pursuing

Can squaring ever increase expected free-spanning-forest degree? For an infinite, connected, locally finite, simple vertex-transitive graph X, can

E deg_FUSF(X²)(o) > E deg_FUSF(X)(o)?

Here X² is the simple square, and every edge in both graphs has unit conductance.

This paper establishes a strict decrease but does not resolve the opposite direction. A general nonincrease theorem would replace the failed invariance statement with a weaker law. An increasing example would show that squaring can change the expectation in either direction. I see this as a research question; the present evidence does not favor a conjectured answer.

Read the paper

Open PDF in a full window · Download the original from Zenodo

Collaborate on this result

I welcome researchers with expertise in spanning forests, probability on graphs, or electrical networks who would like to examine or develop this work.

Useful contributions include independently checking the free-exhaustion arguments, comparing the result with earlier literature, or investigating the question above. I am also open to collaboration on a revised manuscript and journal submission.

Authorship and responsibilities would be discussed in relation to the substantive contributions made.

Cite this paper

Download BibTeX. Original prose and certificate data: CC BY 4.0. Verification code: MIT.

Background and prior work

• Miklós Abért, Some questions (2010), Question 24.
• Benjamini, Lyons, Peres & Schramm, Uniform spanning forests (2001): the electrical and free-forest framework.
• Pengfei Tang, Weights of uniform spanning forests on nonunimodular transitive graphs (2021): the established grandparent-graph setting.
• Pete & Timár, The free uniform spanning forest is disconnected in some virtually free groups, depending on the generator set (2022): component counts and their distinction from expected degree.

The manuscript and source supplement identify the exact source editions examined and the limits of the literature search.