op_1106_forest_carpooling_single_edge_max_discrepancy
For any single edge on Fin n with distinct endpoints and any initial coin, randomized greedy carpooling produces a maximum discrepancy of at most 1.
Statement
theorem op_1106_forest_carpooling_single_edge_max_discrepancy
(n : ℕ) (e : Fin n × Fin n) (he : e.1 ≠ e.2) (c : Bool) :
carpool_max_discrepancy n [e] (carpool_greedy_orientations n [e] [c]) ≤ 1- Source
- arXiv:2611.00388: Online carpooling against an oblivious adversary; OP-1106
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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…
- carpool_max_discrepancyThe maximum discrepancy M_T over all time steps 0 ≤ t ≤ T of the maximum vertex discrepancy.
- 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.
Read back from the Lean
For any natural number n, any edge e : Fin n × Fin n whose endpoints are distinct (e.1 ≠ e.2), and any boolean coin flip c: the maximum vertex discrepancy throughout the greedy carpooling orientation process on the single-edge list [e] with tie-breaker coin list [c] is at most 1.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
Greedy carpooling on an instance consisting of a single edge produces a single orientation decision. The result then follows from `op_902_single_edge_max_discrepancy`, which proves that any orientation of a single edge with distinct endpoints achieves a maximum discrepancy of at most 1. The proof applies this lemma and discharges the requirement that the endpoints are distinct using the assumed hypothesis.
The maximum discrepancy under greedy carpooling for a single edge is at most 1.
Greedy carpooling on a single-edge instance $[e]$ assigns a single orientation bit to $e$. By `op_902_single_edge_max_discrepancy`, any orientation of a single edge with distinct endpoints achieves a maximum discrepancy of at most 1. Applying this lemma reduces the goal to the hypothesis that the endpoints of $e$ are distinct ($e.1 \neq e.2$), which is provided by the hypothesis $he$.
uses
op_902_single_edge_max_discrepancycarpool_max_discrepancy n [e] (carpool_greedy_orientations n [e] [c]) ≤ 1 := by first | exact op_902_single_edge_max_discrepancy | (apply op_902_single_edge_max_discrepancy <;> assumption) | (apply op_902_single_edge_max_discrepancy <;> simp_all) | simpa using op_902_single_edge_max_discrepancy | (simp only [carpool_max_discrepancy, carpool_greedy_orientations] at *; first | exact op_902_single_edge_max_discrepancy | (apply op_902_single_edge_max_discrepancy <;> assumption) | (apply op_902_single_edge_max_discrepancy <;> simp_all) | simpa using op_902_single_edge_max_discrepancy)
op_902_single_edge_max_discrepancy- Any single orientation of an edge with distinct endpoints results in a maximum discrepancy of at most 1.
- The tactic is structured as a `first | ...` block of fallbacks. The second branch, `apply op_902_single_edge_max_discrepancy <;> assumption`, succeeds and closes the goal immediately; the later branches are never executed.
- Lean definitionally matches the single-element list produced by `carpool_greedy_orientations n [e] [c]` with the arbitrary singleton orientation `[b]` in `op_902_single_edge_max_discrepancy`.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- On a single-edge carpooling instance with distinct endpoints, randomized greedy orientation achieves maximum discrepancy at most 1. -/theorem op_1106_forest_carpooling_single_edge_max_discrepancy (n : ℕ) (e : Fin n × Fin n) (he : e.1 ≠ e.2) (c : Bool) : carpool_max_discrepancy n [e] (carpool_greedy_orientations n [e] [c]) ≤ 1 := by first | exact op_902_single_edge_max_discrepancy | (apply op_902_single_edge_max_discrepancy <;> assumption) | (apply op_902_single_edge_max_discrepancy <;> simp_all) | simpa using op_902_single_edge_max_discrepancy | (simp only [carpool_max_discrepancy, carpool_greedy_orientations] at *; first | exact op_902_single_edge_max_discrepancy | (apply op_902_single_edge_max_discrepancy <;> assumption) | (apply op_902_single_edge_max_discrepancy <;> simp_all) | simpa using op_902_single_edge_max_discrepancy)