CarpoolForestEdgeSequence
A list of edges on Fin n is an oblivious forest edge sequence for online carpooling if all edges connect distinct vertices, no undirected edge appears more than once, and the simple graph formed by the edges is acyclic.
Statement
def CarpoolForestEdgeSequence (n : ℕ) (edges : List (Fin n × Fin n)) : Prop
- Defined in
- arXiv:2611.00388: Online carpooling against an oblivious adversary; OP-1106
- Verified
- 08 Nov 2026
- Axioms
- none listed
- Built on 1
- ValidCarpoolEdgeSequenceA list of edges on n vertices is valid for online carpooling if every arriving edge connects two distinct vertices.
- Used by 7
- carpool_forest_edge_sequence_nilThe empty list of edges is an oblivious forest edge sequence on Fin n.
- forest_carpool_disjoint_components_independentIf appending the edge u-v to the given prefix yields a forest, then under uniformly random prefix coins the two endpoint final…
- forest_carpool_append_edge_disconnectedWhen a new edge appended to an edge sequence still forms a forest with no duplicate undirected edges, its endpoints lie in distinct…
- 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_final_one_sided_fibonacci_tailFor any forest arrival sequence and any vertex, the finite uniform probability that its final greedy discrepancy is at least D is bounded…
- 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
Given a natural number n and a list edges of pairs (u, v) of vertices in Fin n, CarpoolForestEdgeSequence n edges asserts that:
1. Every edge e ∈ edges has distinct endpoints (e.1 ≠ e.2, i.e., no self-loops).
2. The list obtained by mapping each edge e in edges to the unordered pair s(e.1, e.2) contains no duplicate elements (List.Nodup). In particular, no undirected edge appears more than once, so neither duplicate directed edges nor pairs of antiparallel edges (u, v) and (v, u) are present.
3. The simple graph on Fin n whose edge set is {s(e.1, e.2) | e ∈ edges} is acyclic (i.e., a forest).
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
/-- A list of edges on Fin n is a carpool forest edge sequence if every edge connects distinct vertices, the undirected edges are pairwise distinct, and their union forms an acyclic simple graph (a forest). -/ def CarpoolForestEdgeSequence (n : ℕ) (edges : List (Fin n × Fin n)) : Prop := ValidCarpoolEdgeSequence n edges ∧ (edges.map (fun e => s(e.1, e.2))).Nodup ∧ (SimpleGraph.fromEdgeSet {s(e.1, e.2) | e ∈ edges}).IsAcyclic