On the Transversal Number and VC-Dimension of Families of Positive Homothets of a Convex Body

Let F be a family of positive homothets (or translates) of a given convex body K in R^n. We investigate two approaches to measuring the complexity of F. First, we find an upper bound on the transversal number $\tau (F)$ of F in terms of $n$ and the independence number $\nu (F)$. This question is motivated by a problem of Gr"unbaum. Our bound $\tau(F)\le 2^n \binom{2n}{n} (n \log n + \log\log n + 5n) \nu(F)$ is exponential in n, an improvement from the previously known bound of Kim, Nakprasit, Pelsmajer and Skokan, which was of order n^n. By a lower bound, we show that the right order of magnitude is exponential in n. Next, we consider another measure of complexity, the Vapnik–Chervonenkis dimension of F. We prove that this quantity is at most 3 if n=2 and is infinite for some F if n>2. This settles a conjecture of G"unbaum: Show that the maximum dual VC-dimension of a family of positive homothets of a given convex body K in R^n is n+1. This conjecture was disproved by Naiman and Wynn, who constructed a counterexample of dual VC-dimension $\lfloor 3n\mathrm{/}2\rfloor$. Our result implies that no upper bound exists.