ValidCarpoolEdgeSequence
def
A list of edges on n vertices is valid for online carpooling if every arriving edge connects two distinct vertices.
Statement
def ValidCarpoolEdgeSequence (n : ℕ) (edges : List (Fin n × Fin n)) : Prop
- Defined in
- arXiv:2611.00388 Sec 1.1, Online carpooling against an oblivious adversary
- Verified
- 06 Nov 2026
- Axioms
- none listed
- Used by 5
- 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…
- CarpoolForestEdgeSequenceA list of edges on Fin n is an oblivious forest edge sequence for online carpooling if all edges connect distinct vertices, no undirected…
- 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…
- 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 of elements of Fin n, ValidCarpoolEdgeSequence n edges asserts that for every edge e in edges, the first component e.1 is not equal to the second component e.2 (that is, no edge in the list is a self-loop).
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
/-- Validity condition that every edge joins two distinct vertices. -/ def ValidCarpoolEdgeSequence (n : ℕ) (edges : List (Fin n × Fin n)) : Prop := ∀ e ∈ edges, e.1 ≠ e.2