carpool_step
def
In online carpooling on n vertices, given an edge e joining two distinct vertices and an orientation bit b, the discrepancy vector d updates by adding 1 to e.1 and -1 to e.2 if b is true, and the opposite if b is false.
Statement
def carpool_step (n : ℕ) (d : Fin n → ℤ) (e : Fin n × Fin n) (b : Bool) : Fin n → ℤ- Defined in
- arXiv:2611.00388 Eq (1.1), Online carpooling against an oblivious adversary
- Verified
- 06 Nov 2026
- Axioms
- none listed
- Used by 7
- 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…
- op_902_single_edge_max_discrepancyOn any single-edge carpooling instance with distinct endpoints, the maximum discrepancy under any orientation sign is at most 1.
- 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…
- 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…
- 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…
Read back from the Lean
carpool_step n d e b is the function Fin n → ℤ that updates a vector d : Fin n → ℤ along a pair e = (e.1, e.2) : Fin n × Fin n according to a boolean b : Bool. For any v : Fin n, the value is:
- d v + (if b then 1 else -1) if v = e.1 and v ≠ e.2;
- d v + (if b then -1 else 1) if v = e.2 and v ≠ e.1;
- d v if v = e.1 = e.2 (the +1 and -1 cancel out);
- d v if v ≠ e.1 and v ≠ e.2.
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
/-- One step of discrepancy update in online carpooling for an edge e with orientation sign b. -/ def carpool_step (n : ℕ) (d : Fin n → ℤ) (e : Fin n × Fin n) (b : Bool) : Fin n → ℤ := fun v => d v + (if v = e.1 then (if b then 1 else -1) else 0) + (if v = e.2 then (if b then -1 else 1) else 0)