AFTD Auto-Formalizing Theoretical Domains

op_1106_forest_carpooling_single_edge_max_discrepancy

theoremverified

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.

  1. 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$.

    line 4

    uses op_902_single_edge_max_discrepancy

        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)
op_902_single_edge_max_discrepancy
Any single orientation of an edge with distinct endpoints results in a maximum discrepancy of at most 1.

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

/-- 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)
See it in the graphDiscuss this resultChallenge it