Measurable Nikiforov

Nikiforov bound.

Let $G$ be an (undirected) finite graph with top adjacency eigenvalue $\mu_1$, and top Laplacian eigenvalue $\lambda_1$. then

$$ \chi(G)\ge \left\lceil 1+ \frac{\mu_1}{\lambda_1-\mu_1} \right\rceil $$

</aside>

Nikiforov Bound, measurable.

Let $\mathcal G$ be an (undirected) bounded-degree pmp Borel graph on a Polish space $(X,\mu)$ with adjacency operator $T_\mathcal G$ and Laplacian operator $L_\mathcal G$. Then

$$ \chi_\mu(G)\ge \left\lceil 1+ \frac{M(T_\mathcal G)} {M(L_\mathcal G)-M(T_\mathcal G)} \right\rceil $$

</aside>

Theorem 1

Nikiforov Theorem 1.

Let $A$ be a Hermitian matrix partitioned into $r$ blocks by $r$ blocks so that all diagonal blocks $A_{1,1},\dots,A_{r,r}$ are zero. Then for every real diagonal matrix $B$ of the same size as $A$,

$$ \mu(B-A) \ge \mu\left(B+\frac 1{r-1} A\right) $$

</aside>

Def. An operator $S:L^2(X)$ is a multiplication operator if there exists a multiplication function $\sigma:X\to \mathbb C$ such that

$$ \forall f\in L^2(X),\ \forall x\in X \quad (S(f))(x)=\sigma(x)f(x) $$

</aside>

Nikiforov Theorem 1, measurable.

Let $T:L^2(X)\to L^2(X)$ be bounded, self-adjoint, with $(X,\mu)$ a measure space. Suppose there are measurable disjoint $X_1,\dots,X_k$ such that

$$ X=\bigsqcup_{i=1}^k X_i $$

and the block decomposition of $T$ over $\left\{ X_1,\dots,X_k \right\}$ has $0$s in $(1,1),\dots,(k,k)$.

Then, for any real bounded multiplication operator $S:L^2(X)\to L^2(X)$,

$$ M(S-T) \ge M\left(S+\frac 1{k-1} T\right) $$

</aside>

Let

$$ L=S-T,\quad K = (k-1) S + T =(k-1) \left(S+\frac 1{k-1} T\right) $$

Let $(\mathbf f_n)_{n\in \N}$ be a sequence of unit vectors in $L^2(X)$ such that

$$ \forall n\in \N\quad M(K) - \lang K\mathbf f_n, \mathbf f_n\rang <\frac 1n $$

Goal: to define $k$ sequences of vectors $(\mathbf g_{1n}){n\in \N},\dots,(\mathbf g{kn})_{n\in \N}$ to achieve a sequence of inequalities:

$$ \small k(k-1)M(L) \overset{(1)}= M(L) \sum_{i\in [k]} \|\mathbf g_{in}\|^2 \overset{(2)}\ge \sum {i\in [k]} \left\lang L \mathbf g{in}, \mathbf g_{in} \right\rang \overset{(3)}= k\left\lang K\mathbf f_n,\mathbf f_n \right \rang \overset{(4)} \ge k \left( M(K) -\frac 1n\right) $$

For each $i\in [k]$, define a sequence $(\mathbf g_{in})_{n\in \N}$ such that

$$ \mathbf g _{in}(x) =\begin{cases} -(k-1) \mathbf f_n(x) &\text{if } x\in X_i\\ \mathbf f_n(x) &\text{if } x\notin X_i

\end{cases} $$

where the $X_i$s are the color sets, i.e. $X_i=c^{-1}\{i\}$.

(1) $\small k(k-1) = \sum\limits_{i\in [k]} \|\mathbf g_{in}\|^2$
(2)

$M(L) \sum\limits_{i\in [k]} \|\mathbf g_{in}\|^2 \ge \sum\limits {i\in [k]} \left\lang L \mathbf g{in}, \mathbf g_{in} \right\rang$

(3) $\sum \limits_{i\in [k]} \left\lang L \mathbf g_{in}, \mathbf g_{in} \right\rang = k\left\lang K\mathbf f_n,\mathbf f_n \right \rang$