A chessboard complex is a particular kind of abstract simplicial complex, which has various applications in topological graph theory and algebraic topology.
[1][2] 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.
For any two positive integers m and n, the (m, n)-chessboard complex
is the abstract simplicial complex with vertex set
are two distinct elements of S, then both
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 Dm be a set of m discrete points.
Then the chessboard complex is the n-fold 2-wise deleted join of Dm, denoted by
[3]: 176 Another definition is the set of all matchings in the complete bipartite graph
[1] 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.
The homotopical connectivity of the chessboard complex is at least
η ≥ min
[1]: Sec.1 The Betti numbers
of chessboard complexes are zero if and only if
{\displaystyle (m-r)(n-r)>r}
[5]: 200 The eigenvalues of the combinatorial Laplacians of the chessboard complex are integers.
[6]: 527 The homology group
is a 3-group of exponent at most 9, and is known to be exactly the cyclic group on 3 elements when
-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
[7]: 3 As a corollary, any position of k rooks on a m-by-n chessboard, where
, can be transformed into any other position using at most
single-rook moves (where each intermediate position is also not rook-taking).
is a "chessboard complex" defined for a k-dimensional chessboard.
Equivalently, it is the set of matchings in a complete k-partite hypergraph.
ν := min {