Extremal Spanning Trees in Product Grid Graphs
Abstract
We compare spanning-tree counts at a fixed number of vertices for Cartesian products of paths Pr, r≥1, or cycles Cs, s≥3. With the number d of factors fixed, an equal-volume tuple that is more balanced in the logarithmic majorization order has at least as many spanning trees, with equality only for permutations. This comparison persists after adjoining any fixed finite connected Cartesian factor; equal-sided blocks therefore uniquely maximize the count at admissible block volume nd. We prove the comparison through strict log-convexity of one-dimensional heat traces in logarithmic length. The Hartman--Watson representation expresses the cycle interpolation as a positive mixture of theta functions, and the path case follows from it. The same heat-trace order decreases every positive inverse-power sum of the nonzero Laplacian eigenvalues, and hence the total effective resistance. Cylinders behave differently: square balancing can fail. For Pr□ Cs of area N=rs, extending the product formula to real height and optimizing over integer circumferences 3≤ s≤ N yields an optimum on the scale N1/3. Along areas having a divisor asymptotic to that optimum, quantitative estimates place every graph-maximizing circumference on the same scale. For two-dimensional tori, balancing remains optimal, but the gain in the logarithmic spanning-tree count admits no positive uniform lower bound proportional to the decrease in the side sum.
Related
- Extremal Spanning Trees of Random Marked Graphs with Independent Edge Weights
- A Turán-type extremal problem for the number of spanning trees in C4-free graphs
- An extremal theorem for non-isomorphic spanning trees
- Product approximations for uniform spanning trees and determinantal processes
- Spectral radius and edge-disjoint spanning trees of graphs with edge connectivity
BibTeX
@misc{zhang2026extremal,
title = {{Extremal Spanning Trees in Product Grid Graphs}},
author = {Jiechen Zhang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2606.24016},
eprint = {2606.24016},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.24016},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Extremal Spanning Trees in Product Grid Graphs
AU - Jiechen Zhang
PY - 2026
DA - 2026/09/27
PB - arXiv
DO - 10.48550/arxiv.2606.24016
UR - https://arxiv.org/abs/2606.24016
AB - We compare spanning-tree counts at a fixed number of vertices for Cartesian products of paths P_r, r≥1, or cycles C_s, s≥3. With the number d of factors fixed, an equal-volume tuple that is more balanced in the logarithmic majorization order has at least as many spanning trees, with equality only for permutations. This comparison persists after adjoining any fixed finite connected Cartesian factor; equal-sided blocks therefore uniquely maximize the count at admissible block volume n^d. We prove the comparison through strict log-convexity of one-dimensional heat traces in logarithmic length. The Hartman--Watson representation expresses the cycle interpolation as a positive mixture of theta functions, and the path case follows from it. The same heat-trace order decreases every positive inverse-power sum of the nonzero Laplacian eigenvalues, and hence the total effective resistance. Cylinders behave differently: square balancing can fail. For P_r□ C_s of area N=rs, extending the product formula to real height and optimizing over integer circumferences 3≤ s≤ N yields an optimum on the scale N^1/3. Along areas having a divisor asymptotic to that optimum, quantitative estimates place every graph-maximizing circumference on the same scale. For two-dimensional tori, balancing remains optimal, but the gain in the logarithmic spanning-tree count admits no positive uniform lower bound proportional to the decrease in the side sum.
ER -