IsOnlineColoringAlg
A deterministic coloring algorithm A : SimpleGraph (Fin n) → (Fin n → ℕ) assigning natural number colors to vertices of graphs on Fin n is online (causal) if for any two graphs G₁ and G₂ and any vertex i : Fin n, if for all j, l ≤ i we have G₁.Adj j l ↔ G₂.Adj j l, then A G₁ i = A G₂ i.
Statement
def IsOnlineColoringAlg {n : ℕ} (A : SimpleGraph (Fin n) → (Fin n → ℕ)) : Prop
- Defined in
- arXiv:2610.41516 Section 1
- Verified
- 02 Nov 2026
- Axioms
- none listed
- Used by 3
- 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_three_colorable_bound_implies_deterministic_lower_boundIf the three-colorable deterministic online coloring lower bound of arXiv:2610.41516 Theorem 1.1 holds in the stated finite-graph model,…
Read back from the Lean
For a fixed natural number $n$ and a map $A$ from simple graphs on vertex set $\operatorname{Fin} n$ to assignments $\operatorname{Fin} n \to \mathbb{N}$, IsOnlineColoringAlg A asserts that for all simple graphs $G_1, G_2$ on $\operatorname{Fin} n$ and every vertex $i : \operatorname{Fin} n$, if $G_1$ and $G_2$ agree on adjacency between all pairs of vertices $j, l \le i$ (that is, for all $j, l : \operatorname{Fin} n$ with $j \le i$ and $l \le i$, $G_1\text{.Adj } j\ l \leftrightarrow G_2\text{.Adj } j\ l$), then $A(G_1)(i) = A(G_2)(i)$.
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
/-- A deterministic vertex coloring algorithm on Fin n assigning natural number colors is online if the color of vertex i depends only on edges between vertices up to index i. -/ def IsOnlineColoringAlg {n : ℕ} (A : SimpleGraph (Fin n) → (Fin n → ℕ)) : Prop := ∀ (G₁ G₂ : SimpleGraph (Fin n)) (i : Fin n), (∀ j l : Fin n, j ≤ i → l ≤ i → (G₁.Adj j l ↔ G₂.Adj j l)) → A G₁ i = A G₂ i