Department of Computational and Applied Mathematics

The chromatic number of a graph (or hypergraph) is minimum number of colors needed such that the vertices can be assigned each one color and no edge is monochromatic. A classical result of Hoffman (1969) bounds the chromatic number of a graph in terms of the maximum and minimum eigenvalues of the adjacency matrix.

In our talk, we expand on Hoffman's result by using spectral theory and probabilistic methods in concert. We give a probabilistic proof of Hoffman's theorem and derive several adaptations.

Lastly, we expand these results to hypergraphs where we give necessary conditions 2-coloring 3-, 4-, and 5- uniform hypergraphs. We apply our results examples and give applications to Ramsey theory.