Talk information

Date: Sunday, April 24, 2023
Time: 10:10–11:00
Place: Schreiber 309
Speaker: Michael Simkin (Harvard University)
Title: The Number of $n$-queens configurations

Abstract:

The chief innovation is the introduction of limit objects for $n$-queens configurations, which we call “queenons”. These are a convex set in $P([-1/2,1/2]^2)$. We define an entropy function that counts the number of $n$-queens configurations approximating a given queenon. The upper bound uses the entropy method of Radhakrishnan and Linial–Luria. For the lower bound we describe a randomized algorithm that constructs a configuration near a prespecified queenon and whose entropy matches that found in the upper bound. The enumeration of $n$-queens configurations is then obtained by maximizing the (concave) entropy function over the space of queenons.

Based on arXiv:2107.13460