155 通りのルーク配置を持つ順列格子
A Permutation Grid with 155 Rook Placements
研究概要
完全なルーク配置がちょうど 155 通りとなる順列格子を構成して Lewis–Won 予想 3.10 を否定し、8 以上のすべての次数に反例を与える。
原文要旨(英語)
A permutation determines a crossword grid by placing one black square in each row and column. A complete rook placement chooses white squares so that every maximal horizontal or vertical white interval contains exactly one rook. Lewis and Won conjectured that the positive integers which occur as complete placement counts are precisely those other than 4, 12, and the integers congruent to 3 modulo 4. We disprove the proposed congruence restriction: the permutation 27481635 has exactly 155 complete rook placements. The count is obtained directly from the grid. Five rooks are forced; a further reversible reduction leaves a weighted bipartite graph with eight vertices in each part. Its matching count is a squarefree coefficient, which we evaluate as 116+39. We also give a bijection showing that prepending an initial fixed point preserves the number of complete placements. Repeatedly applying this operation produces counterexamples in every order at least eight. The argument uses only explicit word intervals, matching reductions, and a finite polynomial calculation.
数学の検証
Kernel-Only
主要結論には公開されたカーネル検証済みの証明があり、論文との対応も確認されています。これは外部査読とは別の検証です。
検証基準