Shattering and finite primal and dual VC dimensions
DefinitionNearLogSetCover966_Main_Supplement_FiniteVCp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1parameterized-complexityset-cover
For a finite indexed incidence relation , a subset is shattered when
Its VC dimension is the largest shattered cardinality, with value zero when no nonempty set is shattered. Primal dimension uses the original incidence relation; dual dimension reverses its arguments. Empty universes and repeated set labels are allowed. Both dimensions are computed over actual finite subsets, so no unbounded or empty real supremum convention is involved.
Definition code
import Definitions.Def_NearLogSetCover966_Main_Supplement_Random
set_option autoImplicit false
namespace NearLogSetCover966.Main.Supplement
/-- Shattering and VC dimension on arbitrary finite indexed incidence systems.
An absent nonempty shattered set contributes dimension zero. -/
def Shatters {A E : Type} [Fintype A] [Fintype E] [DecidableEq E]
(R : A → E → Prop) (X : Finset E) : Prop :=
∀ Y ⊆ X, ∃ a, ∀ e ∈ X, R a e ↔ e ∈ Y
noncomputable def incidenceVC {A E : Type} [Fintype A] [Fintype E] [DecidableEq E]
(R : A → E → Prop) : ℕ := by
classical
exact (Finset.univ.powerset.filter (Shatters R)).sup Finset.card
def incidence (I : SCInstance) (a : Fin I.sets.length) (e : Fin I.n) : Prop := e ∈ I.sets.get a
noncomputable def primalVC (I : SCInstance) : ℕ := incidenceVC (incidence I)
noncomputable def dualVC (I : SCInstance) : ℕ := incidenceVC (fun e a => incidence I a e)
end NearLogSetCover966.Main.Supplement
Source
Bingkai Lin, Xin Zheng, STOC 2027 submission #966 (October 2026), §2.3, printed p.11 (PDF p.13)