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 -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 -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 -chessboard complex is the abstract simplicial complex with vertex set that contains all subsets S such that, if and are two distinct elements of S, then both and. The vertex set can be viewed as a two-dimensional grid, 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 .
Another definition is the set of all matchings in the complete bipartite graph.
Examples
In any -chessboard complex, the neighborhood of each vertex has the structure of a -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 -chessboard complex, and the - and -chessboard complexes within it:- The -chessboard complex is a hexagon, consisting of six vertices connected by six edges.
- The -chessboard complex is a triangulation of a torus, with 24 triangles, 36 edges, and 12 vertices. Six triangles meet at each vertex, in the same hexagonal pattern as the -chessboard complex.
- The -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 contains elements. Therefore, the dimension of is.The homotopical connectivity of the chessboard complex is at least .
The Betti numbers of chessboard complexes are zero if and only if. The eigenvalues of the combinatorial Laplacians of the chessboard complex are integers.
The chessboard complex is -connected, where. 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.
The -skeleton of chessboard complex is vertex decomposable in the sense of Provan and Billera, and the entire complex is vertex decomposable if. 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.