simple_graph_fort_transversal_number
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
- op_979_fort_transversal_number_empty_graphFor the edgeless graph (the empty graph bot) on a finite vertex set V with decidable equality, the fort transversal number equals the…
- simple_graph_fort_transversal_number_le_all_forts_transversal_numberFor any finite simple graph G, the fort transversal number T(G) is at most the transversal number of the family of all forts of G.
- op_979_csym_max_nullity_le_fort_transversal_numberFor every finite simple graph G on a finite type V with decidable equality, the combinatorially symmetric maximum nullity N(G) is at most…
- op_979_csym_max_nullity_eq_fort_transversal_number_of_edgelessFor the edgeless graph bot on a finite vertex set V with decidable equality, the combinatorially symmetric maximum nullity equals the fort…
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 }