is_admissible_diagonal_selection
A selection M of unit diagonals on the grid V_{2k-1} = {0, ..., 2k-1}^2 is admissible if its edges are unit diagonals, have pairwise disjoint endpoints, and no unit square contains both of its diagonals.
Statement
def is_admissible_diagonal_selection (k : ℕ) (M : Finset (Sym2 (Fin (2 * k) × Fin (2 * k)))) : Prop
- Defined in
- arXiv:2610.33042 Section 1 and Section 2
- Verified
- 27 Oct 2026
- Axioms
- none listed
Read back from the Lean
A predicate is_admissible_diagonal_selection k M asserting that, for a given natural number k and a finite set M of unordered pairs of vertices in Fin (2 * k) × Fin (2 * k), all of the following hold:
1. **Every edge is a unit-square diagonal**: For every e ∈ M, there exist vertices u and v such that e = s(u, v) (the unordered pair of u and v), and there exist natural numbers r and c with r + 1 < 2 * k and c + 1 < 2 * k such that either:
- u = (r, c) and v = (r + 1, c + 1) (or vice-versa), or
- u = (r, c + 1) and v = (r + 1, c) (or vice-versa).
2. **Vertex-disjointness**: For all e₁, e₂ ∈ M, if e₁ ≠ e₂, then e₁ and e₂ share no vertices (for every vertex v, if v ∈ e₁ then v ∉ e₂).
3. **No crossing diagonals**: For all natural numbers r and c with r + 1 < 2 * k and c + 1 < 2 * k, M does not contain both diagonals of the unit square [r, r+1] × [c, c+1], i.e., it is not the case that both s((r, c), (r + 1, c + 1)) ∈ M and s((r, c + 1), (r + 1, c)) ∈ M.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- An admissible selection of unit diagonals on V_{2k-1} is a matching of unit diagonals containing at most one diagonal from each unit square. -/ def is_admissible_diagonal_selection (k : ℕ) (M : Finset (Sym2 (Fin (2 * k) × Fin (2 * k)))) : Prop := (∀ e ∈ M, ∃ u v, e = s(u, v) ∧ ((∃ (r c : ℕ) (hr : r + 1 < 2 * k) (hc : c + 1 < 2 * k), (u = (⟨r, by omega⟩, ⟨c, by omega⟩) ∧ v = (⟨r + 1, hr⟩, ⟨c + 1, hc⟩) ∨ u = (⟨r + 1, hr⟩, ⟨c + 1, hc⟩) ∧ v = (⟨r, by omega⟩, ⟨c, by omega⟩))) ∨ (∃ (r c : ℕ) (hr : r + 1 < 2 * k) (hc : c + 1 < 2 * k), (u = (⟨r, by omega⟩, ⟨c + 1, hc⟩) ∧ v = (⟨r + 1, hr⟩, ⟨c, by omega⟩) ∨ u = (⟨r + 1, hr⟩, ⟨c, by omega⟩) ∧ v = (⟨r, by omega⟩, ⟨c + 1, hc⟩))))) ∧ (∀ e₁ ∈ M, ∀ e₂ ∈ M, e₁ ≠ e₂ → ∀ v, v ∈ e₁ → v ∉ e₂) ∧ (∀ (r c : ℕ) (hr : r + 1 < 2 * k) (hc : c + 1 < 2 * k), ¬ (s((⟨r, by omega⟩, ⟨c, by omega⟩), (⟨r + 1, hr⟩, ⟨c + 1, hc⟩)) ∈ M ∧ s((⟨r, by omega⟩, ⟨c + 1, hc⟩), (⟨r + 1, hr⟩, ⟨c, by omega⟩)) ∈ M))