11
$\begingroup$

For the purpose of this question, a chess piece is the King, Queen, Rook, Bishop or Knight of the game of chess. To a chess piece is attached a graph which represents the legal moves it can make on an empty chess board. Except for the bishop, the graph attached to a chess piece has 64 vertices, while the bishop's graph has 32 vertices.

These graphs satisfy a number of interesting mathematical properties from the point of view of graph theory.

  • Only the rook's graph is regular, and the rook's graph is even strongly regular (a fact well-known to chess player with no knowledge of mathematics).
  • The knight's graph is bipartite.
  • The king's, rook's, queen's and bishop's graph are hamiltonian (and after Euler, it is very well-known though to me non-obvious a priori that the knight's graphs is hamiltonian).

Less obvious properties have of course been devised by graph theorists.

Recently, I asked myself (with no other purpose than leisure) if these graphs were known to satisfy interesting algebraic properties.

A quick computation based on its strong regularity or on the observation that it is the cartesian product of two copies of the complete graph $K_8$ show that spectrum of the rook's graph is $\{14^{(1)},6^{(14)},-2^{(49)}\}$ (in particular, it is an integral graph).

Are there any other remarkable algebraic properties of the graphs of chess pieces, either of their spectra or of their group of automorphisms?

Improve this question
$\endgroup$
2
  • 5
    $\begingroup$ My guess is that you will get nicer properties for a toroidal chessboard. $\endgroup$
    – Igor Rivin
    Dec 18, 2019 at 0:38
  • 2
    $\begingroup$ Or a Klein bottle! At the risk of getting slightly off-topic, I can't resist mentioning some chess puzzles on a Klein bottle that I once composed. $\endgroup$
    – Timothy Chow
    Dec 18, 2019 at 16:43

2 Answers 2

Reset to default
12
$\begingroup$

The clique complex of the complement of the rook's graph is sometimes called a chessboard complex. It has some remarkable algebraic properties. For example, its Laplacian eigenvalues are all nonnegative integers. This is a rare property, shared by matroid complexes but very few other "naturally occurring" simplicial complexes. See for example Michelle Wachs's paper Topology of matching, chessboard, and general bounded degree graph complexes for more information.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Great answer! The OP is encouraged to see in particular the Friedman-Hanlon Theorem [Thm 3.2 in Wachs's survey]. It relates the reduced cohomology of $m \times n$ chessboard complexes to irreducible representations of products of symmetric groups $S_m \times S_n$. $\endgroup$
    – Vidit Nanda
    Dec 17, 2019 at 23:59
2
$\begingroup$

Wikipedia says the chromatic polynomial is "studied in algebraic graph theory". So here's an answer involving the chromatic polynomial of the rook's graph.

The rook's graph is $K_8 \Box K_8$, i.e., the Cartesian product of $K_8$ and $K_8$.

The chromatic polynomial $P(K_8 \Box K_8;n)$ of the rook's graph is the number of $8 \times 8$ generalized Latin squares, where we can use $n$ symbols (without repeated symbols in any row or column). In particular, evaluating it at its chromatic number...

$$P(K_8 \Box K_8;8) = \text{number of Latin squares of order $8$}.$$

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.