Chessboard complex explained

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

\Delta_m,n

is the abstract simplicial complex with vertex set

[m] x [n]

that contains all subsets S such that, if

(i_1,j₁₎

and

(i_2,j₂₎

are two distinct elements of S, then both

i_{1 ≠}i₂

and

j_{1 ≠}j₂

. 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

	*n
(D
	\Delta(2)

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:^[3]

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

\Delta_m,n

contains

min(m,n)

elements. Therefore, the dimension of

\Delta_m,n

min(m,n)-1

The homotopical connectivity of the chessboard complex is at least

min\left(m,n,

	m+n+1
	3

\right)-2

(so

η\geqmin\left(m,n,

	m+n+1
	3

\right)

b_r

of chessboard complexes are zero if and only if

(m-r)(n-r)>r

.^[4] The eigenvalues of the combinatorial Laplacians of the chessboard complex are integers.

The chessboard complex is

(\nu_m,-1)

-connected, where

\nu_m,:=min\{m,n,\lfloor

	m+n+1
	3

\rfloor\}

.^[5] The homology group

H
	\nu_m,

(M_m,)

is a 3-group of exponent at most 9, and is known to be exactly the cyclic group on 3 elements when

m+n\equiv1\pmod{3}

The

(\lfloor	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\geq2m-1

.^[6] As a corollary, any position of k rooks on a m-by-n chessboard, where

k\leq\lfloor	m+n+1
	3

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

Generalizations

The complex

\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

(\nu-2)

-connected, for

\nu:=min\{n_1,\lfloor

	n₁+n₂+1
	3

\rfloor,...,\lfloor

	n₁+n₂+...+n_k+1
	2k+1

\rfloor\}

Notes and References

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 . en . 49 . 1 . 25–39 . 10.1112/jlms/49.1.25.
Vrećica . Siniša T. . Živaljević . Rade T. . 2011-10-01 . Chessboard complexes indomitable . . Series A . en . 118 . 7 . 2157–2166 . 10.1016/j.jcta.2011.04.007 . free . 0097-3165. 0911.3512 .
Visualizing Regular Tessellations: Principal Congruence Links and Equivariant Morphisms from Surfaces to 3-Manifolds. 1.2.2 Relationship to the 4 × 5 Chessboard Complex. Matthias Rolf Dietrich. Goerner. University of California, Berkeley. 2011. Doctoral dissertation.
Friedman . Joel . Hanlon . Phil . 1998-09-01 . On the Betti Numbers of Chessboard Complexes . Journal of Algebraic Combinatorics . en . 8 . 2 . 193–203 . 10.1023/A:1008693929682 . 1572-9192. 2027.42/46302 . free .
Shareshian . John . Wachs . Michelle L. . 2007-07-10 . Torsion in the matching complex and chessboard complex . . en . 212 . 2 . 525–570 . 10.1016/j.aim.2006.10.014 . free . 0001-8708. math/0409054 .
Web site: Ziegler . Günter M. . 1992-09-23 . Shellability of Chessboard Complexes. .