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)表示该工作在公开前已完成整理和内部审核,并以工作论文形式发布。请将它作为普通学术预印本来阅读和讨论;后续检查或讨论仍可能带来更正。它不表示已经完成完整形式化或经过外部同行评审。

审核标准
返回结果列表
返回 数学