dephased_path_greedy_chosen
def
The greedy matching has just chosen the edge ending at b+1 exactly when the fold over the positions 0,…,b ends in the "chosen" state.
Statement
open scoped Classical in def dephased_path_greedy_chosen (n : ℕ) (I D : Finset ℕ) (left right : Bool) (b : ℕ) : Bool
- Source
- step towards dephased_path_unpinned_intervals_add_greedy_matching
- Verified
- 15 Nov 2026
- Axioms
- none listed
- Built on 1
- dephased_path_greedy_stateFolding the greedy step over the edge positions 0,…,m-1 yields the flag "the edge at m-1 was chosen" together with the number of edges…
- Used by 1
- dephased_path_active_positionAn unstruck active vertex: it lies in I ∩ D, the edge to its right was not chosen by the greedy matching, and its right end is either…
Lean source view module on GitHub
open scoped Classical in /-- Whether the left-to-right greedy matching chose the edge ending at position b+1, i.e. the flag after processing positions 0, …, b. -/ def dephased_path_greedy_chosen (n : ℕ) (I D : Finset ℕ) (left right : Bool) (b : ℕ) : Bool := (dephased_path_greedy_state n I D left right (b + 1)).1