AFTD Auto-Formalizing Theoretical Domains

dephased_path_greedy_state

def

Folding 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 chosen so far.

Statement

open scoped Classical in
def dephased_path_greedy_state (n : ℕ) (I D : Finset ℕ) (left right : Bool) (m : ℕ) : Bool × ℕ
Source
step towards dephased_path_unpinned_intervals_add_greedy_matching
Verified
15 Nov 2026
Axioms
none listed
Built on 1
  • dephased_path_active_edgeFor a path on n vertices with vertex sets I, D ⊆ ℕ and end pin flags left, right, the activity flag of the cut edge at position e: the end…
Used by 2
  • dephased_path_greedy_chosenThe 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.
  • 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
/-- State of the left-to-right greedy matching after processing the edge positions 0, …, m-1: a "was the last processed edge chosen" flag together with the number of chosen edges. -/
def dephased_path_greedy_state (n : ℕ) (I D : Finset ℕ) (left right : Bool) (m : ℕ) : Bool × ℕ := (List.range m).foldl
    (fun acc e =>
      if dephased_path_active_edge n I D left right e && !acc.1 then (true, acc.2 + 1)
      else (false, acc.2)) (false, 0)
See it in the graphDiscuss this resultChallenge it