Nonintersecting Unit Diagonals in Odd Square Arrays

Abstract

Let D(n) be the maximum number of unit-square diagonals in an n× 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)×(2k−1) square array into an isometric path cover of the k× k vertex grid with at most 2k²−|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.

The relative isoperimetric profile of a unit square with a central square removed
Kyle Byassee, Hunter Johnson, Brandon Jones +1
arXiv26 Sep 2026PreprintCC BY 4.0Full textGeometry & topologyarXiv
On the covering of n + ε square with n² + 1 unit squares for n ≥ 4
Sira Sriswasdi
arXiv14 Sep 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematics Geometry & topologyarXiv
Rational Area Profiles of Regular Polygons Cut by Two Congruent Diagonals
Shoichi Inoue, Keiichi Watanabe
arXiv16 Oct 2026PreprintarXiv licenceFull textAlgebra & number theory Geometry & topologyarXiv
Linear-exponent bounds for the automatic complexity of rational diagonals modulo prime powers
Alex Shvets
arXiv1 Nov 2026PreprintCC BY 4.0Full textGeneral mathematicsarXiv
A weak invariance principle for triangular arrays of independent random variables in some Besov spaces
Davide Giraudo, Sadillo Sharipov
HAL22 Sep 2026PreprintPublisher termsFull textProbability StatisticsHALarXiv

Cite

BibTeX RIS

BibTeX

@misc{song2026nonintersecting,
  title = {{Nonintersecting Unit Diagonals in Odd Square Arrays}},
  author = {Luyu Song},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.33042},
  eprint = {2610.33042},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.33042},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Nonintersecting Unit Diagonals in Odd Square Arrays
AU  - Luyu Song
PY  - 2026
DA  - 2026/10/16
PB  - arXiv
DO  - 10.48550/arxiv.2610.33042
UR  - https://arxiv.org/abs/2610.33042
AB  - Let D(n) be the maximum number of unit-square diagonals in an n× 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)×(2k−1) square array into an isometric path cover of the k× 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.
ER  -

Abstract

Related

Cite