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 _))