Chessboard complex

For any two positive integers m and n, the (m, n)-chessboard complex $\backslash Delta\_\{m,n\}$ is the abstract simplicial complex with vertex set $[m]\backslash 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\backslash neq\; i\_2$ and $j\_1\backslash 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)^\{*n\}\_\{\backslash Delta(2)\}$.{{Cite Matousek 2007}}{{Rp|page=176}}

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

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:{{cite thesis|url=https://www.unhyperbolic.org/research/matthias_goerner_thesis_print.pdf|contribution=1.2.2 Relationship to the 4 × 5 Chessboard Complex|title=Visualizing Regular Tessellations: Principal Congruence Links and Equivariant Morphisms from Surfaces to 3-Manifolds|first=Matthias Rolf Dietrich|last=Goerner|publisher=University of California, Berkeley|year=2011|type=Doctoral dissertation}}

• 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.

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

The homotopical connectivity of the chessboard complex is at least $\backslash min\backslash left(m,\; n,\; \backslash frac\{m+n+1\}\{3\}\backslash right)-2$ (so $\backslash eta\; \backslash geq\; \backslash min\backslash left(m,\; n,\; \backslash frac\{m+n+1\}\{3\}\backslash right)$).{{Rp|location=Sec.1}}

The Betti numbers $b\_\{r\; -\; 1\}$ of chessboard complexes are zero if and only if $(m\; -\; r)(n\; -\; r)\; >\; r$.{{Cite journal |last=Friedman |first=Joel |last2=Hanlon |first2=Phil |date=1998-09-01 |title=On the Betti Numbers of Chessboard Complexes |url=https://doi.org/10.1023/A:1008693929682 |journal=Journal of Algebraic Combinatorics |language=en |volume=8 |issue=2 |pages=193–203 |doi=10.1023/A:1008693929682 |issn=1572-9192|hdl=2027.42/46302 |hdl-access=free }}{{Rp|page=200}} The eigenvalues of the combinatorial Laplacians of the chessboard complex are integers.{{Rp|page=193}}

The chessboard complex is $(\backslash nu\_\{m,\; n\}\; -\; 1)$-connected, where $\backslash nu\_\{m,\; n\}\; :=\; \backslash min\backslash \{m,\; n,\; \backslash lfloor\backslash frac\{m\; +\; n\; +\; 1\}\{3\}\backslash rfloor\; \backslash \}$.{{Cite journal |last=Shareshian |first=John |last2=Wachs |first2=Michelle L. |date=2007-07-10 |title=Torsion in the matching complex and chessboard complex |journal=Advances in Mathematics |language=en |volume=212 |issue=2 |pages=525–570 |doi=10.1016/j.aim.2006.10.014 |doi-access=free |issn=0001-8708|arxiv=math/0409054 }}{{Rp|page=527}} The homology group $H\_\{\backslash 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\; \backslash equiv\; 1\backslash pmod\{3\}$.{{Rp|pages=543–555}}

The $(\backslash lfloor\backslash frac\{n\; +\; m\; +\; 1\}\{3\}\backslash 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\backslash geq\; 2m\; -\; 1$.{{Cite web |last=Ziegler |first=Günter M. |date=1992-09-23 |title=Shellability of Chessboard Complexes. |url=https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/89}}{{Rp|page=3}} As a corollary, any position of k rooks on a m-by-n chessboard, where $k\backslash leq\backslash lfloor\backslash frac\{m\; +\; n\; +\; 1\}\{3\}\backslash 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).{{Rp|page=3}}

The complex $\backslash Delta\_\{n\_1,\backslash ldots,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 $(\backslash nu\; -\; 2)$-connected, for $\backslash nu\; :=\; \backslash min\backslash \{n\_1,\; \backslash lfloor\backslash frac\{n\_1\; +\; n\_2\; +\; 1\}\{3\}\backslash rfloor,\; \backslash dots,\; \backslash lfloor\backslash frac\{n\_1\; +\; n\_2\; +\; \backslash dots\; +\; n\_k\; +\; 1\}\{2k\; +\; 1\}\backslash rfloor\backslash \}$ {{Rp|page=33}}

{{Reflist}}

Category:Topological graph theory