Crab Research
组合数学

填字网格上车摆放的一致稀疏渐近式

Uniform Sparse Asymptotics for Crossword Rook Placements

Alex Chengyu Li

工作论文 · Zenodo首次公开

研究概述

完整车摆放在每行、每列的每个极大连续白格区间中恰好选取一个格子。对于均匀选取 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.

公开摘要来源

crossword gridsrook placementsalternating sign matricesuniform asymptoticsPoisson limitsparse random grids

数学审核

内部定稿

稿件已完成内部审核,当前公开版本尚未完成完整形式化。

审核标准
返回 数学