Balanced spanning trees of the 2-by-N grid

2025/08/14 by Gallagher, Makenzie, Tapp, Kristopher
#Combinatorics (math.CO) #FOS: Mathematics #FOS: Physical sciences #Physics and Society (physics.soc-ph)

paper · doi:10.48550/arxiv.2508.10614

Abstract

We obtain an exact formula for the probability that a uniformly random spanning tree of the 2-by-n square grid is ``balanced'' in the sense that it has an edge whose removal partitions its vertices into two sets of equal size. We compute the exact limit of this probability as n→∞.

Citations

• Balanced Spanning Tree Distributions Have Separation Fairness
• Sampling tree-weighted partitions without sampling trees
• Splittable Spanning Trees and Balanced Forests in Dense Random Graphs
• Automated Counting of Spanning Trees for Several Infinite Families of Graphs
• Models of random spanning trees
• Sampling Balanced Forests of Grids in Polynomial Time
• On the Complexity of Sampling Redistricting Plans
• Recombination: A family of Markov chains for redistricting
• Metropolized Forest Recombination for Monte Carlo Sampling of Graph Partitions
• Spanning Trees in Grid Graphs

Related

• Sharp threshold for embedding balanced spanning trees in random geometric graphs
• Splittable Spanning Trees and Balanced Forests in Dense Random Graphs
• Sampling Balanced Forests of Grids in Polynomial Time
• On the Minimum Spanning Tree Distribution in Grids
• Arboricity and spanning-tree packing in random graphs with an application to load balancing