On the chromatic number of a simplicial complex (Q722323)

The chromatic number \(\chi(G)\) of a graph \(G\) is the minimal number of colors needed to color its vertices \(V\) in such a way that no edge is monochromatic. It has been studied extensively by different methods. The spectral method bounds \(\chi(G)\) by means of the spectra of various operators is defined on the graph. An advantage of the method is that the spectrum of an operator on a finite graph can be calculated in polynomial time, while the problem of finding the chromatic number of a graph is NP-complete. The Laplacian \(\Delta\) of a graph \(G\) is an operator on the space \(C^0\) of the real-valued functions on the vertex set \(V\) of \(G\) acting by the rule \[ \Delta f(v)=\operatorname{deg}v\cdot f(v)-\sum_{u\sim v}f(u), \] where \(\text{deg}v\), \(v\in V\), is the number of vertices adjacent to \(v\), and \(u\sim v\) means that \(u\) and \(v\) are connected by an edge. The paper \textit{A. J. Hoffman} [in: Graph theory and its applications. Proceedings of an advanced seminar conducted by the Mathematics Research Center, United States Army, at the University of Wisconsin, Madison, October 13--15, 1969. New York - London: Academic Press. 79--91 (1970; Zbl 0221.05061)] gives a lower bound on the chromatic number of a graph in the terms of the largest and the smallest eigenvalues of its adjacency matrix. In the paper under review, the author establishes a higher dimensional version of this result and gives a lower bound on the chromatic number of a pure \(d\)-dimensional simplicial complex in terms of the spectra of the higher Laplacian operators introduced in \textit{B. Eckmann}, [Comment. Math. Helv. 17, 240--255 (1945; Zbl 0061.41106)]. The finite pure \(d\)-dimensional abstract simplicial complex is a family \(X\) of subsets (called faces) of a finite vertex set \(V\) closed under taking subsets, such that every maximal subset in the family is of size \(d+1\). The chromatic number \(\chi(X)\) is the least number of colors needed to color its vertices in such a way that no maximal face is monochromatic. In the special case of a pure \(d\)-dimensional simplicial complex with a complete \((d-1)\)-skeleton, a different shorter proof is given.