Английская Википедия:Chessboard complex
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.
Definitions
For any two positive integers m and n, the (m, n)-chessboard complex <math>\Delta_{m,n}</math> is the abstract simplicial complex with vertex set <math>[m]\times [n]</math> that contains all subsets S such that, if <math>(i_1,j_1)</math> and <math>(i_2,j_2)</math> are two distinct elements of S, then both <math>i_1\neq i_2</math> and <math>j_1\neq j_2</math>. 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 <math>(D_m)^{*n}_{\Delta(2)}</math>.[3]Шаблон:Rp
Another definition is the set of all matchings in the complete bipartite graph <math>K_{m,n}</math>.[1]
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:[4]
- 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 <math>\Delta_{m,n}</math> contains <math>\min(m,n)</math> elements. Therefore, the dimension of <math>\Delta_{m,n}</math> is <math>\min(m,n)-1</math>.
The homotopical connectivity of the chessboard complex is at least <math>\min\left(m, n, \frac{m+n+1}{3}\right)-2</math> (so <math>\eta \geq \min\left(m, n, \frac{m+n+1}{3}\right)</math>).[1]Шаблон:Rp
The Betti numbers <math>b_{r - 1}</math> of chessboard complexes are zero if and only if <math>(m - r)(n - r) > r</math>.[5]Шаблон:Rp The eigenvalues of the combinatorial Laplacians of the chessboard complex are integers.[5]Шаблон:Rp
The chessboard complex is <math>(\nu_{m, n} - 1)</math>-connected, where <math>\nu_{m, n} := \min\{m, n, \lfloor\frac{m + n + 1}{3}\rfloor \}</math>.[6]Шаблон:Rp The homology group <math>H_{\nu_{m, n}}(M_{m, n})</math> is a 3-group of exponent at most 9, and is known to be exactly the cyclic group on 3 elements when <math>m + n \equiv 1\pmod{3}</math>.[6]Шаблон:Rp
The <math>(\lfloor\frac{n + m + 1}{3}\rfloor - 1)</math>-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 <math>n\geq 2m - 1</math>.[7]Шаблон:Rp As a corollary, any position of k rooks on a m-by-n chessboard, where <math>k\leq\lfloor\frac{m + n + 1}{3}\rfloor</math>, can be transformed into any other position using at most <math>mn - k</math> single-rook moves (where each intermediate position is also not rook-taking).[7]Шаблон:Rp
Generalizations
The complex <math>\Delta_{n_1,\ldots,n_k}</math> 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 <math>(\nu - 2)</math>-connected, for <math>\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\}</math> [1]Шаблон:Rp
References
