Menu
Home Explore People Places Arts History Plants & Animals Science Life & Culture Technology
On this page
Chessboard complex
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. 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.

We don't have any images related to Chessboard complex yet.
We don't have any YouTube videos related to Chessboard complex yet.
We don't have any PDF documents related to Chessboard complex yet.
We don't have any Books related to Chessboard complex yet.
We don't have any archived web articles related to Chessboard complex yet.

Definitions

For any two positive integers m and n, the (m, n)-chessboard complex Δ m , n {\displaystyle \Delta _{m,n}} is the abstract simplicial complex with vertex set [ m ] × [ n ] {\displaystyle [m]\times [n]} that contains all subsets S such that, if ( i 1 , j 1 ) {\displaystyle (i_{1},j_{1})} and ( i 2 , j 2 ) {\displaystyle (i_{2},j_{2})} are two distinct elements of S, then both i 1 ≠ i 2 {\displaystyle i_{1}\neq i_{2}} and j 1 ≠ j 2 {\displaystyle j_{1}\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 Dm be a set of m discrete points. Then the chessboard complex is the n-fold 2-wise deleted join of Dm, denoted by ( D m ) Δ ( 2 ) ∗ n {\displaystyle (D_{m})_{\Delta (2)}^{*n}} .3: 176 

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

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:5

  • 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 Δ m , n {\displaystyle \Delta _{m,n}} contains min ( m , n ) {\displaystyle \min(m,n)} elements. Therefore, the dimension of Δ m , n {\displaystyle \Delta _{m,n}} is min ( m , n ) − 1 {\displaystyle \min(m,n)-1} .

The homotopical connectivity of the chessboard complex is at least min ( m , n , m + n + 1 3 ) − 2 {\displaystyle \min \left(m,n,{\frac {m+n+1}{3}}\right)-2} (so η ≥ min ( m , n , m + n + 1 3 ) {\displaystyle \eta \geq \min \left(m,n,{\frac {m+n+1}{3}}\right)} ).6: Sec.1 

The Betti numbers b r − 1 {\displaystyle b_{r-1}} of chessboard complexes are zero if and only if ( m − r ) ( n − r ) > r {\displaystyle (m-r)(n-r)>r} .7: 200  The eigenvalues of the combinatorial Laplacians of the chessboard complex are integers.8: 193 

The chessboard complex is ( ν m , n − 1 ) {\displaystyle (\nu _{m,n}-1)} -connected, where ν m , n := min { m , n , ⌊ m + n + 1 3 ⌋ } {\displaystyle \nu _{m,n}:=\min\{m,n,\lfloor {\frac {m+n+1}{3}}\rfloor \}} .9: 527  The homology group H ν m , n ( M m , n ) {\displaystyle H_{\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 ≡ 1 ( mod 3 ) {\displaystyle m+n\equiv 1{\pmod {3}}} .10: 543–555 

The ( ⌊ n + m + 1 3 ⌋ − 1 ) {\displaystyle (\lfloor {\frac {n+m+1}{3}}\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 ≥ 2 m − 1 {\displaystyle n\geq 2m-1} .11: 3  As a corollary, any position of k rooks on a m-by-n chessboard, where k ≤ ⌊ m + n + 1 3 ⌋ {\displaystyle k\leq \lfloor {\frac {m+n+1}{3}}\rfloor } , can be transformed into any other position using at most m n − k {\displaystyle mn-k} single-rook moves (where each intermediate position is also not rook-taking).12: 3 

Generalizations

The complex Δ n 1 , … , n k {\displaystyle \Delta _{n_{1},\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 ( ν − 2 ) {\displaystyle (\nu -2)} -connected, for ν := min { n 1 , ⌊ n 1 + n 2 + 1 3 ⌋ , … , ⌊ n 1 + n 2 + ⋯ + n k + 1 2 k + 1 ⌋ } {\displaystyle \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 \}} 13: 33 

References

  1. Björner, A.; Lovász, L.; Vrećica, S. T.; Živaljević, R. T. (1994-02-01). "Chessboard Complexes and Matching Complexes". Journal of the London Mathematical Society. 49 (1): 25–39. doi:10.1112/jlms/49.1.25. http://doi.wiley.com/10.1112/jlms/49.1.25 ↩

  2. Vrećica, Siniša T.; Živaljević, Rade T. (2011-10-01). "Chessboard complexes indomitable". Journal of Combinatorial Theory. Series A. 118 (7): 2157–2166. arXiv:0911.3512. doi:10.1016/j.jcta.2011.04.007. ISSN 0097-3165. https://www.sciencedirect.com/science/article/pii/S0097316511000756 ↩

  3. Matoušek, Jiří (2007). Using the Borsuk-Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry (2nd ed.). Berlin-Heidelberg: Springer-Verlag. ISBN 978-3-540-00362-5. Written in cooperation with Anders Björner and Günter M. Ziegler 978-3-540-00362-5 ↩

  4. Björner, A.; Lovász, L.; Vrećica, S. T.; Živaljević, R. T. (1994-02-01). "Chessboard Complexes and Matching Complexes". Journal of the London Mathematical Society. 49 (1): 25–39. doi:10.1112/jlms/49.1.25. http://doi.wiley.com/10.1112/jlms/49.1.25 ↩

  5. Goerner, Matthias Rolf Dietrich (2011). "1.2.2 Relationship to the 4 × 5 Chessboard Complex". Visualizing Regular Tessellations: Principal Congruence Links and Equivariant Morphisms from Surfaces to 3-Manifolds (PDF) (Doctoral dissertation). University of California, Berkeley. https://www.unhyperbolic.org/research/matthias_goerner_thesis_print.pdf ↩

  6. Björner, A.; Lovász, L.; Vrećica, S. T.; Živaljević, R. T. (1994-02-01). "Chessboard Complexes and Matching Complexes". Journal of the London Mathematical Society. 49 (1): 25–39. doi:10.1112/jlms/49.1.25. http://doi.wiley.com/10.1112/jlms/49.1.25 ↩

  7. Friedman, Joel; Hanlon, Phil (1998-09-01). "On the Betti Numbers of Chessboard Complexes". Journal of Algebraic Combinatorics. 8 (2): 193–203. doi:10.1023/A:1008693929682. hdl:2027.42/46302. ISSN 1572-9192. https://doi.org/10.1023/A:1008693929682 ↩

  8. Friedman, Joel; Hanlon, Phil (1998-09-01). "On the Betti Numbers of Chessboard Complexes". Journal of Algebraic Combinatorics. 8 (2): 193–203. doi:10.1023/A:1008693929682. hdl:2027.42/46302. ISSN 1572-9192. https://doi.org/10.1023/A:1008693929682 ↩

  9. Shareshian, John; Wachs, Michelle L. (2007-07-10). "Torsion in the matching complex and chessboard complex". Advances in Mathematics. 212 (2): 525–570. arXiv:math/0409054. doi:10.1016/j.aim.2006.10.014. ISSN 0001-8708. https://doi.org/10.1016%2Fj.aim.2006.10.014 ↩

  10. Shareshian, John; Wachs, Michelle L. (2007-07-10). "Torsion in the matching complex and chessboard complex". Advances in Mathematics. 212 (2): 525–570. arXiv:math/0409054. doi:10.1016/j.aim.2006.10.014. ISSN 0001-8708. https://doi.org/10.1016%2Fj.aim.2006.10.014 ↩

  11. Ziegler, Günter M. (1992-09-23). "Shellability of Chessboard Complexes". https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/89 ↩

  12. Ziegler, Günter M. (1992-09-23). "Shellability of Chessboard Complexes". https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/89 ↩

  13. Björner, A.; Lovász, L.; Vrećica, S. T.; Živaljević, R. T. (1994-02-01). "Chessboard Complexes and Matching Complexes". Journal of the London Mathematical Society. 49 (1): 25–39. doi:10.1112/jlms/49.1.25. http://doi.wiley.com/10.1112/jlms/49.1.25 ↩