AFTD Auto-Formalizing Theoretical Domains

op869_predecessor_causality

theoremverified

If two predecessor presentations agree through vertex i, any online coloring algorithm gives vertex i the same color on both graphs.

Statement

theorem op869_predecessor_causality {n : ℕ} (A : SimpleGraph (Fin n) → Fin n → ℕ)
    (hA : IsOnlineColoringAlg A) (P Q : Fin n → Finset (Fin n)) (i : Fin n)
    (hPQ : ∀ j : Fin n, j ≤ i → P j = Q j) :
    A (op869_graph_from_predecessors P) i = A (op869_graph_from_predecessors Q) i
Source
arXiv:2610.41516, Sections 1 and 2; formal infrastructure for the adaptive online-coloring construction.
Verified
11 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • op869_graph_from_predecessorsThe 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…
  • IsOnlineColoringAlgA deterministic coloring algorithm A : SimpleGraph (Fin n) → (Fin n → ℕ) assigning natural number colors to vertices of graphs on Fin n is…
Used by 1
  • op869_adversary_forces_soundA winning one-fold adversary position, whose recorded earlier colors agree with a proper online algorithm on the current predecessor…

The proof, explained

An online coloring algorithm determines the color of vertex i solely from the edges among vertices up to i. Because the predecessor assignments P and Q agree on all vertices up to i, the graphs constructed from them have the exact same edges on these vertices. Therefore, the algorithm assigns vertex i the same color in both graphs.

  1. It suffices to show that the graphs generated by P and Q agree on all edges between vertices at most i.

    By definition of an online coloring algorithm (hA), the color assigned to vertex i depends only on the induced subgraph on vertices at most i. Thus, if the two graphs have identical adjacency relations on {j | j ≤ i}, the algorithm must output the same color at vertex i for both.

    line 5

      apply hA
  2. For any vertices j, l ≤ i, j and l are adjacent in the graph from P if and only if they are adjacent in the graph from Q.

    Let j, l ≤ i. Unfolding the definition of op869_graph_from_predecessors, an edge between j and l requires j ∈ P l (when j < l) or l ∈ P j (when l < j). Since j ≤ i and l ≤ i, the hypothesis hPQ ensures P j = Q j and P l = Q l. Rewriting with these equalities makes the adjacency condition under P identical to that under Q.

    lines 6–8

    uses op869_graph_from_predecessors

      intro j l hj hl
      simp only [op869_graph_from_predecessors]
      rw [hPQ j hj, hPQ l hl]
op869_graph_from_predecessors
the simple graph on Fin n where an undirected edge connects two vertices if and only if the smaller vertex is in the predecessor set of the larger

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

theorem op869_predecessor_causality {n : ℕ} (A : SimpleGraph (Fin n) → Fin n → ℕ)    (hA : IsOnlineColoringAlg A) (P Q : Fin n → Finset (Fin n)) (i : Fin n)    (hPQ : ∀ j : Fin n, j ≤ i → P j = Q j) :    A (op869_graph_from_predecessors P) i = A (op869_graph_from_predecessors Q) i := by  apply hA  intro j l hj hl  simp only [op869_graph_from_predecessors]  rw [hPQ j hj, hPQ l hl]
See it in the graphDiscuss this resultChallenge it