Effect of edge-stretching on Steklov eigenvalues and sharp Steklov eigenvalue bounds  on leaf--boundary trees

Technical Summary: Effect of Edge-Stretching on Steklov Eigenvalues and Sharp Bounds on Leaf-Boundary Trees

Problem Statement
This research investigates the spectral properties of the Steklov problem on finite graphs, specifically focusing on trees where the boundary $\delta\Omega$ is defined as the set of leaf vertices. The Steklov eigenvalues $\lambda_k$ are the eigenvalues of the Dirichlet-to-Neumann (DtN) operator, which maps boundary functions to their normal derivatives via harmonic extension. The primary objectives are to understand how discrete geometric deformations influence these eigenvalues and to establish sharp upper bounds for the first nontrivial eigenvalue $\lambda_2$ in terms of the maximum vertex degree $D$ and the number of leaves $\ell$.

Methodology
The authors employ a combination of discrete geometric analysis, variational methods, and combinatorial graph theory:

1. Edge-Stretching Operation: Motivated by "neck-stretching" in Riemannian manifolds (inserting long cylindrical regions), the authors define a discrete analogue: replacing an edge with a path of length $L$ through new interior vertices.
2. Variational Characterization: The Steklov eigenvalues are analyzed using the Rayleigh quotient involving the Dirichlet energy of harmonic extensions. The authors utilize the min-max principle and the Schur complement formula (Kron reduction) to relate the graph Laplacian to the DtN operator.
3. Energy Minimization: Proofs of monotonicity rely on constructing specific test functions (linear interpolations on stretched edges) to bound the energy of the harmonic extension.
4. Centroid Arguments: To derive sharp bounds for $\lambda_2$, the authors utilize a weighted centroid argument on trees to identify a vertex that splits the boundary into balanced components, allowing for the construction of optimized two-value test functions.
5. Explicit Spectral Analysis: For level-regular trees (trees with a fixed branching sequence), the authors perform a closed-form diagonalization of the DtN operator by exploiting symmetry and flux computations on symmetric branches.
6. Numerical Verification: The theoretical bounds are validated through exhaustive enumeration of unlabeled trees (up to $n=16$ vertices) and randomized experiments on larger trees.

Key Contributions and Results

• Monotonicity under Edge-Stretching (Theorem 1.2): The paper proves that Steklov eigenvalues decrease monotonically when an edge is stretched. Specifically, if $G(L)$ is obtained by $L$-stretching an edge in $G$, then $\lambda_k(G(L)) \le \lambda_k(G)$ for all $k$. This implies that contracting interior vertices of degree 2 increases the eigenvalues, suggesting that extremal trees for $\lambda_2$ can be assumed to be homeomorphically irreducible (no degree-2 interior vertices).
• Sharp Upper Bound for $\lambda_2$ (Theorem 1.4): The authors establish the inequality:
  $$\lambda_2 \le \frac{D}{\ell}$$
  where $D$ is the maximum degree and $\ell$ is the number of leaves. Equality holds if and only if the tree is a star graph ($K_{1,\ell}$).
  • Significance: This improves upon the previous bound by He–Hua ($\lambda_2 \le 4(D-1)/\ell$) and Lin–Zhao ($\lambda_2 \le 8D/\ell$ for planar graphs). The improvement from a constant factor of 4 (or 8) to the optimal factor of 1 is achieved by bypassing Cheeger-type inequalities and working directly with the Rayleigh quotient at a leaf centroid.
• Explicit Spectra for Level-Regular Trees (Theorem 1.6): The paper provides a closed-form formula for the Steklov eigenvalues of level-regular trees with branching sequence $m = (m_0, \dots, m_{h-1})$. The eigenvalues are given by $\mu_j(m)$ with specific multiplicities. For complete $m$-ary trees, this yields $\lambda_2 = (m-1)/(m^h-1)$, demonstrating that the bound $D/\ell$ is asymptotically tight as $D \to \infty$.
• General Bound for Higher Eigenvalues (Theorem 1.8): A general upper bound is provided for higher eigenvalues:
  $$\lambda_k \le \min\left\{1, \frac{16Dk}{\ell}\right\}$$
  This is derived via a partitioning argument and the construction of an independent set in a quotient graph.
• Numerical Findings on Extremal Trees: Exhaustive searches for trees with fixed $\ell$ and $D$ reveal that the "balanced minimum-height" tree conjectured by Lin–Zhao is not always the maximizer of $\lambda_2$. Specifically, for $\ell=8, D=3$ and $\ell=6, D=4$, unbalanced trees with specific leaf splits yield higher $\lambda_2$ values than the balanced candidates. However, for larger $\ell$, the balanced trees consistently outperform random samples, supporting the conjecture in the asymptotic regime.

Significance and Claims
The paper claims to fundamentally improve the understanding of Steklov eigenvalues on trees by:

1. Establishing a direct link between discrete edge-stretching and spectral monotonicity, providing a discrete counterpart to continuous geometric deformation results.
2. Resolving the constant in the upper bound for $\lambda_2$ on trees, reducing it to the optimal value of 1. The authors emphasize that their method avoids the multiplicative constants inherent in isoperimetric (Cheeger-type) approaches by utilizing direct energy optimization.
3. Providing explicit spectral formulas for a broad class of trees (level-regular), which serve as a large family of test candidates for extremal problems.
4. Refining the search space for extremal trees by showing that the "balanced minimum-height" conjecture requires the condition "$\ell$ sufficiently large" to hold, as counterexamples exist for small leaf counts.

The work positions these results within the broader extremal program for Steklov eigenvalues, offering tools (monotonicity, sharp bounds, explicit spectra) to further investigate the structure of trees that maximize spectral invariants under degree and leaf constraints.