Misplaced Pages

Chessboard complex

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
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.

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 \times } 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}} .

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

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:

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

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} . The eigenvalues of the combinatorial Laplacians of the chessboard complex are integers.

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 \}} . 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}}} .

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} . 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).

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 \}}

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.
  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.
  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
  4. 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.
  5. ^ 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.
  6. ^ 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.
  7. ^ Ziegler, Günter M. (1992-09-23). "Shellability of Chessboard Complexes".
Category: