{{Short description|Mathematical object in topological graph theory}}
A '''chessboard complex''' is a particular kind of abstract simplicial complex, which has various applications in topological graph theory and algebraic topology.<ref name=":0">{{Cite journal |last=Björner |first=A. |last2=Lovász |first2=L. |last3=Vrećica |first3=S. T. |last4=Živaljević |first4=R. T. |date=1994-02-01 |title=Chessboard Complexes and Matching Complexes |url=http://doi.wiley.com/10.1112/jlms/49.1.25 |journal=Journal of the London Mathematical Society |language=en |volume=49 |issue=1 |pages=25–39 |doi=10.1112/jlms/49.1.25|url-access=subscription }}</ref><ref>{{Cite journal |last=Vrećica |first=Siniša T. |last2=Živaljević |first2=Rade T. |date=2011-10-01 |title=Chessboard complexes indomitable |url=https://www.sciencedirect.com/science/article/pii/S0097316511000756 |journal=Journal of Combinatorial Theory | series=Series A |language=en |volume=118 |issue=7 |pages=2157–2166 |doi=10.1016/j.jcta.2011.04.007 |doi-access=free |issn=0097-3165|arxiv=0911.3512 }}</ref> 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 ''D<sub>m</sub>'' be a set of ''m'' discrete points. Then the chessboard complex is the ''n''-fold 2-wise deleted join of ''D<sub>m</sub>'', denoted by ''<math>(D_m)^{*n}_{\Delta(2)}</math>''.<ref name=":03">{{Cite Matousek 2007}}</ref>{{Rp|page=176}}
Another definition is the set of all matchings in the complete bipartite graph <math>K_{m,n}</math>.<ref name=":0" />
== 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:<ref>{{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}}</ref> *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>).<ref name=":0" />{{Rp|location=Sec.1}}
The Betti numbers <math>b_{r - 1}</math> of chessboard complexes are zero if and only if <math>(m - r)(n - r) > r</math>.<ref name=":1">{{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 }}</ref>{{Rp|page=200}} The eigenvalues of the combinatorial Laplacians of the chessboard complex are integers.<ref name=":1" />{{Rp|page=193}}
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>.<ref name=":2">{{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 }}</ref>{{Rp|page=527}} 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>.<ref name=":2" />{{Rp|pages=543–555}}
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>.<ref name=":3">{{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}}</ref>{{Rp|page=3}} 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).<ref name=":3" />{{Rp|page=3}}
== 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> <ref name=":0" />{{Rp|page=33}}
== References == {{Reflist}} Category:Topological graph theory