betaFeedback

WorksMathematics

Nonintersecting Unit Diagonals in Odd Square Arrays

Abstract

Let D(n)D(n) be the maximum number of unit-square diagonals in an n×nn\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 nn, D(n)=n(n+1)/2+⌊(n+1)/6⌋D(n)=n(n+1)/2+\lfloor(n+1)/6\rfloor. 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 MM in a (2k−1)×(2k−1)(2k-1)\times(2k-1) square array into an isometric path cover of the k×kk\times k vertex grid with at most 2k2−∣M∣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 dada or of type bcbc. 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.

Introduction

Consider the lattice vertex set

Vn={0,1,…,n}2V_n = \{0,1,\ldots,n\}^2

and the n×nn \times n array of unit squares that it determines. A unit diagonal is a diagonal of one of these squares. A selection is admissible if its members have pairwise disjoint endpoints and no square contains both of its diagonals. These conditions are equivalent to the selected segments being pairwise disjoint. Indeed, the relative interiors of distinct unit squares are disjoint, and a diagonal meets the boundary of its own square only at its endpoints. Write D(n)D(n) for the maximum cardinality of an admissible selection.

Boyland, Roth, Pintér, Laukó, Schoenfield, and Wasielewski [1] proved

D(n)=n(n+1)2D(n) = \frac{n(n+1)}{2}

when nn is even.

For odd nn, Proposition 5 and the border extension following its proof give the lower bound

D(n)≥n(n+1)2+⌊n+16⌋(1)D(n) \ge\frac{n(n+1)}{2} + \left\lfloor\frac{n+1}{6}\right\rfloor \tag*{(1)}

They also gave an upper bound and discussed the conjectured optimality of their constructions. The odd-order formula is still labeled a conjecture in OEIS entry A264041 as accessed on October 15, 2026 [4]. Our contribution is a general upper bound matching (1).

Theorem 1.1. For every integer k≥1k \ge1,

D(2k−1)=2k2−⌈2k3⌉(2)D(2k-1) = 2k^2 - \left\lceil\frac{2k}{3}\right\rceil \tag*{(2)}

Equivalently, for every odd positive integer nn,

D(n)=n(n+1)2+⌊n+16⌋(3)D(n) = \frac{n(n+1)}{2} + \left\lfloor\frac{n+1}{6}\right\rfloor \tag*{(3)}

Date: October 15, 2026.

Key words and phrases. Nonintersecting diagonals, matchings, Cartesian grids, isometric path covers.

The upper bound applies to every admissible selection, without imposing a prescribed pattern. Its main ingredient is a transformation to an isometric path cover of a smaller grid. The number of paths in the cover is controlled exactly by the number of unmatched original vertices. § 3 proves this transformation, including the type invariant needed for geodesicity, and combines the resulting upper bound with the published lower bound to prove Theorem 1.1. Finally, § 4 states the scope of the accompanying Lean verification.

Grid paths and the Fisher–Fitzpatrick theorem

Coordinates are written as (r,c)(r,c), with the row coordinate increasing downward and the column coordinate increasing to the right. Thus a unit diagonal joins (r,c)(r,c) to (r+1,c+1)(r+1,c+1) or joins (r,c+1)(r,c+1) to (r+1,c)(r+1,c). An admissible selection is a matching in the graph of all unit diagonals, subject to the additional prohibition on the two diagonals of a single square.

Let

Γk=Pk□Pk\Gamma_k = P_k \mathbin{\square} P_k

be the Cartesian grid with vertex set {0,…,k−1}2\{0,\ldots,k-1\}^2 and edges joining vertices at Manhattan distance one. Here PkP_k has kk vertices. A path is isometric, or geodesic, if it is a shortest path between its endpoints. A path consisting of one vertex is permitted. An isometric path cover is a family of such paths whose vertex sets cover the graph; different paths may share vertices.

The distance between (i,j)(i,j) and (i′,j′)(i',j') in Γk\Gamma_k is ∣i−i′∣+∣j−j′∣|i-i'|+|j-j'|. In particular, an orthogonal grid path whose two coordinates are each monotone is isometric: its horizontal and vertical step counts are the absolute changes in the corresponding coordinates, so its length equals this distance.

Theorem 2.1 (Fisher–Fitzpatrick). The minimum number of paths in an isometric path cover of Γk\Gamma_k is ⌈2k/3⌉\lceil2k/3\rceil.

This is the square-grid specialization of the grid-cover results in [2 Section 4]; see also [3] for the distinction between covers and partitions. We use only the assertion that every isometric path cover contains at least ⌈2k/3⌉\lceil2k/3\rceil paths. The grid in this statement has k2k^2 vertices, rather than k2k^2 unit squares.

An upper bound by local routing

Fix k≥1k \ge1 and an arbitrary admissible selection MM on V2k−1V_{2k-1}. Put m=∣M∣m=|M|. Partition the 4k24k^2 original vertices into the disjoint four-vertex blocks

Bij={(2i+u,2j+v):u,v∈{0,1}},0≤i,j<k.(4)B_{ij}=\{(2i+u,2j+v):u,v\in\{0,1\}\},\qquad0\le i,j<k. \tag*{(4)}

Within a block, write

aij=(2i,2j),bij=(2i,2j+1),cij=(2i+1,2j),dij=(2i+1,2j+1).a_{ij}=(2i,2j),\qquad b_{ij}=(2i,2j+1),\qquad c_{ij}=(2i+1,2j),\qquad d_{ij}=(2i+1,2j+1).

We suppress the subscripts when discussing a single block and display its labels as abcd\begin{matrix}a&b\\c&d\end{matrix}. An edge of MM is internal if its endpoints belong to the same block, and external otherwise. The only possible internal edges are adad and bcbc. They cannot both be selected, since they are the two diagonals of one unit square.

Local routes and their ports

Define an auxiliary perfect matching NN within the blocks. In a block with no internal edge of MM, choose adad and bcbc as the two NN-edges. In a block containing either internal edge, choose abab and cdcd. In each case NN pairs all four vertices and has no edge in common with MM. Here NN is a matching in the graph-theoretic sense: its edges may cross in the drawing, and such crossings do not create graph vertices.

The graph consisting of the local NN-edges and the internal MM-edges is a union of paths. We call these paths local routes. Their endpoints are called ports. A route is of type A if its ports are a,da,d, oriented from aa to dd, and of type B if its ports are c,bc,b, oriented from cc to bb. All possibilities are listed in Table 1.

Internal edge of MMEdges of NNOriented local routesTypes
nonead,bcad, bca→d,c→ba \to d, c \to bA and B
adadab,cdab, cdc→d→a→bc \to d \to a \to bB
bcbcab,cdab, cda→b→c→da \to b \to c \to dA

Table 1. Local routes. In the last two rows the intermediate vertices are already matched by the internal edge of MM.

The routes partition the original vertices. At least one route occurs in every block. Furthermore, an external MM-edge can meet a local route only at a port: each intermediate vertex of a three-edge route is already incident with its internal MM-edge.

Local routes with no internal edge, internal edge $ad$, and internal edge $bc$

Figure 1. Solid edges belong to MM and dashed edges belong to NN. A crossing without a dot is not a graph vertex. The auxiliary matching is used only for routing.

It is essential to distinguish the type of a route from the labels of its intermediate vertices. For example, c−d−a−bc-d-a-b is a type B route even though it contains aa and dd. Those two vertices cannot carry external edges. Type preservation concerns the ports through which routes are connected.

Alternating paths in the original graph

Let

H=(V2k−1,M∪N).H=(V_{2k-1}, M \cup N).

Since NN is a perfect matching, MM is a matching, and the two matchings have no common edge, every vertex of HH has degree one or two. A degree-two vertex is incident with one edge of each matching. Each connected component is therefore an alternating path or an alternating cycle. In particular, HH has no isolated vertices. The local routes in Table 1 are the parts of these components inside individual blocks, before external MM-edges are included.

Lemma 3.1 (Uniform type and directed steps). Every external edge of MM joins the exit port of one local route to the entry port of another local route of the same type. Consequently, all local routes in a connected component of HH have a common type.

Orient the local routes as in Table 1, and orient each external edge from its exit port to its entry port. These orientations make every component of HH a directed path or a directed cycle. In a type A component, every external edge is directed from dijd_{ij} to ai′j′a_{i'j'}, with block increment

(i′−i,j′−j)∈{(1,0),(0,1),(1,1)}.(5)(i' - i,j' - j) \in\{(1,0),(0,1),(1,1)\}. \tag*{(5)}

In a type B component, every external edge is directed from bijb_{ij} to ci′j′c_{i'j'}, with block increment

(i′−i,j′−j)∈{(−1,0),(0,1),(−1,1)}.(6)(i' - i,j' - j) \in\{(-1,0),(0,1),(-1,1)\}. \tag*{(6)}

Thus all cross-block segments on a given component are of type dada, or all are of type bcbc.

Proof. A unit diagonal changes both coordinate parities. Thus it pairs an aa-vertex with a dd-vertex, or a bb-vertex with a cc-vertex. External edges meet local routes only at ports. An external adad edge therefore joins two type A routes, and an external bcbc edge joins two type B routes. In either case, one is an exit to an entry. Every component of HH consists of local routes joined by external edges, so its local routes all have the same type.

At the entry port of a local route, its first edge points out of that port, and an external edge, if present, points into it. At the exit port the directions are reversed. The matching property allows at most one external edge at each port. At an intermediate vertex of a local route there is already one incoming and one outgoing edge, and no external edge can occur there. The orientations therefore fit together to give directed paths and directed cycles.

The four unit-diagonal neighbors of dij=(2i+1,2j+1)d_{ij}=(2i+1,2j+1) are

aij,ai+1,j,ai,j+1,ai+1,j+1,a_{ij},\quad a_{i+1,j},\quad a_{i,j+1},\quad a_{i+1,j+1},

whenever the corresponding indices are in range. The first neighbor is internal; the other three give (5) in the orientation d→ad\to a. Similarly, the four possible neighbors of bij=(2i,2j+1)b_{ij}=(2i,2j+1) are

cij,ci−1,j,ci,j+1,ci−1,j+1.c_{ij},\quad c_{i-1,j},\quad c_{i,j+1},\quad c_{i-1,j+1}.

Removing the internal neighbor gives (6) in the orientation b→cb\to c.

Lemma 3.2 (Path decomposition and count). Every connected component of HH is an alternating path with at least one edge. The number of these paths is

p=2k2−m.(7)p=2k^2-m. \tag*{(7)}

Proof. By Lemma 3.1, a component has a common type. Assign the integer i+ji+j to each vertex in a type A local route in block BijB_{ij}, and assign j−ij-i to each vertex in a type B local route in that block. Along an oriented local route this value is constant. Along an external edge it increases strictly, by (5) and (6).

Any cycle in HH would be directed by Lemma 3.1 and would contain an external edge: inside any single block, the local routes are disjoint paths. The assigned integer would then be nondecreasing around the cycle and would increase strictly at least once, which is impossible. Hence every component is a path. It has at least one edge because NN meets every original vertex.

A vertex of HH has degree one exactly when it is not matched by MM. There are 4k2−2m4k^2-2m such vertices. Each path component has exactly two degree-one vertices, so

p=4k2−2m2=2k2−m.p=\frac{4k^2-2m}{2}=2k^2-m.

:::

Projected paths in the block grid

Let Q=ΓkQ=\Gamma_k be the ordinary k×kk\times k vertex grid: its vertices are the block indices (i,j)(i,j), and two vertices are adjacent exactly when their Manhattan distance is one. Define the block projection

π:V2k−1⟶V(Q),π(r,c)=(⌊r2⌋,⌊c2⌋).\pi:V_{2k-1}\longrightarrow V(Q),\qquad\pi(r,c)=\left(\left\lfloor\frac{r}{2}\right\rfloor,\left\lfloor\frac{c}{2}\right\rfloor\right).

For a directed path PP of HH, project its vertex sequence by π\pi and delete consecutive repetitions. Each remaining step corresponds to an external edge of MM. A step may be diagonal in the block coordinates; expand it into an east step followed by its vertical step, as specified below. We call the resulting walk the projected walk of PP in QQ. The next lemma shows that it is a geodesic path.

The paths used to cover QQ are these projections of the paths of HH. Different projected paths may meet at a grid vertex; the prescribed continuation of each is inherited from its path in HH. Their number is counted in HH, not by the connected components of their union in QQ.

Lemma 3.3 (Geodesic cover transformation). An admissible selection MM on V2k−1V_{2k-1} determines an isometric path cover of Q=ΓkQ=\Gamma_k with at most 2k2−∣M∣2k^2-|M| paths.

Proof. Let PP be a directed path component of HH, and project it as described above. Lemma 3.1 applies to the entire path: all its cross-block segments are of type dada, or all are of type bcbc. In the first case, both block coordinates are nondecreasing; in the second, the row coordinate is nonincreasing and the column coordinate is nondecreasing. After consecutive

repetitions have been deleted, every step changes at least one coordinate strictly. Thus a block index cannot recur in the resulting sequence.

Expand its diagonal steps using

(i,j)→(i+1,j+1)⇝(i,j)→(i,j+1)→(i+1,j+1),(i,j) \to(i+1,j+1) \leadsto(i,j) \to(i,j+1) \to(i+1,j+1),
(i,j)→(i−1,j+1)⇝(i,j)→(i,j+1)→(i−1,j+1).(i,j) \to(i-1,j+1) \leadsto(i,j) \to(i,j+1) \to(i-1,j+1).

Each inserted vertex lies in QQ, because its coordinates are coordinates of the two original endpoints. The expanded walk uses only edges of QQ and preserves both coordinate directions.

This monotonicity proves simplicity and short­estness. If a vertex occurred twice, both coordinates would have the same value at those occurrences. Monotonicity would force them to remain constant between those occurrences, contradicting the unit steps. The horizontal step count equals the total increase of the column coordinate, and the vertical step count equals the absolute change of the row coordinate. Hence the length equals the Manhattan distance between the endpoints, so the projected walk is a geodesic path. If PP lies in a single block, its projection is the single-vertex path at that block index.

Every original vertex belongs to a path component of HH. Thus each block is visited by at least one of these paths. Projection retains its block index, and expansion only adds vertices. Consequently, the projected paths cover all k2k^2 vertices of QQ. They form an indexed family with one member for each of the p=2k2−mp = 2k^2 - m paths of HH, by Lemma 3.2. Intersections between members are allowed. If coincident members are discarded, the number of paths can only decrease.

Proposition 3.4. For every k≥1k \ge1,

D(2k−1)≤2k2−⌈2k3⌉.D(2k-1) \le2k^2 - \left\lceil\frac{2k}{3} \right\rceil.

Proof. For any admissible MM, Lemma 3.3 and Theorem 2.1 imply

⌈2k3⌉≤2k2−∣M∣.\left\lceil\frac{2k}{3} \right\rceil\le2k^2 - |M|.

Rearranging and maximizing over MM proves the assertion.

Proof of Theorem 1.1. For k≥1k \ge1, the lower bound of Boyland et al. recorded in (1), with n=2k−1n = 2k-1, gives

D(2k−1)≥2k2−k+⌈k3⌉=2k2−⌊2k3⌋,D(2k-1) \ge2k^2-k+\left\lceil\frac{k}{3} \right\rceil= 2k^2-\left\lfloor\frac{2k}{3} \right\rfloor,

where the equality follows from ⌈2k/3⌉=k−⌊k/3⌋\lceil2k/3\rceil= k-\lfloor k/3\rfloor. Together with Proposition 3.4, this proves (2). Substituting n=2k−1n = 2k-1 gives (3).

Formal verification and its scope

A Lean 4.19.0 formalization of the upper-bound reduction is provided as ancillary material with this article on arXiv. It is available through the ancillary-file links on the article’s abstract page. The source project includes a pinned mathlib dependency, a toolchain specification, and a README giving reproduction instructions and the correspondence between formal declarations and the paper’s arguments. The formalization verifies the encoding of unit diagonals, the uniform route type, acyclicity, the component count, and the transformation to a cover by shortest grid paths. The implementation uses local routes as an intermediate representation of the paths of HH.

The Fisher–Fitzpatrick grid-cover bound is an explicit hypothesis of the formal upper-bound theorem; that published result is not proved in the Lean project. The published lower-bound construction of Boyland et al. is also not formalized, and the formal exact-value statement assumes the existence of an attaining selection. Thus the formal verification covers the reduction and its conditional consequences, rather than every ingredient of Theorem 1.1. A separate Python script in the ancillary material checks explicit configurations attaining the known lower bound for all odd side lengths from 1 through 99. These finite checks supplement the proofs and do not replace them.

Disclosure of generative AI assistance

Generative AI tools (OpenAI Codex) assisted with the development and exposition of the proof, the drafting and revision of the manuscript, and the Lean formalization. The author is responsible for the mathematical claims, attribution, and submitted content. The scope of the formal verification is stated in § 4.

School of Mathematical Sciences, Peking University, Beijing, China

References

  1. [1]P. Boyland, I. Roth, G. Pintér, I. Laukó, J. E. Schoenfield, and S. Wasielewski, On the maximum number of non-intersecting diagonals in an array, J. Integer Seq. 20 (2017), Article 17.2.4. https://cs.uwaterloo.ca/journals/JIS/VOL20/Pinter/pinter3.html.
  2. [2]D. C. Fisher and S. L. Fitzpatrick, The isometric path number of a graph, J. Combin. Math. Combin. Comput. 38 (2001), 97–110. https://combinatorialpress.com/jcmcc-articles/volume-038/the-isometric-path-number-of-a-graph/.
  3. [3]P. Manuel, On the isometric path partition problem, Discuss. Math. Graph Theory 41 (2021), 1077–1089. https://doi.org/10.7151/dmgt.2236.
  4. [4]OEIS Foundation Inc., Entry A264041, The On-Line Encyclopedia of Integer Sequences, https://oeis.org/A264041, accessed October 15, 2026.

Paper details

vlnc:W_32n67mg6
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents