On the Betti numbers of chessboard complexes (Q1272900): Difference between revisions

An admissible rook configuration on an \(m \times n\) chessboard is a subset of squares of the chessboard such that no two squares lie in the same row or column. The collection of such configurations forms an abstract simplicial complex \(C(m,n)\), called the chessboard complex. These complexes arise in various combinatorial settings. For the first time, in the thesis of \textit{P. F. Garst} (1979), in connection with coset complexes of finite symmetric groups. Later, in a paper by \textit{R. T. Živaljević} and \textit{S. T. Vrećica} [J. Comb. Theory, Ser. A 61, No. 2, 309-318 (1992; Zbl 0782.52003)], in some combinatorial geometry problems where understanding the connectivity properties of \(C(m,n)\) were important. In a paper by \textit{A. Björner}, \textit{L. Lovász}, \textit{S. T. Vrećica} and \textit{R. T. Živaljević} [J. Lond. Math. Soc., II. Ser. 49, No. 1, 25-39 (1994; Zbl 0790.57014)] it was proved that \(C(m,n)\) is \((\nu-2)\)-connected, where \(\nu = \text{ min}(m,n,\lfloor (m+n+1)/3 \rfloor)\), and it was conjectured that \(C(m,n)\) is not \((\nu-1)\)-connected. In the paper under review, this conjecture is verified with the aid of the Betti numbers of \(C(m,n)\) in the case in which \(n \geq 2m-4\) or \((m,n) = (6,6), (7,7), (8,9)\). Moreover, it is shown that in the other cases if the conjecture holds it is due to torsion in the rational homology group \(H_{\nu-1}(C(m,n))\). The method applied in this paper is to study the combinatorial Laplacians, which are most easily described via Hodge theory. It was empirically observed by the first named author [Algorithmica 21, No. 4, 331-346 (1998; Zbl 0911.57021)] that the eigenvalues of the Laplacians of \(C(m,n)\) are integers. The authors prove this observation, and give a formula for the multiplicity of the eigenvalues in terms of certain partitions. The dimension of the kernel of the \(i\)-th Laplacian on \(C(m,n)\) is just the \(i\)-th Betti number of \(C(m,n)\). Using this, the authors obtain a formula for the Betti numbers of \(C(m,n)\) and determine exactly which Betti numbers vanish.