HUJI Combinatorics Seminar 


When: Monday June 14th, 2021, at 5PM. **Note special time**


Zoom link: https://huji.zoom.us/j/82914357402?pwd=Vnk3VkJKK3Yrak5HU0tCT3FIbUZxUT09



Speaker:  Michael Simkin (Harvard)
Title: The number of $n$-queens configurations
Abstract: 
The $n$-queens problem is to determine $Q(n)$, the number of ways to place $n$ mutually non-threatening chess queens on an $n \times n$ board. This falls under the umbrella of combinatorial design theory. This field has seen several breakthroughs in recent years: random greedy algorithms and the absorber method for constructing designs, and the entropy method for bounding their number. In their most general form these methods are used to study perfect matchings in regular hypergraphs. However, since the lengths of diagonals in a square vary widely, the $n$-queens problem does not exhibit the regularity necessary for direct applications of these methods. To overcome this challenge we introduce an analytic limit object for $n$-queens configurations. This allows us to refine the existing methods to construct and enumerate $n$-queens configurations. Specifically, we show that $Q(n) \approx (ne^\alpha)^n$, where $\alpha \approx -1.944$ is characterized as the solution to a convex optimization problem in the space of limit objects.

Based partly on joint work with Zur Luria.