carpool_discrepancies
The 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 edge and its orientation sign.
Statement
def carpool_discrepancies (n : ℕ) (edges : List (Fin n × Fin n)) (signs : List Bool) :
List (Fin n → ℤ)- Defined in
- arXiv:2611.00388 Eq (1.1), Online carpooling against an oblivious adversary
- Verified
- 06 Nov 2026
- Axioms
- none listed
- Built on 1
- carpool_stepIn online carpooling on n vertices, given an edge e joining two distinct vertices and an orientation bit b, the discrepancy vector d…
- Used by 4
- forest_carpool_final_discrepancyThe final discrepancy of a vertex after greedy orientation of the given edges with the given indexed tie-breaking coins.
- 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…
- op_1106_forest_carpooling_length_two_boundFor any oblivious forest edge sequence of length 2 on Fin n and any assignment of 2 coins, the maximum prefix discrepancy under randomized…
- carpool_max_discrepancyThe maximum discrepancy M_T over all time steps 0 ≤ t ≤ T of the maximum vertex discrepancy.
Read back from the Lean
A definition of carpool_discrepancies n edges signs, which computes the list of cumulative discrepancy states (functions from Fin n to ℤ) across a sequence of steps.
Given:
- n : ℕ, the number of vertices,
- edges : List (Fin n × Fin n), a list of directed edges,
- signs : List Bool, a list of boolean signs,
the function pairs edges and signs elementwise using List.zip (truncating to the length of the shorter list), and performs a left scan (List.scanl) starting from the all-zero discrepancy function fun _ => 0. At each step, for the current discrepancy d : Fin n → ℤ, an edge e = (e.1, e.2), and a boolean sign b, the discrepancy is updated via carpool_step n d e b:
- vertex e.1 changes by +1 if b = true and -1 if b = false;
- vertex e.2 changes by -1 if b = true and +1 if b = false (with effects summing to 0 if e.1 = e.2);
- all other vertices remain unchanged.
The resulting list has length min (edges.length) (signs.length) + 1, with the initial all-zero function as its first element.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The trajectory of discrepancy vectors from time 0 to T for an edge sequence and signs. -/ def carpool_discrepancies (n : ℕ) (edges : List (Fin n × Fin n)) (signs : List Bool) : List (Fin n → ℤ) := (edges.zip signs).scanl (fun d (e, b) => carpool_step n d e b) (fun _ => 0)