Nonintersecting Unit Diagonals in Odd Square Arrays
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
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality