A Spectral Lower Bound on Chromatic Numbers using $p$-Energy

Abstract

Let $A_G$ be the adjacency matrix of a simple graph $G$, and let $\ddot{I}‡(G)$, $\ddot{I}{‡}_f(G)$, $\ddot{I}{‡}_q(G)$, $\hat{I}¾(G)$ and $\hat{I}{¾}_f(G)$ denote its chromatic number, fractional chromatic number, quantum chromatic number, orthogonal rank and projective rank, respectively. For $p\ge 0$, we define the positive and negative $p$-energies of $G$ by $${\mathcal{E}}_p^{+}(G)=\sum _{\hat{I}{»}_i>0}\hat{I}{»}_i^p,{\mathcal{E}}_p^{-}(G)=\sum _{\hat{I}{»}_i<0}|\hat{I}{»}_i{|}^p,$$ where $\hat{I}{»}_1\ge \cdots \ge \hat{I}{»}_n$ are the eigenvalues of $A_G$. We prove that for all $p\ge 0$, $$\ddot{I}‡(G)\ge \left\{\ddot{I}{‡}_f(G),\ddot{I}{‡}_q(G),\hat{I}¾(G)\right\}\ge \hat{I}{¾}_f(G)\ge 1+\max {\left\{\frac{{\mathcal{E}}_p^{+}(G)}{{\mathcal{E}}_p^{-}(G)},\frac{{\mathcal{E}}_p^{-}(G)}{{\mathcal{E}}_p^{+}(G)}\right\}}^{\frac{1}{|p-1|}}.$$ This result unifies and strengthens a series of existing bounds corresponding to the cases $p\in \{0,2,\infty \}$. In particular, the case $p=0$ yields the inertia bound $$\ddot{I}{‡}_f(G)\ge \hat{I}{¾}_f(G)\ge 1+\max \left\{\frac{n^{+}}{n^{-}},\frac{n^{-}}{n^{+}}\right\},$$ where $n^{+}$ and $n^{-}$ denote the number of positive and negative eigenvalues of $A_G$, respectively. This resolves two conjectures of Elphick and Wocjan. We also demonstrate that for certain graphs, non-integer values of $p$ provide sharper lower bounds than existing spectral bounds. As an example, we determine $\ddot{I}{‡}_q$ for the Tilley graph, which cannot be achieved using existing (unweighted) $p$-energy bounds. Our proof employs a novel synthesis of linear algebra and measure-theoretic tools, which allows us to surpass existing spectral bounds.

20 pages, 4 figures, 1 table. v5 adds a conjecture on the vector chromatic number at the end; this is the submitted version. v4 extends the method of v3 to establish a lower bound on the projective rank and resolves two inertia conjectures of Elphick and Wocjan. Supersedes all previous preliminary versions. v3 introduced three authors and extended the original proof to the case $p>1$