carpool_max_discrepancy
The maximum discrepancy M_T over all time steps 0 ≤ t ≤ T of the maximum vertex discrepancy.
Statement
def carpool_max_discrepancy (n : ℕ) (edges : List (Fin n × Fin n)) (signs : List Bool) : ℕ- Defined in
- arXiv:2611.00388 Eq (1.2), Online carpooling against an oblivious adversary
- Verified
- 06 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…
- max_vertex_discrepancyThe maximum absolute discrepancy among all vertices for an integer discrepancy vector d on n vertices.
- Used by 5
- 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.
- op_1106_forest_carpooling_single_edge_max_discrepancyFor any single edge on Fin n with distinct endpoints and any initial coin, randomized greedy carpooling produces a maximum discrepancy of…
- 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…
- op_1106_forest_carpooling_random_greedy_double_exponential_tailThere exist absolute positive real constants c, C, and a such that for every natural number n, every forest edge sequence of length T ≥ 2…
- 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
The definition carpool_max_discrepancy n edges signs computes the maximum discrepancy across all vertices and across all prefix steps during the carpool process, returning a natural number ℕ.
Given:
- n : ℕ: the number of vertices, with vertex set Fin n,
- edges : List (Fin n × Fin n): a sequence of directed edges,
- signs : List Bool: a sequence of boolean choices,
the function computes:
1. The list of pairs obtained by zipping edges with signs (truncated to the length of the shorter list).
2. The sequence of discrepancy functions Fin n → ℤ produced by scanl, starting from the all-zero function fun _ => 0. At each step with edge e = (u, v) and sign b : Bool, the discrepancy vector d is updated at vertex x by adding (if b then 1 else -1) if x = u and (if b then -1 else 1) if x = v (adding both if u = v).
3. For each intermediate discrepancy state d : Fin n → ℤ (including the initial all-zero state), the maximum vertex discrepancy max_{v : Fin n} |d(v)| (computed via Finset.univ.sup (fun v => (d v).natAbs)).
4. The maximum over all intermediate states of these maximum vertex discrepancies, folded via max starting at 0.
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 maximum prefix discrepancy M_T of an online carpooling trajectory. -/ def carpool_max_discrepancy (n : ℕ) (edges : List (Fin n × Fin n)) (signs : List Bool) : ℕ := ((carpool_discrepancies n edges signs).map (max_vertex_discrepancy n)).foldl max 0