Necessary Spectral Conditions for Coloring Hypergraphs

Abstract

Hoffman proved that for a simple graph $G$, the chromatic number $\chi (G)$ obeys $\chi (G)\le 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)\le 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 $\bar{d}\le -\frac{3}{2}{\lambda }_{\min }$ where $\bar{d}$ is the average degree and ${\lambda }_{\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.

7 pages