On the transversal number and VC-dimension of families of positive homothets of a convex body (Q1045145): Difference between revisions

Let \(\mathcal{F}\) be a family of positive homothets (or translates) of a given convex body \(K\) in \(\mathbb{R}^n\). The authors investigate two approaches to measuring of complexity of \(\mathcal{F}\). In particular, they present an upper bound on the transversal number \(\tau(\mathcal{F})\) of \(\mathcal{F}\) in terms of \(n\) and the independence number \(\nu(\mathcal{F})\). The second main result of the paper under review is related to another measure of complexity, the Vapnik-Červonenkis dimension (VC-dimension) of \(\mathcal{F}\). Namely, it is proved that \(vcdim(\mathcal{F})\leq 3\) if \(n=2\) and is infinite for some \(\mathcal{F}\) if \(n \geq 3\).