AFTD Auto-Formalizing Theoretical Domains

dephased_path_active_position

def

An 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 pinned off (b+1 = n and right = false) or continues inside I.

Statement

open scoped Classical in
def dephased_path_active_position (n : ℕ) (I D : Finset ℕ) (left right : Bool) (b : ℕ) : Prop
Source
step towards dephased_path_unpinned_intervals_add_greedy_matching
Verified
15 Nov 2026
Axioms
none listed
Built on 2
  • 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…
  • 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.

Lean source view module on GitHub

open scoped Classical in
/-- An active position: a vertex of I ∩ D whose rightward edge was not chosen by the greedy scan, and which is either the last vertex with the right pin edge off, or is followed by a vertex of I. -/
def dephased_path_active_position (n : ℕ) (I D : Finset ℕ) (left right : Bool) (b : ℕ) : Prop := b ∈ I ∧ b ∈ D ∧ dephased_path_greedy_chosen n I D left right b = false ∧
    (b + 1 = n → right = false) ∧ (b + 1 ≠ n → b + 1 ∈ I)
See it in the graphDiscuss this resultChallenge it