Subdivision and Graph Eigenvalues

NEW

Problem: Reconstructed Conjecture 20. Fix a finite simple graph $G=(V,E)$ and a fixed subset $S\subseteq E$. For $t\ge1$, let $G_t=G_t(S)$ be obtained by replacing every edge of $S$ by a path of length $t$, leaving edges of $E\setminus S$ unchanged. For a graph $X$, let

$$m_X(-\infty,-2)=\#\{\text{adjacency eigenvalues of }X\text{ strictly less than }-2\},$$

counted with multiplicity. Then there is $t_0$ such that $m_{G_t}(-\infty,-2)$ is constant for all $t\ge t_0$.

This is the natural formalization because the paper defines $G_t(S)$ for a fixed $G,S$ immediately before the conjecture and defines $m_G(I)$ as interval eigenvalue multiplicity.

Result: The conjecture is true.

Let $A_S$ be the adjacency matrix of the spanning subgraph $(V,S)$, let $A_0$ be the adjacency matrix of $(V,E\setminus S)$, and let $D_S=\operatorname{diag}(d_S(v))$. Define

$$K_\infty:=D_S-2I-A_0 .$$

Then, for all sufficiently large $t$,

$$m_{G_t}(-\infty,-2)=n_+(K_\infty),$$

where $n_+(M)$ denotes the number of positive eigenvalues of a real symmetric matrix $M$.

Proof. Put

$$B_t=-2I-A(G_t).$$

An adjacency eigenvalue $\lambda<-2$ of $G_t$ corresponds exactly to a positive eigenvalue $-2-\lambda$ of $B_t$. Hence

$$m_{G_t}(-\infty,-2)=n_+(B_t).$$

Partition $V(G_t)$ into the original vertex set $V$ and the internal vertices inserted on the subdivided edges. For one subdivided edge of length $t$, the internal block is

$$T_{t-1}= \begin{pmatrix} -2&-1\\ -1&-2&-1\\ &\ddots&\ddots&\ddots\\ &&-1&-2 \end{pmatrix}.$$

Its eigenvalues are

$$-2-2\cos\frac{k\pi}{t},\qquad k=1,\dots,t-1,$$

all strictly negative, so the full internal block is negative definite.

The needed inverse entries are

$$(T_{t-1}^{-1})_{11}=(T_{t-1}^{-1})_{t-1,t-1}=-\frac{t-1}{t}, \qquad (T_{t-1}^{-1})_{1,t-1}=\frac{(-1)^{t-1}}{t}.$$

Thus the Schur complement of the internal block in $B_t$, indexed by $V$, is

$$K_t = D_S-2I-A_0+\frac1t\bigl(-D_S+(-1)^tA_S\bigr).$$

By Sylvester inertia law, since the eliminated internal block is negative definite,

$$n_+(B_t)=n_+(K_t).$$

Now

$$K_t=K_\infty+\frac1t R_t, \qquad R_t=-D_S+(-1)^tA_S.$$

If $t$ is even, then

$$R_t=-D_S+A_S=-L_S,$$

the negative Laplacian of $(V,S)$, so $R_t\le0$. If $t$ is odd, then

$$R_t=-D_S-A_S=-Q_S,$$

the negative signless Laplacian of $(V,S)$, so again $R_t\le0$. Therefore $K_t\le K_\infty$ in Loewner order.

Let $p=n_+(K_\infty)$. Since $K_t\le K_\infty$, Weyl monotonicity gives

$$\lambda_{p+1}(K_t)\le \lambda_{p+1}(K_\infty)\le0,$$

so $n_+(K_t)\le p$ for every $t$. On the other hand, $K_t\to K_\infty$ in operator norm. Hence every positive eigenvalue of $K_\infty$ remains positive in $K_t$ for all sufficiently large $t$. Thus $n_+(K_t)\ge p$ eventually. Therefore

$$n_+(K_t)=p$$

for all sufficiently large $t$, and consequently

$$m_{G_t}(-\infty,-2)=p$$

for all sufficiently large $t$.

This proves the conjecture.

Verification audit: The proof uses exactly the paper’s $G_t(S)$, finite simple graphs, adjacency eigenvalues, and strict interval $(-\infty,-2)$. The threshold $-2$ is handled by inertia of $-2I-A(G_t)$, so eigenvalues equal to $-2$ are not counted. The internal path block is verified negative definite, justifying Schur complements and inertia additivity. No connectedness or nonemptiness assumption on $S$ is added.

Citation: Kumar–Mohar–Pragada–Zhan, “Subdivision and Graph Eigenvalues,” arXiv:2303.10488, for the conjecture and notation. The resolution above is self-contained.