max_vertex_discrepancy
def
The maximum absolute discrepancy among all vertices for an integer discrepancy vector d on n vertices.
Statement
def max_vertex_discrepancy (n : ℕ) (d : Fin n → ℤ) : ℕ- Defined in
- arXiv:2611.00388 Sec 1.1, Online carpooling against an oblivious adversary
- Verified
- 06 Nov 2026
- Axioms
- none listed
- Used by 4
- 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_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_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…
- carpool_max_discrepancyThe maximum discrepancy M_T over all time steps 0 ≤ t ≤ T of the maximum vertex discrepancy.
Read back from the Lean
Given a natural number $n$ and a function $d : \mathrm{Fin}\ n \to \mathbb{Z}$, max_vertex_discrepancy n d is defined as the supremum (maximum) over all vertices $v \in \mathrm{Fin}\ n$ of the absolute value $|d(v)|$ (as a natural number), evaluating to $0$ if $n = 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 supremum norm of an integer discrepancy vector on n vertices. -/ def max_vertex_discrepancy (n : ℕ) (d : Fin n → ℤ) : ℕ := Finset.univ.sup (fun v => (d v).natAbs)