Nonintersecting Unit Diagonals in Odd Square Arrays

arXiv:2610.33042 · math.CO · Submitted 2026-10-16 · Read on arXiv

math.CO

Submitted: 2026-10-16

Updated: 2026-10-16

Comments: Lean source code included as ancillary files

License: http://creativecommons.org/licenses/by/4.0/

The gist: Let D(n) be the maximum number of unit-square diagonals in an n times n square array such that no two selected diagonals share an endpoint and no unit square contains both diagonals.

Abstract

Let D(n) be the maximum number of unit-square diagonals in an n times n square array such that no two selected diagonals share an endpoint and no unit square contains both diagonals. We prove that, for every odd positive integer n, D(n)=n(n+1)/2+ (n+1)/6. The matching lower bound was established by Boyland, Roth, Pintér, Laukó, Schoenfield, and Wasielewski. We obtain the upper bound by transforming any admissible selection M in a (2k-1) times(2k-1) square array into an isometric path cover of the k times k vertex grid with at most 2k 2-M paths. An auxiliary matching decomposes the original vertices into alternating paths. On each such path, all segments between blocks are either of type da or of type bc. Projecting these paths to the block grid gives coordinate-monotone sequences, which become geodesics when diagonal steps are expanded. The Fisher--Fitzpatrick theorem then yields the sharp upper bound. We also describe a Lean verification of the upper-bound reduction, with the grid-cover theorem supplied as an explicit hypothesis.

Related papers