OpenAlex ·
Non-attacking rook placements on crossword grids
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2609.03081
- Original
- Read it at the publisher
- Topics
Abstract
We introduce the notion of a non-attacking rook placement on a crossword grid. A crossword grid is a collection of white squares (which comprise across and down words) and black squares (which separate the words), and a complete non-attacking rook placement on such a grid is a subset of white squares which intersects every across and every down word exactly once. We prove an upper bound on the number of rook placements that a general grid can admit. We then study sparse grids in which no two black squares share an edge and show that rook placements on certain sparse grids correspond bijectively to alternating sign matrices with prescribed $-1$ entries. Specializing further to permutation grids, we prove that every permutation grid admits at least one rook placement, and characterize the permutations whose grids admit exactly one placement in terms of the Robinson--Schensted correspondence. Throughout, we pose a variety of conjectures and open questions.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computational Complexity
A new proof that more than $2/3$ of the zeros of the Riemann zeta function are simple and on the critical line
Odd denominators in the Lonely Runner spectrum for six speeds
Algebraic Geometry Codes Approach the Half-Singleton Bound with Constant Field Size
The Truncated Octahedral Conjecture
Integrality Gap Bounds for the Goemans-Linial SDP on Finite Abelian Cayley Graphs
Get the few papers worth your time in Computational Complexity every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.