op869_predecessor_causality
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.
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.
apply hAFor 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.
uses
op869_graph_from_predecessorsintro 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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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]