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 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
The manuscript has completed internal review. Complete formalization is not yet established for this public version.
Review standard