AFTD Auto-Formalizing Theoretical Domains

simple_graph_fort_transversal_number

def

The fort transversal number T(G) of a finite simple graph G on a finite type V with decidable equality is the supremum of the transversal numbers of all compatible finite collections C of forts of G.

Statement

noncomputable def simple_graph_fort_transversal_number {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) : ℕ
Defined in
arXiv:2611.01102 Sec. 2, equation (2.3)
Verified
03 Nov 2026
Axioms
none listed
Built on 3
  • simple_graph_is_fortFor a simple graph G on an arbitrary type V, a subset F of V is a fort if F is nonempty and for every vertex v not in F, it is not the…
  • is_compatible_collectionFor an arbitrary type V with decidable equality, a finite collection C of finite subsets of V (C : Finset (Finset V)) is compatible if for…
  • finset_transversal_numberThe transversal number of a collection C of subsets of a finite set V is the minimum cardinality of a subset T of V that intersects every…
Used by 4

Read back from the Lean

Given a finite type V with decidable equality and a simple graph G on V, simple_graph_fort_transversal_number G is defined as the supremum (sSup) of the set of natural numbers k for which there exists a finite collection C of finite subsets of V (C : Finset (Finset V)) satisfying: 1. Every member F ∈ C is a fort of G (i.e., F is non-empty and no vertex v ∉ F has exactly one neighbor in F); 2. C is a compatible collection (i.e., for any two distinct sets C1, C2 ∈ C and any element x ∈ C1 ∩ C2, there exists C3 ∈ C such that C3 ⊆ (C1 ∪ C2) \ {x}); and 3. The transversal number of C is equal to k (where the transversal number of C is the infimum size of a finite subset T ⊆ V that has non-empty intersection with every set S ∈ C).

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

/-- The fort transversal number T(G) of G is the maximum transversal number of a compatible collection of forts. -/
noncomputable def simple_graph_fort_transversal_number {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) : ℕ := sSup { k : ℕ | ∃ C : Finset (Finset V),
    (∀ F ∈ C, simple_graph_is_fort G (F : Set V)) ∧ is_compatible_collection C ∧ finset_transversal_number C = k }
See it in the graphDiscuss this resultChallenge it