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

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

Then, for all sufficiently large $t$,

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

Proof. Put

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

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

Its eigenvalues are

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

The needed inverse entries are

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

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

Now

If $t$ is even, then

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

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

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

for all sufficiently large $t$, and consequently

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.