2025/01/16 by Eleftheriou, Pantelis E., Papadopoulos, Aris, Westhead, Francis
#2020MSC. Primary: 52C35. Secondary: 03C98 #Combinatorics (math.CO) #FOS: Mathematics #Logic (math.LO)
paper · doi:10.48550/arxiv.2501.09847
The VC-dimension of a family of sets is a measure of its combinatorial complexity used in machine learning theory, computational geometry, and even model theory. Computing the VC-dimension of the k-fold union of geometric set systems has been an open and difficult combinatorial problem, dating back to Blumer, Ehrenfeucht, Haussler, and Warmuth in 1989, who ask about the VC-dimension of k-fold unions of half-spaces in ℝd. Let F1 denote the family of all lines in ℝ2. It is well-known that VC-dim(F1) = 2. In this paper, we study the 2-fold and 3-fold unions of F1, denoted F2 and F3, respectively. We show that VC-dim(F2) = 5 and VC-dim(F3) = 9. Moreover, we give complete characterisations of the subsets of ℝ2 of maximal size that can be shattered by F2 and F3, showing they are exactly two and five, respectively, up to isomorphism in the language of the point-line incidence relation.