Greedy graph-marker set operators
DefinitionAT260939824_ClopenMarkersarxiv-2609-39824arxiv-2609-39824-positivecombinatoricslean-formalizationtopology
For a graph on , the neighbor set of consists of vertices adjacent to some point of ; independence means that no two points of are adjacent. Given sets , define
The marker set is the union of these stages. These operators isolate the set-theoretic part of the later clopen maximal-independent-set construction.
Definition code
import Init
import Mathlib.Combinatorics.SimpleGraph.Basic
import Mathlib.Order.Monotone.Basic
import Mathlib.Topology.Clopen
set_option autoImplicit false
/-!
# A clopen maximal independent set from a countable clopen independent cover
This is the maximal-independent-set part of Lemma 3.1 of
arXiv:2609.39824. The graph-neighbor operator is assumed to preserve clopen
sets, as happens for graphs generated by finitely many homeomorphisms.
The existence of the countable independent cover is a separate input.
-/
namespace AbelianTargets
universe u
variable {X : Type u} (G : SimpleGraph X)
/-- Points adjacent to some point of a set. The order of the adjacency
arguments is immaterial for a simple graph, but is fixed here for witnesses. -/
def NeighborSet (S : Set X) : Set X := {y | ∃ x ∈ S, G.Adj x y}
/-- A set of vertices containing no pair of adjacent points. -/
def GraphIndependent (S : Set X) : Prop :=
∀ x ∈ S, ∀ y ∈ S, ¬ G.Adj x y
/-- The accumulated greedy independent sets. At stage `n`, every point of
the `n`th cover set not adjacent to an earlier choice is added. -/
def markerAccumulation (C : ℕ → Set X) : ℕ → Set X
| 0 => ∅
| n + 1 => markerAccumulation C n ∪ (C n \ NeighborSet G (markerAccumulation C n))
/-- The union of all greedy stages. -/
def maximalMarkerSet (C : ℕ → Set X) : Set X := ⋃ n, markerAccumulation G C n
variable {G}
@[simp] theorem markerAccumulation_zero (C : ℕ → Set X) :
markerAccumulation G C 0 = ∅ := rfl
@[simp] theorem markerAccumulation_succ (C : ℕ → Set X) (n : ℕ) :
markerAccumulation G C (n + 1) =
markerAccumulation G C n ∪ (C n \ NeighborSet G (markerAccumulation G C n)) := rfl
variable [TopologicalSpace X]
end AbelianTargets
Source
Ruijun Wang, Continuous graph homomorphisms of higher dimensional abelian group actions, arXiv:2609.39824v1 (2026), Section(s) 3; https://arxiv.org/abs/2609.39824v1. This item is auxiliary infrastructure of the accompanying formalization, not a claim that each implementation definition is separately numbered in the paper. Original Lean module AbelianTargets/ClopenMarkers.lean, selected declaration lines 19-21, 23-25, 27-31, 33-34, 38-39, 41-43; SHA-256 7555b61d55257a699bdb418732869ed00680e5f483d1794d31b47ef023996b17. Selected spans are from the final generated manifest. The original source snapshot is local; no public repository URL or commit was available.