AFTD Auto-Formalizing Theoretical Domains

forest_carpool_final_discrepancy

def

The final discrepancy of a vertex after greedy orientation of the given edges with the given indexed tie-breaking coins.

Statement

def forest_carpool_final_discrepancy (n : ℕ) (edges : List (Fin n × Fin n)) (r : Fin edges.length → Bool) (v : Fin n) : ℤ
Source
Helper for OP-1106, forest greedy carpooling; related background arXiv:2611.00388.
Verified
13 Nov 2026
Axioms
none listed
Built on 2
  • carpool_discrepanciesThe sequence of discrepancy vectors (d₀, ..., d_T) starting from the zero vector, where each d_t is updated from d_{t-1} using the t-th…
  • carpool_greedy_orientationsGiven a list of edges and a list of tie-breaking coins, randomized greedy carpooling orients each edge toward the endpoint with smaller…
Used by 4

Lean source view module on GitHub

def forest_carpool_final_discrepancy (n : ℕ) (edges : List (Fin n × Fin n)) (r : Fin edges.length → Bool) (v : Fin n) : ℤ := ((carpool_discrepancies n edges (carpool_greedy_orientations n edges (List.ofFn r))).getLastD (fun _ => 0)) v
See it in the graphDiscuss this resultChallenge it