A Balancing Theorem for Spanning Trees of Rectangular Grid Graphs

Jiechen Zhang · 2026

Read A Balancing Theorem for Spanning Trees of Rectangular 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-2605-23773.txt.

Introduction

Zhang determines which N-vertex sets in the square lattice support the most trees. Every maximizer minimizes edges joining the set to the rest. Its shape is a rectangle with at most two strips at opposite corners. For N at least 18, the maximizer is unique up to symmetry: a rectangle with one corner strip. For square N, he proves a stability inequality bounding the difference from a translated square by tree loss. He also derives a product formula and a recurrence for tree counts in rectangles with a corner strip.

Catalog record

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

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

Browse the full library · About the Tower of Babel

Full text

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

A Balancing Theorem for Spanning Trees of Rectangular Grid Graphs Jiechen Zhang Abstract We prove that, among rectangular grid graphs with a fixed number of vertices, the number of spanning trees increases when the side lengths are made more balanced. In particular, among all rectangular grid graphs with n 2 n^{2} vertices, the square n × n n\times n grid has the largest number of spanning trees. The proof starts with the Laplacian product formula, passes to hyperbolic coordinates, and compares logarithms by separating a discrete-concavity term from a positive decreasing residual term. 1 Introduction Let P_{r} be the path graph on r vertices, and let R_{\ell,m}=P_{\ell}\square P_{m} be the \ell\times m rectangular grid graph formed by their Cartesian product. Let \tau(G) denote the number of spanning trees of a finite connected graph G , and abbreviate \tau(\ell,m)=\tau(R_{\ell,m}). The guiding question is whether the square shape maximizes the number of spanning trees. To state the question in a more general induced-grid form, let \mathcal{L} be the infinite square-lattice graph with vertex set \mathbb{Z}^{2} . Conjecture 1.1 . Let n\geq 1 be an integer. Let S\subset\mathbb{Z}^{2} be a finite set of vertices such that |S|=n^{2} , and suppose that the induced subgraph \mathcal{L}[S] is connected. Then \tau(\mathcal{L}[S])\leq\tau(R_{n,n}). This work proves the conjectured square-maximal principle within the family of rectangles. More precisely, we prove the following stronger balancing statement: among rectangular grids with fixed area, moving the side lengths closer together cannot decrease the number of spanning trees. The directly related background is the Matrix–Tree Theorem of Kirchhoff [ 2 ] , which expresses the spanning-tree count as a Laplacian cofactor, together with classical product formulas and asymptotic studies for spanning trees on rectangular grids and lattices [ 6 , 7 , 4 , 1 ] . The broader square-maximal principle for induced grid graphs has also appeared in the redistricting literature [ 3 ] ; recent boundary-sensitive bounds of Tapp [ 5 ] are close in spirit, although they do not imply the exact rectangular comparison proved here. Theorem 1.2 (Balancing Theorem) . Let \ell,m,\ell^{\prime},m^{\prime} be positive integers such that \ell m=\ell^{\prime}m^{\prime},\qquad\ell\leq\ell^{\prime}\leq m^{\prime}\leq m. Then \tau(\ell,m)\leq\tau(\ell^{\prime},m^{\prime}). In words, among rectangles of fixed area, increasing the shorter side and decreasing the longer side cannot decrease the number of spanning trees. Corollary 1.3 . If \ell m=n^{2} , then \tau(\ell,m)\leq\tau(n,n). Proof. Since R_{\ell,m}\cong R_{m,\ell} , we may assume \ell\leq m . From \ell m=n^{2} it follows that \ell\leq n\leq m . Applying Theorem 1.2 with \ell^{\prime}=m^{\prime}=n gives the claim. ∎ 2 Preliminaries For r\geq 1 and 0\leq j\leq r-1 , set \lambda_{j}(r)=2-2\cos\frac{\pi j}{r}. Thus \lambda_{0}(r)=0 , and for j\geq 1 , \lambda_{j}(r)=4\sin^{2}\frac{\pi j}{2r}. Proposition 2.1 . For all positive integers \ell,m , \tau(\ell,m)=\prod_{j=1}^{\ell-1}\prod_{k=1}^{m-1}\bigl(\lambda_{j}(\ell)+\lambda_{k}(m)\bigr). Proof. For the path spectrum, the case r=1 is immediate. Assume r\geq 2 . The Laplacian eigenvalues of P_{r} are the numbers \lambda_{j}(r) , 0\leq j\leq r-1 . Indeed, if the vertices are 1,\ldots,r and u_{x}^{(j)}=\cos\left(\left(x-\frac{1}{2}\right)\frac{\pi j}{r}\right), then a direct substitution gives (Lu^{(j)})_{x}=\lambda_{j}(r)u_{x}^{(j)} at every interior vertex. The same identity holds at the endpoints using the reflecting boundary relations u^{(j)}_{0}=u^{(j)}_{1} and u^{(j)}_{r+1}=u^{(j)}_{r} . Indeed, at x=1 one has (Lu^{(j)})_{1}=u^{(j)}_{1}-u^{(j)}_{2}=2u^{(j)}_{1}-u^{(j)}_{0}-u^{(j)}_{2} , and similarly at x=r . Thus the endpoint equations agree with the same second-difference eigenvalue equation. The r values \lambda_{j}(r) are distinct. Hence the corresponding eigenvectors are linearly independent; since P_{r} has r vertices, they form a basis. The Laplacian of a Cartesian product is L(P_{\ell}\square P_{m})=L(P_{\ell})\otimes I_{m}+I_{\ell}\otimes L(P_{m}) . Hence the Laplacian eigenvalues of R_{\ell,m} are \lambda_{j}(\ell)+\lambda_{k}(m),\qquad 0\leq j\leq\ell-1,\quad 0\leq k\leq m-1. Since R_{\ell,m} is connected, the only zero Laplacian eigenvalue occurs at (j,k)=(0,0) . Kirchhoff’s Matrix–Tree Theorem [ 2 ] gives \tau(\ell,m)=\frac{1}{\ell m}\prod_{\begin{subarray}{c}0\leq j\leq\ell-1\\ 0\leq k\leq m-1\\ (j,k)\neq(0,0)\end{subarray}}\bigl(\lambda_{j}(\ell)+\lambda_{k}(m)\bigr). All products below are interpreted as empty products when one of the side lengths is equal to 1 . Thus the argument also covers the degenerate rectangular grids R_{1,m} and R_{\ell,1} . It remains only to cancel the one-dimensional factors. For every r\geq 1 , \prod_{j=1}^{r-1}\lambda_{j}(r)=r, where the case r=1 is an empty product. For r\geq 2 , this follows from \lambda_{j}(r)=4\sin^{2}\frac{\pi j}{2r} and the identity \prod_{j=1}^{r-1}2\sin\frac{\pi j}{2r}=\sqrt{r}. To prove this identity, recall that the roots of z^{2r}-1=0 are the complex roots of unity e^{\pi iq/r} for 0\leq q<2r . Factoring the polynomial and dividing by the trivial root (z-1) yields the standard result: \frac{z^{2r}-1}{z-1}=\prod_{q=1}^{2r-1}\bigl(z-e^{\pi iq/r}\bigr) and letting z\to 1 and taking absolute values gives 2r=\prod_{q=1}^{2r-1}\left|1-e^{\pi iq/r}\right|. The middle factor, corresponding to q=r , is |1-e^{\pi i}|=2 . For 1\leq j\leq r-1 , the factors indexed by j and 2r-j are equal in absolute value, and \left|1-e^{\pi ij/r}\right|=2\sin\frac{\pi j}{2r} . Pairing these factors gives 2r=2\prod_{j=1}^{r-1}\left(2\sin\frac{\pi j}{2r}\right)^{2}. The nonzero factors with k=0 , where 1\leq j\leq\ell-1 , multiply to \prod_{j=1}^{\ell-1}\lambda_{j}(\ell)=\ell , and the nonzero factors with j=0 , where 1\leq k\leq m-1 , multiply to \prod_{k=1}^{m-1}\lambda_{k}(m)=m . These two one-dimensional products cancel the prefactor 1/(\ell m) , leaving only the terms with j,k\geq 1 . ∎ Thus the zero-mode contributions have canceled the Kirchhoff normalization, leaving only the interaction of the positive modes in the two coordinate directions. 3 Hyperbolic Form and Discrete Concavity For r\geq 1 , define q_{r}(x)=\prod_{j=1}^{r-1}\bigl(x+\lambda_{j}(r)\bigr). Then Section 2 can be written as \tau(\ell,m)=\prod_{j=1}^{\ell-1}q_{m}(\lambda_{j}(\ell))=\prod_{k=1}^{m-1}q_{\ell}(\lambda_{k}(m)). (3.1) Lemma 3.1 . If x=2\cosh\theta-2 with \theta>0 , then q_{r}(x)=\frac{\sinh(r\theta)}{\sinh\theta}. Proof. Let p_{1}(x)=1 , p_{2}(x)=x+2 , and p_{r+1}(x)=(x+2)p_{r}(x)-p_{r-1}(x). By induction, p_{r} is monic of degree r-1 . If x=2\cosh\theta-2 , the identity \sinh((r+1)\theta)=2\cosh\theta\sinh(r\theta)-\sinh((r-1)\theta) shows that p_{r}(x)=\sinh(r\theta)/\sinh\theta . For r=1 , both p_{1} and q_{1} are the constant polynomial 1 , so the claim is immediate. We therefore assume r\geq 2 in the root identification below. To identify p_{r} with q_{r} , substitute x=2\cos\phi-2 . The same recurrence gives p_{r}(2\cos\phi-2)=\frac{\sin(r\phi)}{\sin\phi} whenever \sin\phi\neq 0 . Taking \phi=\pi j/r for 1\leq j\leq r-1 shows that p_{r}(-\lambda_{j}(r))=0 . Thus p_{r} and q_{r} are monic polynomials of degree r-1 with the same r-1 roots, namely -\lambda_{j}(r) for 1\leq j\leq r-1 . Hence p_{r}=q_{r} . ∎ Equivalently, q_{r}(x)=U_{r-1}\left(\frac{x+2}{2}\right), where U_{r-1} is the Chebyshev polynomial of the second kind. The proof above is included to keep the normalization and boundary convention explicit. Define c(x)=\arcosh\left(2-\cos(\pi x)\right)=2\arsinh\left(\sin\frac{\pi x}{2}\right),\qquad 0\leq x\leq 1. Here \operatorname{arcosh} and \operatorname{arsinh} denote the inverse hyperbolic cosine and sine, respectively. For 1\leq j\leq r-1 , the number c(j/r) is the hyperbolic parameter corresponding to the j -th positive eigenvalue of P_{r} . Then \lambda_{j}(r)=2\cosh c(j/r)-2. (3.2) Lemma 3.2 . The function c satisfies c(0)=0 , c^{\prime}(x)\geq 0 , and c^{\prime\prime}(x)\leq 0 on [0,1] . Proof. The value c(0)=0 is immediate. Differentiating the 2\arsinh(\sin(\pi x/2)) expression gives c^{\prime}(x)=\frac{\pi\cos(\pi x/2)}{(1+\sin^{2}(\pi x/2))^{1/2}}\geq 0 and c^{\prime\prime}(x)=-\frac{\pi^{2}\sin(\pi x/2)}{(1+\sin^{2}(\pi x/2))^{3/2}}\leq 0. ∎ Recall that for a function f on [0,1] with f(0)=0 , the expression \frac{1}{r}\sum_{j=1}^{r-1}f(j/r) is the standard left Riemann sum. As r\to\infty , this sum converges to \int_{0}^{1}f(x)\,dx . The following lemma shows that if f is increasing and concave, then these left Riemann sums form a monotonically nondecreasing sequence in r . Lemma 3.3 . Let f\in C^{2}[0,1] satisfy f(0)=0 , f^{\prime}\geq 0 , and f^{\prime\prime}\leq 0 . For r\geq 1 , set A_{r}(f)=\frac{1}{r}\sum_{j=1}^{r-1}f(j/r). Then A_{r}(f)\leq A_{r+1}(f) for every r\geq 1 . Consequently, if r\leq s , then \frac{1}{r}\sum_{j=1}^{r-1}f(j/r)\leq\frac{1}{s}\sum_{j=1}^{s-1}f(j/s). Proof. We first verify the claim for two elementary building blocks. For the identity function \operatorname{id}(x)=x , A_{r}(\operatorname{id})=\frac{1}{r}\sum_{j=1}^{r-1}\frac{j}{r}=\frac{r-1}{2r}, which is increasing in

Read the complete text