AFTD Auto-Formalizing Theoretical Domains

is_globally_best_outside

def

Given a simple graph G on V, an ordinal profile π : V → LinearOrder V, and vertices r, g : V, is_globally_best_outside G π r g holds if g does not belong to the same connected component of G as r, and for every vertex v not in the same connected component of G as r, g ≤ v according to the linear order π r.

Statement

def is_globally_best_outside {V : Type*} (G : SimpleGraph V) (π : V → LinearOrder V) (r g : V) : Prop
Defined in
arXiv:2610.23032 Definition 1
Verified
20 Oct 2026
Axioms
none listed
Used by 2
  • 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…
  • boruvka_round_contraction_leIn any Borůvka round from F to F' under profile π : V → LinearOrder V on finite type V, the number of connected components Fintype.card…

Read back from the Lean

Given a type V, a simple graph G on V, a family of linear orders π : V → LinearOrder V associating each vertex of V with a linear order on V, and vertices r, g : V, is_globally_best_outside G π r g asserts that: 1. g is not in the same connected component of G as r (i.e., G.connectedComponentMk g ≠ G.connectedComponentMk r), and 2. for all v : V, if v is not in the same connected component of G as r, then g ≤ v under the linear order π(r) (i.e., (π r).le g v).

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

/-- Vertex g is the globally best outside vertex of r if it is outside r's component and is r's most preferred outside vertex. -/
def is_globally_best_outside {V : Type*} (G : SimpleGraph V) (π : V → LinearOrder V) (r g : V) : Prop :=
  G.connectedComponentMk g ≠ G.connectedComponentMk r ∧
  ∀ v : V, G.connectedComponentMk v ≠ G.connectedComponentMk r → (π r).le g v
See it in the graphDiscuss this resultChallenge it