Chessboard Complex

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 $\Delta_$ is the abstract simplicial complex with vertex set times /math> 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\neq i_2$ and $j_1\neq 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)^_$''.

Another definition is the set of all matchings in the complete bipartite graph $K_$.

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 $\Delta_$ contains $\min(m,n)$ elements. Therefore, the dimension of $\Delta_$ is $\min(m,n)-1$.

The homotopical connectivity of the chessboard complex is at least $\min\left(m, n, \frac\right)-2$ (so $\eta \geq \min\left(m, n, \frac\right)$).

The Betti numbers $b_$ 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_ - 1)$-connected, where $\nu_ := \min\$. The homology group $H_(M_)$ 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\pmod$.

The $(\lfloor\frac\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\geq 2m - 1$. As a corollary, any position of ''k'' rooks on a ''m''-by-''n'' chessboard, where $k\leq\lfloor\frac\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 $\Delta_$ 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\$

References

{{Reflist
Topological graph theory