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
- forest_carpool_disjoint_components_independentIf appending the edge u-v to the given prefix yields a forest, then under uniformly random prefix coins the two endpoint final…
- forest_carpool_component_coin_localityTwo coin assignments that agree on every edge in the final connected component of a fixed vertex give the same final greedy discrepancy at…
- forest_carpool_final_one_sided_fibonacci_tailFor any forest arrival sequence and any vertex, the finite uniform probability that its final greedy discrepancy is at least D is bounded…
- forest_carpool_maximum_fibonacci_tailFor a forest arrival sequence, the probability that any vertex at any prefix has absolute discrepancy at least D is at most four times the…
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