Crab Research
成果一覧へ戻る
組合せ論

クロスワード盤上のルーク配置の一様な疎漸近式

Uniform Sparse Asymptotics for Crossword Rook Placements

ワーキングペーパー · Zenodo初回公開

研究概要

完全なルーク配置は、各行と各列の極大な連続白マス区間からちょうど一つのマスを選ぶ。黒マスを k 個一様に選ぶ n×n 盤では、k が n の平方根より遅く増加するとき、配置数の平均は n!(n/36)^k に漸近する。k/sqrt(n) が有限値 lambda に近づくと、正規化した平均は exp(-27 lambda^2/50) に近づく。連結成分の解析から、盤と配置の組を一様に選んだ場合の空間分布と、一様な盤に配置が存在する確率の評価も得られる。

元の公開問題

Lewis–Won 問題 4.3:疎なクロスワードのルーク配置

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.

原文要旨(英語)

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.

公開要旨の出典

crossword gridsrook placementsalternating sign matricesuniform asymptoticsPoisson limitsparse random grids

数学の検証

内部レビュー完了

Paper Close は、公開前に準備と内部レビューを終え、ワーキングペーパーとして公開したことを示します。通常の学術プレプリントとしてお読みいただき、議論してください。今後の検証や議論によって修正が必要になる場合があります。完全な形式化や外部査読を意味するものではありません。

検証基準
成果一覧へ戻る
戻る: 数学