University of Birmingham > Talks@bham > Combinatorics and Probability Seminar > The n-queens problem

The n-queens problem

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Johannes Carmesin.

How many ways are there to place n queens on an n by n chessboard so that no two can attack one another? What if the chessboard is embedded on the torus? Let Q(n) be the number of ways on the standard chessboard and T(n) the number on the toroidal board. The toroidal problem was first studied in 1918 by PĆ³lya who showed that T(n)>0 if and only if n is not divisible by 2 or 3. Much more recently Luria showed that T(n) is at most ((1+o(1))ne)n and conjectured equality when n is not divisible by 2 or 3. We prove this conjecture, prior to which no non-trivial lower bounds were known to hold for all (sufficiently large) n not divisible by 2 or 3. We also show that Q(n) is at least ((1+o(1))ne)n for all natural numbers n which was independently proved by Luria and Simkin and, combined with our toroidal result, completely settles a conjecture of Rivin, Vardi and Zimmerman regarding both Q(n) and T(n).

In this talk we’ll discuss our methods used to prove these results. A crucial element of this is translating the problem to one of counting matchings in a 4-partite 4-uniform hypergraph. Our strategy combines a random greedy algorithm to count `almost’ configurations with a complex absorbing strategy that uses ideas from the methods of randomised algebraic construction and iterative absorption.

This is joint work with Peter Keevash.

This talk is part of the Combinatorics and Probability Seminar series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

Talks@bham, University of Birmingham. Contact Us | Help and Documentation | Privacy and Publicity.
talks@bham is based on talks.cam from the University of Cambridge.