Uniform Sparse Asymptotics for Crossword Rook Placements
Overview
A complete rook placement chooses one cell in every maximal uninterrupted white segment of each row and column. For an n-by-n grid with k uniformly chosen black cells, the mean number of placements is asymptotic to n!(n/36)^k when k grows more slowly than the square root of n. When k/sqrt(n) tends to a finite value lambda, the normalized mean tends to exp(-27 lambda^2/50). The component analysis also gives spatial laws for uniformly chosen grid-placement pairs and existence bounds for uniform grids.
Original public questions
Lewis–Won Question 4.3: the sparse crossword rook regime
Joel Brewster Lewis and Robert Won: Non-attacking rook placements on crossword grids — arXiv 2609.03081v1: Question 4.3 and its following discussion. The proposed sparse mean is established uniformly for k=o(sqrt(n)); this is not a solution of every density regime in that question.
Original abstract (English)
A complete rook placement on a crossword grid meets every maximal horizontal and vertical white word exactly once. For a uniformly chosen n-by-n grid with k black cells, we prove the proposed mean n!(n/36)^k uniformly when k=o(sqrt(n)), with relative error O(k^2/n). The same estimate extends the classical fixed-defect asymptotic for alternating sign matrices to a growing number of negative entries. When k/sqrt(n) tends to a finite nonnegative value lambda, both normalized counts converge to exp(-27 lambda^2/50). The proof uses uniform connected-component bounds for a marked row-column graph and controls the contribution of boundary and adjacent black cells. At this critical scale, the number of connected size-five components with two negative entries has a Poisson limit of mean 99 lambda^2/25. In the smaller sparse regime, almost all uniformly chosen grid-placement pairs consist of disjoint elementary crosses and a permutation remainder; their black coordinates have an explicit median law with independent beta(2,2) limits for fixed k. Uniform sparse grids admit a complete placement with high probability, while at fixed positive black and white densities the existence probability decays exponentially in the area.
Mathematical review
Paper Close marks a working paper prepared and internally reviewed before release. Please treat it as an ordinary scholarly preprint: further checking or discussion may lead to corrections. It does not indicate complete formal verification or external peer review.
Review standard