Suppose $G$ is a $d$-regular (finite) graph for some $d \geq 1$. Let $A$ denote the adjacency matrix of $G$, and let $L$ denote the Laplacian of $G$.
-
Prove that $\sigma(L) = d - \sigma(A)$.
Since $G$ is $d$-regular, its degree matrix is simply $dI$ (where $I$ is the identity operator).
For any spectral value $\lambda\in \sigma(A)$, there exists a sequence of eigenvectors $(\xi_n)_{n\in \N}$ in $L^2(V(G))$ such that
$$ \left\|A\xi_n-\lambda\xi_n\right\| \to 0 $$
Then, notice
$$ \left\|L\xi_n-(d-\lambda)\xi_n\right\|
\left\|d\xi_n-A\xi_n-d\xi_+\lambda\xi_n\right\|
\left\|-A\xi_n+\lambda\xi_n\right\| \to 0 $$
So $d-\lambda$ is a spectral value of $\sigma(L)$ and $d - \sigma(A) \sube \sigma(L)$
Similarly for the other inclusion.
-
Prove that $d < \max\sigma(L) \leq 2d$.
Since $\sigma(L) = d - \sigma(A)$, it suffices to show
$$ -d\le \min\sigma(A)\le 0 $$
The spectrum of $A$ is bounded by its operator norm,
$$ \sigma (A)\sube \left[-\|A\|, \|A\|\right] $$
And we showed previously that $A$ is bounded with $\|A\|\le d$. So indeed $-d\le\min\sigma(A)$.
We also showed previously that the min eigenvalue of $A$ is negative, i.e. $\min\sigma(A)\le 0$, as desired.
-
Prove that Nikiforov's bound reduces to Hoffman's bound.
For a $d$-regular graph, we can show $\mu(A)=d$.
First, $d$ is an eigenvalue with the all-ones eigenvector $\vec 1 = (1\ \cdots \ 1)$. And since $A$ is self-adjoint, we can orthogonalize all other eigenvectors with respect to $\vec 1$. That is, we can guarantee that any other eigenvector $\vec v$ corresponding to some other eigenvalue $\lambda$ will have some negative entries (to guarantee that $\vec v \cdot \vec 1 = 0$).
Then, by Perron-Frobenius theorem, $A$ has a strictly positive eigenvector associated with its largest eigenvalue. And since $\vec 1$ is the only strictly positive eigenvector, $d$ must be the largest eigenvalue.
So
$$
-\mu_{\min}(A) = \mu(L)-d = \mu(L)-\mu(A)\\
1+\frac{\mu(A)}{-\mu_{\min}(A)} =1+\frac{\mu(A)}{ \mu(L)-\mu(A)} $$
Find a (finite) graph $G$ for which Nikiforov's lower bound is tighter than Hoffman's. [Feel free to use Wolfram!]
Want to find a graph such that
$$ 1+\frac{\mu(A)}{\mu(L)-\mu(A)} \ge 1+\frac{\mu(A)}{-\mu_{\min}(A)}\\[4pt]
\frac{1}{\mu(L)-\mu(A)} \ge \frac{1}{-\mu_{\min}(A)}\\[4pt]
-\mu_{\min}(A) \ge\mu(L)-\mu(A) $$
One such graph is pictured below:
with matrices:
$$ A=\begin{pmatrix} 0&1&1&0\\ 1&0&1&1\\ 1&1&0&1\\ 0&1&1&0\\ \end{pmatrix},\quad
L=\begin{pmatrix} 2&-1&-1&0\\ -1&3&-1&-1\\ -1&-1&3&-1\\ 0&-1&-1&2\\ \end{pmatrix} $$
- $\mu(A)=\frac 12\left(1+\sqrt {17}\right)$
- $\mu_{\min}(A)=\frac 12\left(1-\sqrt {17}\right)$
- $\mu(L)=4$
And indeed
$$
-\mu_{\min}(A) \approx 1.56
\ge 4-2.56 \approx\mu(L)-\mu(A) $$
Fill in the details of the proof of Theorem 1 in Nikiforov. In particular:
-
Derive line (4) from the Rayleigh quotient characterization of $\mu(L)$.
(4) states that
$$ \sum_{i\in [r]} \mu(L) \| \mathbf{y}_i \|^2 \ge
\sum_{i\in [r]} \left \lang L \mathbf{y}_i, \mathbf{y}_i \right \rang $$
We can examine this inequality individual term. Take an arbitrary $i\in [r]$. Courant-Fischer tells us that:
$$ \mu(L)
=\sup_{\mathbf{x}\ne 0} \frac{\left \lang L \mathbf{x}, \mathbf{x} \right \rang} {\left \lang \mathbf{x}, \mathbf{x} \right \rang}\ge
\frac{\left \lang L \mathbf{y}_i, \mathbf{y}_i \right \rang}{ \| \mathbf{y}_i \|^2}\\[4pt]
\quad \Rightarrow \quad \mu(L) \| \mathbf{y}_i \|^2 \ge \left \lang L \mathbf{y}_i, \mathbf{y}_i \right \rang $$
-
Explain why $\vert\vert \mathbf{y}i \vert\vert^2 = 1 + r(r - 2) \sum\limits{j \in N_i} \vert x_j \vert^2$
Note that in general, $1+r(r-2)=r^2-2r+1=(r-1)^2$. So:
$$ \begin{align*}
\vert\vert \mathbf{y}i \vert\vert^2 =\sum{j\in [n]} |y_{ij}|^2\\[4pt]
=\sum_{j\in [n]\backslash N_i} |x_{ij}|^2 +\sum_{j\in N_i} |-(r-1)x_{ij}|^2\\[4pt]
=\sum_{j\in [n]\backslash N_i} |x_{ij}|^2 +(r-1)^2\sum_{j\in N_i} |x_{ij}|^2\\[4pt]
=\sum_{j\in [n]\backslash N_i} |x_{ij}|^2 +\sum_{j\in N_i} |x_{ij}|^2 +r(r-2)\sum_{j\in N_i} |x_{ij}|^2\\[4pt]
=\sum_{j\in [n]} |x_{ij}|^2 +r(r-2)\sum_{j\in N_i} |x_{ij}|^2\\[4pt]
=\|\mathbf x\|^2 +r(r-2)\sum_{j\in N_i} |x_{ij}|^2\\[4pt]
= 1 + r(r - 2) \sum\limits_{j \in N_i} \vert x_j \vert^2
\end{align*} $$
-
Explain why $\left\langle L\mathbf{y}i, \mathbf{y}i \right \rangle = \sum\limits{j = 1}^n b_j\vert y{ij}\vert^2 - \sum\limits_{j, k = 1}^n a_{jk}y_{ik}\overline{y_{ij}}$
Since $B$ is diagonal, its $ij$th entry is given by:
$$ B_{ij}=\begin{cases} 0&i\ne j\\ b_i& i=j \end{cases} $$
Using the linearity of matrix multiplication and of the inner product,
$$ \begin{align*}
\left\langle L\mathbf{y}_i, \mathbf{y}_i \right \rangle
\left\langle B\mathbf{y}_i-A\mathbf{y}_i, \mathbf{y}_i \right \rangle \\[4pt]
= \left\langle B\mathbf{y}_i, \mathbf{y}_i \right \rangle - \left\langle A\mathbf{y}_i, \mathbf{y}_i \right \rangle \\[4pt]
= \sum\limits_{j, k = 1}^n B_{jk}y_{ik}\overline{y_{ij}} - \sum\limits_{j, k = 1}^n a_{jk}y_{ik}\overline{y_{ij}}\\[4pt]
= \sum\limits_{j = 1}^n b_{j}y_{ij}\overline{y_{ij}} - \sum\limits_{j, k = 1}^n a_{jk}y_{ik}\overline{y_{ij}}\\[4pt]
= \sum\limits_{j = 1}^n b_j\vert y_{ij}\vert^2 - \sum\limits_{j, k = 1}^n a_{jk}y_{ik}\overline{y_{ij}}
\end{align*} $$
Re-write the (somewhat suspicious...) proof of Lemma 2 in Nikiforov by taking $\mathbf{x}$ to be a unit eigenvector for the maximum eigenvalue of $A$ (rather than of $R + \frac{1}{r - 1}A$).
Taking $\mathbf x$ to be a unit eigenvector for $\mu(A)$, then:
$$ \mu\left(R+\frac1{r-1} A\right) \ge \left\lang \left(R+\frac1{r-1} A\right)\mathbf x, \mathbf x \right\rang\\[4pt] =\left\lang \left(R-A+\frac r{r-1} A\right)\mathbf x, \mathbf x \right\rang =\left\lang \left(R-A\right)\mathbf x, \mathbf x \right\rang
+\frac r{r-1} \left\lang A\mathbf x, \mathbf x \right\rang\\[4pt] \ge
\frac r{r-1} \left\lang A\mathbf x, \mathbf x \right\rang =\frac r{r-1} \mu(A)
$$
Derive inequalities (1) and (2) in Nikiforov from Theorem 1 and Lemma 2.
For (1):
Taking $B=0$ and $A$ as the adjaency matrix of a matrix $G$ with a $r$-coloring,
$$ \mu(-A)\ge \mu\left(\frac 1 {r-1} A\right) \\[4pt]
-\mu_{\min}(A)\ge \frac 1 {r-1}\mu\left( A\right)\\[4pt]
r-1\ge \frac{\mu\left( A\right)}{-\mu_{\min}(A)}\\[4pt]
r\ge 1- \frac{\mu\left( A\right)}{\mu_{\min}(A)} $$
Minimizing $r$ yields $\chi(G)\ge 1- \frac{\mu\left( A\right)}{\mu_{\min}(A)}$ as desired.
For (2):
Combining Lemma 2 & Theorem 1:
$$ \mu(B-A)\ge \mu\left(B+\frac 1 {r-1} A\right) \ge \frac r{r-1} \mu(A) \\[4pt] $$
Taking $B=D$, the degree matrix, and $A$ as the adjacency matrix of a $r$-colorable graph $G$, with $D-A=L$, the Laplacian,
$$ \mu(L)\ge \frac r{r-1} \mu(A) \\[4pt]
r\mu(L)-r \mu(A)\ge \mu(L) \\[4pt]
r\ge \frac{\mu(L)}{\mu(L)- \mu(A)} \\[4pt]
r\ge 1+ \frac{\mu(A)}{\mu(L)- \mu(A)} \\[4pt]
$$
Minimizing $r$ yields $\chi(G)\ge 1+ \frac{\mu(A)}{\mu(L)- \mu(A)}$ as desired.
(Intentionally vague!) Consider whether we can get a new proof of (approximate) measurable Hoffman's bound by adapting the proof of Theorem 1 in Nikiforov. Some extra considerations:
- Getting a bound on $\chi_{\mu}(\mathcal{G})$ will likely be easier than getting a bound on $\chi_{\mu}^{ap}(\mathcal{G})$.
- The proof may be easier if we add in some assumptions, e.g., regularity, ergodicity, and/or spectral gap.