The n-queens problem

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

• Candida Bowtell, Birmingham
• Thursday 09 December 2021, 15:30-16:30
• LTA, additional zoom link: https://bham-ac-uk.zoom.us/j/87124623071 (NOTE: UNUSUAL TIME).

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.

This talk is included in these lists:

• Combinatorics and Probability seminar
• LTA, additional zoom link: https://bham-ac-uk.zoom.us/j/87124623071 (NOTE: UNUSUAL TIME)
• School of Mathematics events

Note that ex-directory lists are not shown.