Chessboard complex

Short description: Mathematical object in topological graph theory

A chessboard complex is a particular kind of abstract simplicial complex, which has various applications in topological graph theory and algebraic topology. Informally, the (m, n)-chessboard complex contains all sets of positions on an m-by-n chessboard, where rooks can be placed without attacking each other. Equivalently, it is the matching complex of the (m, n)-complete bipartite graph, or the independence complex of the m-by-n rook's graph.

Definitions

For any two positive integers m and n, the (m, n)-chessboard complex ${\mathrm{\Delta }}_{m,n}$ is the abstract simplicial complex with vertex set $[m]\times [n]$ that contains all subsets S such that, if $(i_1,j_1)$ and $(i_2,j_2)$ are two distinct elements of S, then both $i_1\ne i_2$ and $j_1\ne j_2$. The vertex set can be viewed as a two-dimensional grid (a "chessboard"), and the complex contains all subsets S that do not contain two cells in the same row or in the same column. In other words, all subset S such that rooks can be placed on them without taking each other.

The chessboard complex can also be defined succinctly using deleted join. Let D_m be a set of m discrete points. Then the chessboard complex is the n-fold 2-wise deleted join of D_m, denoted by $(D_m{)}_{\mathrm{\Delta }(2)}^{*n}$.

Another definition is the set of all matchings in the complete bipartite graph $K_{m,n}$.

Examples

In any (m,n)-chessboard complex, the neighborhood of each vertex has the structure of a (m − 1,n − 1)-chessboard complex. In terms of chess rooks, placing one rook on the board eliminates the remaining squares in the same row and column, leaving a smaller set of rows and columns where additional rooks can be placed. This allows the topological structure of a chessboard to be studied hierarchically, based on its lower-dimensional structures. An example of this occurs with the (4,5)-chessboard complex, and the (3,4)- and (2,3)-chessboard complexes within it:

• The (2,3)-chessboard complex is a hexagon, consisting of six vertices (the six squares of the chessboard) connected by six edges (pairs of non-attacking squares).
• The (3,4)-chessboard complex is a triangulation of a torus, with 24 triangles (triples of non-attacking squares), 36 edges, and 12 vertices. Six triangles meet at each vertex, in the same hexagonal pattern as the (2,3)-chessboard complex.
• The (4,5)-chessboard complex forms a three-dimensional pseudomanifold: in the neighborhood of each vertex, 24 tetrahedra meet, in the pattern of a torus, instead of the spherical pattern that would be required of a manifold. If the vertices are removed from this space, the result can be given a geometric structure as a cusped hyperbolic 3-manifold, topologically equivalent to the link complement of a 20-component link.

Properties

Every facet of ${\mathrm{\Delta }}_{m,n}$ contains $\min (m,n)$ elements. Therefore, the dimension of ${\mathrm{\Delta }}_{m,n}$ is $\min (m,n)-1$.

The homotopical connectivity of the chessboard complex is at least $\min (m,n,\frac{m+n+1}{3})-2$ (so $\eta \ge \min (m,n,\frac{m+n+1}{3})$).

The Betti numbers $b_{r-1}$ of chessboard complexes are zero if and only if $(m-r)(n-r)>r$. The eigenvalues of the combinatorial Laplacians of the chessboard complex are integers.

The chessboard complex is $({\nu }_{m,n}-1)$-connected, where ${\nu }_{m,n}:=\min \{m,n,\lfloor \frac{m+n+1}{3}\rfloor \}$. The homology group $H_{{\nu }_{m,n}}(M_{m,n})$ is a 3-group of exponent at most 9, and is known to be exactly the cyclic group on 3 elements when $m+n\equiv 1(\mathrm{mod}3)$.

The $(\lfloor \frac{n+m+1}{3}\rfloor -1)$-skeleton of chessboard complex is vertex decomposable in the sense of Provan and Billera (and thus shellable), and the entire complex is vertex decomposable if $n\ge 2m-1$. As a corollary, any position of k rooks on a m-by-n chessboard, where $k\le \lfloor \frac{m+n+1}{3}\rfloor$, can be transformed into any other position using at most $mn-k$ single-rook moves (where each intermediate position is also not rook-taking).

Generalizations

The complex ${\mathrm{\Delta }}_{n_1,\dots ,n_k}$ is a "chessboard complex" defined for a k-dimensional chessboard. Equivalently, it is the set of matchings in a complete k-partite hypergraph. This complex is at least $(\nu -2)$-connected, for $\nu :=\min \{n_1,\lfloor \frac{n_1+n_2+1}{3}\rfloor ,\dots ,\lfloor \frac{n_1+n_2+\dots +n_k+1}{2k+1}\rfloor \}$