Speaker: Zur Luria, ETH

Title: New bounds for the n-queen's problem

Abstract:

The famous n-queens problem asks: In how many ways can n nonattacking queens be placed on an n by n chessboard? This question also makes sense on the toroidal chessboard, in which opposite sides of the board are identified. In this setting, the n-queens problem counts the number of perfect matchings in a certain regular hypergraph. We give an extremely general bound for such counting problems, which include Sudoku squares and designs.

Our lower bound, which confirms a conjecture of Vardi and Rivin, is based on an algebraic construction which is similar to the algebraic absorbers used by Peter Keevash in his construction of designs.

Title: New bounds for the n-queen's problem

Abstract:

The famous n-queens problem asks: In how many ways can n nonattacking queens be placed on an n by n chessboard? This question also makes sense on the toroidal chessboard, in which opposite sides of the board are identified. In this setting, the n-queens problem counts the number of perfect matchings in a certain regular hypergraph. We give an extremely general bound for such counting problems, which include Sudoku squares and designs.

Our lower bound, which confirms a conjecture of Vardi and Rivin, is based on an algebraic construction which is similar to the algebraic absorbers used by Peter Keevash in his construction of designs.

## Date:

Mon, 07/05/2018 - 11:00 to 12:30

## Location:

IIAS, Eilat hall, Feldman bldg, Givat Ram