On the transversal number and VC-dimension of families of positive homothets of a convex body

Let FF be a family of positive homothets (or translates) of a given convex body KK in RnRn. We investigate two approaches to measuring the complexity of FF. First, we find an upper bound on the transversal number τ(F)τ(F) of FF in terms of nn and the independence number ν(F)ν(F). This question is motivated by a problem of Grünbaum [L. Danzer, B. Grünbaum, V. Klee, Helly’s theorem and its relatives, in: Proc. Sympos. Pure Math., vol. VII, Amer. Math. Soc., Providence, RI, 1963, pp. 101–180]. Our bound τ(F)≤2n(2nn)(nlogn+loglogn+5n)ν(F) is exponential in nn, an improvement from the previously known bound of Kim, Nakprasit, Pelsmajer and Skokan [S.-J. Kim, K. Nakprasit, M.J. Pelsmajer, J. Skokan, Transversal numbers of translates of a convex body, Discrete Math. 306 (18) (2006) 2166–2173], which was of order nnnn. By a lower bound, we show that the right order of magnitude is exponential in nn.Next, we consider another measure of complexity, the Vapnik–Červonenkis dimension of FF. We prove that vcdim(F)≤3vcdim(F)≤3 if n=2n=2 and is infinite for some FF if n≥3n≥3. This settles a conjecture of Grünbaum [B. Grünbaum, Venn diagrams and independent families of sets, Math. Mag. 48 (1975) 12–23]: Show that the maximum dual VC-dimension of a family of positive homothets of a given convex body KK in RnRn is n+1n+1. This conjecture was disproved by Naiman and Wynn [D.Q. Naiman, H.P. Wynn, Independent collections of translates of boxes and a conjecture due to Grünbaum, Discrete Comput. Geom. 9 (1) (1993) 101–105] who constructed a counterexample of dual VC-dimension ⌊3n2⌋. Our result implies that no upper bound exists.