Subdivision and Graph Eigenvalues

NEW

Problem: For a finite simple graph $G$, a fixed set $S\subseteq E(G)$, and $t\ge1$, let $G_t=G_t(S)$ be obtained by replacing every edge of $S$ by a path of length $t$. Let $H_t=H_t(S)$ be obtained from $G_{2t+1}$ by deleting the middle edge in each stretched $S$-path. For an interval $I$, let $m_X(I)$ be the number of adjacency eigenvalues of $X$ in $I$, counted with multiplicity.

Conjecture 21 asks whether

$$\max_{t\ge1}m_{H_t}(2,\infty)=\max_{t\ge1}m_{G_t}(2,\infty)$$

and

$$\max_{t\ge1}m_{H_t}(-\infty,-2)=\max_{t\ge1}m_{G_t}(-\infty,-2).$$

Result: The conjecture is true.

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

$$B=2I-A_0-D,\qquad C=-2I-A_0+D.$$

Then in fact

$$\max_t m_{G_t}(2,\infty)=\max_t m_{H_t}(2,\infty)=n_-(B),$$

and

$$\max_t m_{G_t}(-\infty,-2)=\max_t m_{H_t}(-\infty,-2)=n_+(C),$$

where $n_-$ and $n_+$ denote negative and positive inertia.

Proof. Let $p_0(x)=1$, $p_1(x)=x$, $p_k(x)=xp_{k-1}(x)-p_{k-2}(x)$, the characteristic polynomial of a path on $k$ vertices, and set $p_{-1}=0$. Then

$$p_k(2)=k+1,\qquad p_k(-2)=(-1)^k(k+1).$$

By Schur complementation on the internal path vertices, for $|\lambda|>2$,

$$F_{G,t}(\lambda)=\lambda I-A_0-\frac{p_{t-2}(\lambda)}{p_{t-1}(\lambda)}D-\frac1{p_{t-1}(\lambda)}A_S$$

detects the eigenvalues of $G_t$ outside $[-2,2]$, while

$$F_{H,t}(\lambda)=\lambda I-A_0-\frac{p_{t-1}(\lambda)}{p_t(\lambda)}D$$

detects those of $H_t$. Since the eliminated path blocks have spectrum in $(-2,2)$, the Schur complements are well-defined at $\lambda=\pm2$. Also

$$F'(\lambda)=I+R(\lambda)^2$$

in Schur-complement form, hence is positive definite; therefore the number of roots above $2$ is $n_-(F(2))$, and the number of roots below $-2$ is $n_+(F(-2))$.

Evaluating at $2$ gives

$$m_{G_t}(2,\infty)=n_-\!\left(B+\frac1t(D-A_S)\right),$$ $$m_{H_t}(2,\infty)=n_-\!\left(B+\frac1{t+1}D\right).$$

Both $D-A_S$ and $D$ are positive semidefinite. Hence each negative inertia is at most $n_-(B)$, and for all sufficiently large $t$, by continuity of eigenvalues, the negative inertia equals $n_-(B)$. Thus the positive-side maxima are both $n_-(B)$.

Similarly, evaluating at $-2$,

$$m_{G_t}(-\infty,-2) = n_+\!\left(C-\frac1t\bigl(D+(-1)^{t-1}A_S\bigr)\right),$$ $$m_{H_t}(-\infty,-2) = n_+\!\left(C-\frac1{t+1}D\right).$$

Here $D-A_S$, $D+A_S$, and $D$ are positive semidefinite. Thus these matrices are all $\le C$ in Loewner order, so their positive inertia is at most $n_+(C)$. For sufficiently large $t$, the perturbations have arbitrarily small norm, so all positive eigenvalues of $C$ remain positive. Hence both negative-side maxima are $n_+(C)$.

This proves both asserted equalities.

Citation: Conjecture source: Hitesh Kumar, Bojan Mohar, Shivaramakrishna Pragada, Hanmeng Zhan, “Subdivision and Graph Eigenvalues,” arXiv:2303.10488, Conjecture 21. No prior resolution is used here.