op869_graph_from_predecessors
def
The simple graph on the ordered vertices Fin n whose edge from an earlier vertex a to a later vertex b exists exactly when a is in the predecessor set of b.
Statement
def op869_graph_from_predecessors {n : ℕ} (P : Fin n → Finset (Fin n)) : SimpleGraph (Fin n)- Source
- arXiv:2610.41516, Sections 1 and 2; formal infrastructure for the adaptive online-coloring construction.
- Verified
- 11 Nov 2026
- Axioms
- none listed
- Built on 2
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- TotalPreorderA total preorder: a preorder where
- Used by 9
- op869_predecessor_colorable_iffThe graph built from predecessor sets is k-colorable exactly when the vertices admit k colors with different colors on each…
- op869_bounded_adversary_forces_unboundedA winning post-degree-bounded t-fold adversary position also wins the same game without the post-degree restriction.
- op869_bounded_adversary_one_vertexWhen n and k are positive, an isolated vertex forces t colors in the bounded t-fold game in one move, for every post-degree bound D.
- op869_adversary_forces_soundA winning one-fold adversary position, whose recorded earlier colors agree with a proper online algorithm on the current predecessor…
- op869_predecessor_causalityIf two predecessor presentations agree through vertex i, any online coloring algorithm gives vertex i the same color on both graphs.
- op869_bounded_fuel_monoIncreasing the number of remaining moves preserves a winning position in the bounded online coloring adversary game.
- op869_adversary_one_vertexFor any positive vertex and color bounds, a t-fold adversary can force t colors in one move from the empty position.
- op869_adversary_forcesA bounded t-fold online-coloring adversary position is winning if, before the move budget or vertex indices run out, the adversary can…
- op869_bounded_adversary_forcesThe bounded t-fold adversary game is the t-fold game where, after each move, every vertex has post-degree at most D.
Lean source view module on GitHub
def op869_graph_from_predecessors {n : ℕ} (P : Fin n → Finset (Fin n)) : SimpleGraph (Fin n) where Adj a b := (a < b ∧ a ∈ P b) ∨ (b < a ∧ b ∈ P a) symm := by constructor intro a b h rcases h with h | h · exact Or.inr h · exact Or.inl h loopless := by constructor intro a simp