Extremal Spanning Trees in Product Grid Graphs

Jiechen Zhang · 2026

Read Extremal Spanning Trees in Product Grid Graphs by Jiechen Zhang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-24016.txt.

Introduction

Zhang asks a counting question about grid networks. Among all grids of the same area, which shape holds the most spanning trees? A spanning tree is a sub-network linking each point with no loops. The answer depends sharply on the edges. A grid can be free on all sides, wrap round like a torus, or mix the two into a cylinder. Zhang's 2026 results split these cases cleanly.

For fully free and fully periodic grids, the closest-to-square shape wins. The mixed cylinder breaks that rule. In divisor-rich cases the best wrap-round length grows much more slowly, at roughly the cube-root scale of the area. In higher dimensions Zhang proves pairwise balancing results for pure free and pure periodic products, and a heat-trace argument strengthens them. At perfect-power volumes the winners are exact cubes in each family. Conjectures extend the pattern to lattice subgraphs.

Catalog record

CREATORJiechen Zhang
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE58 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.24016

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Extremal Spanning Trees in Product Grid Graphs Jiechen Zhang Abstract We study how fixed-volume spanning-tree extremality changes when product-grid boundary factors are free, periodic, or mixed. In two dimensions, extremality depends sharply on the boundary type. The free/free and periodic/periodic products both obey a closest-to-square principle: among fixed-area rectangles, P r ​ □ ​ P s P_{r}\square P_{s} and C r ​ □ ​ C s C_{r}\square C_{s} are maximized by the closest-to-square admissible side lengths. The mixed free/periodic cylinder P r ​ □ ​ C s P_{r}\square C_{s} is different: closest-to-square fails, and in the divisor-rich case the optimizing cyclic circumference has scale N 1 / 3 N^{1/3} when the area is N = r ​ s N=rs . In arbitrary dimension we prove pairwise balancing theorems for pure free products and pure periodic products, and then strengthen them by a heat-trace Schur-concavity theorem in logarithmic side lengths. At perfect-power volume this gives the unique maximizers P n □ ​ d P_{n}^{\square d} and, for n ≥ 3 n\geq 3 , C n □ ​ d C_{n}^{\square d} . These product-grid comparisons motivate perfect-power conjectures for connected induced lattice subgraphs and periodic analogues. 1 Introduction Let \tau(G) denote the number of spanning trees of a finite connected graph G . Throughout, a path factor P_{r} is a free boundary factor, while a cycle factor C_{r} is a periodic boundary factor. Thus P_{r}\square P_{s} is the basic rectangular grid, C_{r}\square C_{s} is the torus, and P_{r}\square C_{s} is the cylinder. The central question is: among product grids of fixed volume, which side lengths maximize \tau , and how does the answer depend on the boundary factors? The answer is boundary-sensitive even in two dimensions. The free/free case was settled quantitatively by the rectangular-grid balancing theorem of Zhang [ 17 ] : among equal-area rectangular grids, moving the side lengths toward a square gives a sharp linear lower bound for the logarithmic spanning-tree gain, with optimal constant \arsinh(1) , and the closest-to-square divisor rectangle uniquely maximizes \tau up to rotation. We study what survives under periodic and mixed boundary conditions, and extend the theory to higher-dimensional pure products. For periodic/periodic products, square-balancing survives: fixed-area tori C_{r}\square C_{s} are also maximized by the closest-to-square admissible divisor pair. For mixed free/periodic products, it fails. At area 36 , \tau(P_{9}\square C_{4})>\tau(P_{6}\square C_{6}) , and at area 120 , \tau(P_{20}\square C_{6})>\tau(P_{12}\square C_{10}) . The cylinder is governed instead by a competition between a free-boundary penalty and a periodic finite-size correction, and the long-cylinder scale developed below is not N^{1/2} but N^{1/3} for the periodic circumference. This gives a finite-size classification for the symmetric boundary cases and an exact/asymptotic theory for the mixed cylinder case. The sharp constants distinguish the boundary conditions. Rectangles have the best positive linear side-sum constant \alpha=\arsinh(1) . Tori balance strictly but have no positive universal linear side-sum constant: the best such constant is 0 . Cylinders have an exact free-boundary penalty -\log\sinh(\alpha s) in the cyclic circumference s ; the same \alpha is sharp, but it competes with a periodic correction of order N/s^{2} rather than with another side length. In higher dimensions the main balancing results concern the two pure products P_{\mathbf{n}}=P_{n_{1}}\square\cdots\square P_{n_{d}}\quad\text{and}\quad C_{\mathbf{n}}=C_{n_{1}}\square\cdots\square C_{n_{d}}, We prove that every nontrivial product-preserving balancing of two coordinates strictly increases the spanning-tree count. Thus fixed-volume maximizers are pairwise balanced. For general N and d\geq 3 , terminal pairwise-balanced divisor tuples need not be unique, so this is a finite reduction rather than a universal closest-to-hypercube uniqueness theorem. This arithmetic obstruction can occur even at a perfect power: the tuple (50,54,64,75) has product 60^{4} and is already pairwise balanced. The heat-trace method gives a stronger global comparison. After extending the one-dimensional heat traces from integer side lengths to positive real side lengths, they become strictly log-convex in logarithmic side length. Karamata’s inequality then gives a Schur-concavity theorem for \log\tau in logarithmic side lengths: among pure path products, and among pure cycle products with all lengths at least 3 , a tuple whose logarithmic side lengths are more balanced has more spanning trees. The perfect-power theorem is the uniform special case. 1.1 Our Contributions We give a boundary-condition extremal theory for spanning trees in product grid graphs with free and periodic boundary factors. The main contributions are the following. (1) Boundary-condition classification in two dimensions ( Sections 3 , 5 and 6 ). The free/free and periodic/periodic products are closest-to-square extremal, while the mixed free/periodic cylinder is not. Thus changing one boundary factor changes the extremal shape. (2) Torus and cylinder exact theory ( Theorems 5.3 , 5.2 , 6.2 , 6.4 , 6.8 and 6.9 ). For tori we prove an exact balancing-gain identity and show that the best universal positive linear side-sum constant is 0 . For cylinders we isolate the exact free-boundary penalty with sharp coefficient \arsinh(1) and derive the N^{1/3} cyclic-circumference scale in the divisor-rich case. (3) Arbitrary-dimensional pure-boundary products ( Theorems 7.1 , 7.2 , 8.1 , 8.2 and 8.2 ). Massive determinant inequalities imply that every nontrivial product-preserving balancing of two coordinates strictly increases \tau for pure free products and pure periodic products. Consequently, fixed-volume maximizers are pairwise balanced; uniqueness follows when the terminal tuple is unique. (4) Schur-concavity by heat traces ( Sections 8.3 , 8.11 and 8.4 ). Pairwise balancing alone cannot prove perfect-power uniqueness, as shown by the pairwise terminal tuple (50,54,64,75) at volume 60^{4} . A heat-trace convexity argument using real side lengths and Karamata’s inequality gives a logarithmic majorization principle, hence Schur-concavity of \log\tau in logarithmic side lengths for pure path and pure cycle products. 1.2 Related Work The product formulas used here go back to Kirchhoff’s Matrix–Tree Theorem [ 7 ] and the classical spectral analysis of lattice spanning trees [ 13 , 15 , 11 ] . Tzeng and Wu obtained closed-form hypercubic formulas under free, periodic, and mixed boundary conditions [ 14 ] , and Golin, Leung, Wang, and Yong surveyed transfer-matrix formulas for grids, cylinders, and tori [ 3 ] . Izmailian and Kenna express square-lattice spanning-tree partition functions under free, cylindrical, toroidal, Möbius, and Klein-bottle boundary conditions in terms of twisted principal partition functions and derive exact finite-size expansions [ 5 , 6 ] . Periodic grids and discrete tori have also been studied through zeta, heat-kernel, and circulant methods [ 1 , 2 , 8 ] . The asymptotic formulas below recover standard finite-size results. The two-dimensional product formulas are special cases of the Tzeng–Wu formulas for hypercubic lattices with free, periodic, and mixed boundary conditions [ 14 ] . The torus bounded-aspect formula recovers the two-dimensional rectangular-torus determinant, or complexity, asymptotic of Chinta, Jorgenson, and Karlsson [ 1 , 2 ] ; the torus and cylinder expansions also match the corresponding boundary-condition corrections of Izmailian and Kenna [ 6 ] . The free/free baseline is the rectangular-grid balancing theorem of Zhang [ 17 ] , which gives the sharp fixed-area comparison for products with two free factors. Procaccia and Tucker-Foltz recorded a two-dimensional square-maximality conjecture for connected induced grid subgraphs [ 10 ] ; the product-extremal conjectures in Section 9 are higher-dimensional product-grid analogues. Tapp’s boundary-sensitive bounds for square-lattice subgraphs give broader extremal context for how boundary

Read the complete text