AFTD Auto-Formalizing Theoretical Domains

IsOnlineColoringAlg

def

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

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
See it in the graphDiscuss this resultChallenge it