AFTD Auto-Formalizing Theoretical Domains

song_aux_matching

def

The auxiliary perfect matching N of the blocks: in a block that already carries a diagonal of M (ad or bc), take the two horizontal edges ab and cd; in a block carrying no diagonal of M, take the two diagonals ad and bc. This is Table 1 (Section 3.1) of arXiv:2610.33042.

Statement

noncomputable def song_aux_matching (k : ℕ) (M : Finset (Sym2 (Fin (2 * k) × Fin (2 * k)))) : Finset (Sym2 (Fin (2 * k) × Fin (2 * k)))
Source
step towards admissible_diagonal_selection_isometric_path_cover
Verified
28 Oct 2026
Axioms
none listed
Built on 1
  • song_block_vertexCorner (u,v) of the 2x2 block B_{ij} of the (2k)x(2k) grid: song_block_vertex k i j u v = (2i+u, 2j+v). With (u,v) =…
Used by 1
  • song_edge_graphThe alternating graph H = (V_{2k-1}, M ∪ N) on the (2k)x(2k) grid vertices, whose edges are the selected diagonals together with the…

Lean source view module on GitHub

/-- Auxiliary perfect matching N: in a block holding an internal M-diagonal it uses the horizontal pairs {ab, cd}, otherwise the diagonal pairs {ad, bc}. This is Table 1 of Song, arXiv:2610.33042. -/
noncomputable def song_aux_matching (k : ℕ) (M : Finset (Sym2 (Fin (2 * k) × Fin (2 * k)))) : Finset (Sym2 (Fin (2 * k) × Fin (2 * k))) := Finset.univ.biUnion (fun p : Fin k × Fin k =>
    if s(song_block_vertex k p.1 p.2 0 0, song_block_vertex k p.1 p.2 1 1) ∈ M ∨
       s(song_block_vertex k p.1 p.2 0 1, song_block_vertex k p.1 p.2 1 0) ∈ M
    then ({s(song_block_vertex k p.1 p.2 0 0, song_block_vertex k p.1 p.2 0 1),
           s(song_block_vertex k p.1 p.2 1 0, song_block_vertex k p.1 p.2 1 1)} : Finset _)
    else ({s(song_block_vertex k p.1 p.2 0 0, song_block_vertex k p.1 p.2 1 1),
           s(song_block_vertex k p.1 p.2 0 1, song_block_vertex k p.1 p.2 1 0)} : Finset _))
See it in the graphDiscuss this resultChallenge it