クロスワード盤上のルーク配置の一様な疎漸近式
Uniform Sparse Asymptotics for Crossword Rook Placements
研究概要
完全なルーク配置は、各行と各列の極大な連続白マス区間からちょうど一つのマスを選ぶ。黒マスを k 個一様に選ぶ n×n 盤では、k が n の平方根より遅く増加するとき、配置数の平均は n!(n/36)^k に漸近する。k/sqrt(n) が有限値 lambda に近づくと、正規化した平均は exp(-27 lambda^2/50) に近づく。連結成分の解析から、盤と配置の組を一様に選んだ場合の空間分布と、一様な盤に配置が存在する確率の評価も得られる。
原文要旨（英語）
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.
数学の検証
原稿は内部レビューを完了しています。この公開版の完全な形式化は、まだ確立されていません。
検証基準