is_algorithm1_output
A graph F on a finite type V is an output of Algorithm 1 on ordinal profile π : V → LinearOrder V if F is a tree (F.IsTree) and there exists a sequence of simple graphs of length k + 1 starting at the empty graph ⊥ and ending at F such that each step from seq(i) to seq(i+1) is a Borůvka round under π.
Statement
def is_algorithm1_output {V : Type*} [Fintype V] (π : V → LinearOrder V) (F : SimpleGraph V) : Prop
- Defined in
- arXiv:2610.23032 Algorithm 1
- Verified
- 20 Oct 2026
- Axioms
- none listed
- Built on 1
- boruvka_roundA Borůvka round transitions forest F to acyclic graph F' containing F under ordinal profile π : V → LinearOrder V if there exist for each…
Read back from the Lean
Given a finite type $V$, a family of linear orders $\pi : V \to \text{LinearOrder}(V)$ (giving a linear order on $V$ for each vertex in $V$), and a simple graph $F$ on $V$, is_algorithm1_output π F asserts that there exist a natural number $k$ and a sequence of simple graphs $\mathrm{seq} : \mathrm{Fin}(k + 1) \to \mathrm{SimpleGraph}(V)$ such that:
1. The initial graph $\mathrm{seq}(0)$ is the empty graph $\bot$ on $V$ (having no edges).
2. The final graph $\mathrm{seq}(\mathrm{last}(k))$ is $F$.
3. For each index $i \in \mathrm{Fin}(k)$, the transition from $\mathrm{seq}(i)$ to $\mathrm{seq}(i + 1)$ is a Borůvka round with respect to $\pi$ (boruvka_round π (seq i.castSucc) (seq i.succ)).
4. $F$ is a tree (F.IsTree, meaning $F$ is connected and acyclic).
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 tree F is an output of Algorithm 1 if it is reached from the empty forest by a sequence of Borůvka rounds. -/ def is_algorithm1_output {V : Type*} [Fintype V] (π : V → LinearOrder V) (F : SimpleGraph V) : Prop := ∃ (k : ℕ) (seq : Fin (k + 1) → SimpleGraph V), seq 0 = ⊥ ∧ seq (Fin.last k) = F ∧ (∀ i : Fin k, boruvka_round π (seq i.castSucc) (seq i.succ)) ∧ F.IsTree