path_cut_word
def
path_cut_word n S is the length-(n-1) boolean word whose j-th letter records whether the j-th edge of the path pathGraph n (i.e. the edge between vertex j and vertex j+1) crosses the cut (S, Sᶜ). So letter j is true exactly when exactly one of j, j+1 lies in S.
Statement
def path_cut_word (n : ℕ) (S : Finset (Fin n)) : List Bool- Source
- step towards claw_free_tree_graph_state_mmi
- Verified
- 01 Nov 2026
- Axioms
- none listed
- Used by 3
- path_cut_word_odd_run_ineqFor a four-partition A,B,C,D of the vertices of the path P_n, the sum of the numbers of maximal odd-length crossing runs for A, B, C and D…
- path_cut_word_count_cancelFor a four-partition A,B,C,D of the vertices of the path P_n, the total number of edges crossing the cuts defined by A, B, C, D equals the…
- path_cert_word_eq_cut_wordThe Boolean edge word used by the finite-state certificate is the ordinary path cut word of the corresponding color mask.
Lean source view module on GitHub
/-- Indicator word of the crossing edges of `S` along the path `pathGraph n`. -/ def path_cut_word (n : ℕ) (S : Finset (Fin n)) : List Bool := List.ofFn (fun j : Fin (n - 1) => (decide ((⟨j.val, by omega⟩ : Fin n) ∈ S)) != (decide ((⟨j.val + 1, by omega⟩ : Fin n) ∈ S)))