VC-saturated set systems. (August 2022)

• Record Type: Journal Article
• Authors: Frankl, Nóra; Kiselev, Sergei; Kupavskii, Andrey; Patkós, Balázs
• Is Part Of: European journal of combinatorics. Volume 104(2022)
• Publication Date: 2022-08
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2022.103528
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: The well-known Sauer lemma states that a family F ⊆ 2 [ n ] of VC-dimension at most d has size at most ∑ i = 0 d n i . We obtain both random and explicit constructions to prove that the corresponding saturation number, i.e., the size of the smallest maximal family with VC-dimension d ≥ 2, is at most 4 d + 1, and thus is independent of n .