AFTD Auto-Formalizing Theoretical Domains

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 than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
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
See it in the graphDiscuss this resultChallenge it