Necessary Spectral Conditions for Coloring Hypergraphs

Abstract

Hoffman proved that for a simple graph $G$, the chromatic number $\chi (G)$ obeys $\chi (G)\ge 1–\frac{{\lambda }_1}{{\lambda }_n}$, where ${\lambda }_1$ and ${\lambda }_n$ are the maximal and minimal eigenvalues of the adjacency matrix of $G$, respectively. Lovász later showed that $\chi (G)\ge 1–\frac{{\lambda }_1}{{\lambda }_n}$ for any (perhaps negatively) weighted adjacency matrix.

In this paper, we give a probabilistic proof of Lovász’s theorem, then extend the technique to derive generalizations of Hoffman’s theorem when allowed a certain proportion of edge-conflicts. Using this result, we show that if a $3$-uniform hypergraph is $2$-colorable, then $\overline{d}\le –\frac{3}{2}{\lambda }_{\text{min}}$ where $\overline{d}$ is the average degree and ${\lambda }_{\text{min}}$ is the minimal eigenvalue of the underlying graph. We generalize this further for $k$-uniform hypergraphs, for the cases $k=4$ and $5$, by considering several variants of the underlying graph.