mondrian_height_graph_adj_of_mem
Every positive-height member of the rectangle list whose width is indivisible by d gives a height-graph edge between its bottom and top row levels.
Statement
theorem mondrian_height_graph_adj_of_mem (d : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ))
(r : ℕ × ℕ × ℕ × ℕ) (hr : r ∈ P) (hfree : ¬ d ∣ mondrian_rect_width r)
(hpos : r.2.2.1 < r.2.2.2) :
(mondrian_height_graph d P).Adj r.2.2.1 r.2.2.2- Source
- Helper for OP-280, arXiv:2610.19193, Section 1. Height-level networks are motivated by the graph model in arXiv:2007.09639, Section 1; the filtered graph and row-potential cut argument are developed here for the remaining cases with at least three prime factors.
- Verified
- 26 Oct 2026
- Axioms
- none — Lean reports it depends on no axioms
- Built on 2
- mondrian_height_graphThe undirected graph on integer row levels whose edges are the bottom and top levels of tiles with width indivisible by d; loops are…
- mondrian_rect_widthThe width x₁ − x₀ of the rectangle (x₀, x₁, y₀, y₁).
- Used by 2
- mondrian_perfect_height_component_countFor a perfect admissible n-square partition and prime p dividing n, each connected component of the height graph contains a number of…
- mondrian_partition_width_free_height_reachableIf d divides the square side and a tile has width indivisible by d, its bottom and top row levels remain connected in the height graph…
The proof, explained
To show that the bottom and top vertical coordinates of the rectangle r form an edge in the height graph, we directly verify the definition of adjacency. The strict inequality between the bottom and top coordinates guarantees that the two vertices are distinct, and r itself provides the required rectangle in P whose width is not divisible by d.
The levels r.2.2.1 and r.2.2.2 are adjacent in the height graph mondrian_height_graph d P
By definition, two vertices x and y are adjacent in the height graph if x ≠ y and there exists a rectangle in P with indivisible width whose bottom and top coordinates are x and y (in either order). We instantiate this definition using r itself: the condition r.2.2.1 ≠ r.2.2.2 follows from r.2.2.1 < r.2.2.2 by Nat.ne_of_lt; the rectangle r belongs to P and has width indivisible by d by the hypotheses hr and hfree; and the coordinate matching holds by reflexivity in the left branch of the disjunction via Or.inl.
uses
Nat.ne_of_lt,Or.inlexact ⟨Nat.ne_of_lt hpos, r, hr, hfree, Or.inl ⟨rfl, rfl⟩⟩
Nat.ne_of_lt- if a natural number is strictly less than another, it is not equal to it
Or.inl- given a proof of A, establishes the disjunction A ∨ B
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem mondrian_height_graph_adj_of_mem (d : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ)) (r : ℕ × ℕ × ℕ × ℕ) (hr : r ∈ P) (hfree : ¬ d ∣ mondrian_rect_width r) (hpos : r.2.2.1 < r.2.2.2) : (mondrian_height_graph d P).Adj r.2.2.1 r.2.2.2 := by exact ⟨Nat.ne_of_lt hpos, r, hr, hfree, Or.inl ⟨rfl, rfl⟩⟩