Problem of the Week
Hilton Memorial Lecture
Recreational chess fans have asked questions like: What is the largest number of identical pieces (queens, or bishops, or …) that can be placed on a chessboard so none attacks any other? Some have tried to solve a harder question: Given q identical pieces, how many ways can they be placed on an n × n chessboard? Here q is fixed, n is variable.
For some chess pieces the answer, surprisingly, is given by a cyclically repeating sequence of polynomials in n. This can be proved by geometry. To find the polynomials one must know how long the sequence is (the 'period'). That can be partly solved by geometry, but it is hard.
The bishop moves and attacks diagonally any distance. Seth Chaiken, Chris Hanusa, and I have found that the bishop requires only 2 polynomials, no matter how many bishops one has. The proof uses the geometric theory of signed graphs.
I will explain the geometry and graph theory that lies behind all the foregoing assertions.
You can view the slides from the talk here: Bishop Slides.