finset_transversal_number
def
The 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 set S in C.
Statement
noncomputable def finset_transversal_number {V : Type*} [Fintype V] [DecidableEq V] (C : Finset (Finset V)) : ℕ
- Defined in
- arXiv:2611.01102 Sec. 2, line 138
- Verified
- 03 Nov 2026
- Axioms
- none listed
- Used by 5
- 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…
- finset_transversal_number_monoFor any two finite collections C1 ⊆ C2 of nonempty subsets of a finite set V, the transversal number of C1 is at most the transversal…
- 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…
- simple_graph_fort_transversal_numberThe 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…
Read back from the Lean
For a finite type V with decidable equality, and a finite collection of finite subsets of V, C : Finset (Finset V), finset_transversal_number C is defined as the infimum (sInf) in ℕ of the set of natural numbers k such that there exists a finite subset T : Finset V of cardinality k with the property that for every S ∈ C, T ∩ S is nonempty (i.e., T is a transversal / hitting set of 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 transversal number of a collection of subsets is the minimum cardinality of a set intersecting each member. -/ noncomputable def finset_transversal_number {V : Type*} [Fintype V] [DecidableEq V] (C : Finset (Finset V)) : ℕ := sInf { k : ℕ | ∃ T : Finset V, (∀ S ∈ C, (T ∩ S).Nonempty) ∧ T.card = k }