Spanning-Tree Maximization Forces Isoperimetry in the Square Lattice
Abstract
We determine which connected sets of N vertices in the square lattice support the most spanning trees, using all lattice edges between the chosen vertices. Every maximizer minimizes the number of edges joining the set to the rest of the lattice. Its shape is a rectangle with at most two straight strips of vertices removed at opposite corners. For N≥18, the maximizer is unique up to translation, rotation, and reflection: an explicitly determined rectangle with one possibly empty corner strip removed along its longer side. The proof combines comparisons of Laplacian determinants with geometric comparisons of corner deletions. For N=n2, we prove a sharp stability inequality that bounds the symmetric difference from a translated n× n square in terms of the loss in logarithmic tree count. Thus, nearly optimal tree counts force the vertex set to be close to a square. We also derive an exact product formula and a recurrence for the number of spanning trees in rectangles with a single corner strip removed.
Related
- Local Search for Almost-Spanning Square Grids in Erdős--Rényi Random Graphs
- Disorder on the hyperbolic square lattice I: Anderson delocalization and absolutely continuous spectrum
- Square root cancellation in the hyperbolic lattice counting problem over cocompact groups
- An Exact Strip Observable and the Half-Plane One-Arm Probability for Critical Bond Percolation on the Square Lattice
- The lattice of varieties of semigroups with completely regular square. II
BibTeX
@misc{zhang2026spanningtree,
title = {{Spanning-Tree Maximization Forces Isoperimetry in the Square Lattice}},
author = {Jiechen Zhang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2605.23773},
eprint = {2605.23773},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.23773},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Spanning-Tree Maximization Forces Isoperimetry in the Square Lattice
AU - Jiechen Zhang
PY - 2026
DA - 2026/10/14
PB - arXiv
DO - 10.48550/arxiv.2605.23773
UR - https://arxiv.org/abs/2605.23773
AB - We determine which connected sets of N vertices in the square lattice support the most spanning trees, using all lattice edges between the chosen vertices. Every maximizer minimizes the number of edges joining the set to the rest of the lattice. Its shape is a rectangle with at most two straight strips of vertices removed at opposite corners. For N≥18, the maximizer is unique up to translation, rotation, and reflection: an explicitly determined rectangle with one possibly empty corner strip removed along its longer side. The proof combines comparisons of Laplacian determinants with geometric comparisons of corner deletions. For N=n^2, we prove a sharp stability inequality that bounds the symmetric difference from a translated n× n square in terms of the loss in logarithmic tree count. Thus, nearly optimal tree counts force the vertex set to be close to a square. We also derive an exact product formula and a recurrence for the number of spanning trees in rectangles with a single corner strip removed.
ER -