carpool_greedy_orientations
Given a list of edges and a list of tie-breaking coins, randomized greedy carpooling orients each edge toward the endpoint with smaller current indegree-minus-outdegree discrepancy (starting from zero), using the corresponding boolean coin to resolve ties.
Statement
def carpool_greedy_orientations (n : ℕ) (edges : List (Fin n × Fin n)) (coins : List Bool) :
List Bool- Defined in
- arXiv:2611.00388: Online carpooling against an oblivious adversary; OP-1106
- Verified
- 08 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 6
- forest_carpool_final_discrepancyThe final discrepancy of a vertex after greedy orientation of the given edges with the given indexed tie-breaking coins.
- 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…
- 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…
- 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
carpool_greedy_orientations n edges coins defines a function taking a natural number n, a list of directed edges edges : List (Fin n × Fin n), and a list of tie-breaking boolean flags coins : List Bool, and returning a list of booleans List Bool.
The function iterates through edges and coins in lockstep, maintaining a state vector d : Fin n → ℤ initially zero everywhere (fun _ => 0):
- If either edges or coins is empty, it returns [].
- For each edge e = (u, v) and coin c:
- If d u < d v, it chooses orientation true.
- If d v < d u, it chooses orientation false.
- If d u = d v, it chooses orientation c.
- It then records this boolean decision and recurses on the remaining edges and coins with the updated state carpool_step n d e b.
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 sequence of orientation bits chosen by the randomized greedy carpooling algorithm starting from discrepancy 0, orienting each edge toward the endpoint with smaller current discrepancy and breaking ties using the corresponding coin. -/ def carpool_greedy_orientations (n : ℕ) (edges : List (Fin n × Fin n)) (coins : List Bool) : List Bool := let rec aux : List (Fin n × Fin n) → List Bool → (Fin n → ℤ) → List Bool | [], _, _ => [] | _, [], _ => [] | e :: es, c :: cs, d => let b := if d e.1 < d e.2 then true else if d e.2 < d e.1 then false else c b :: aux es cs (carpool_step n d e b) aux edges coins (fun _ => 0)