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

الأصل · EN

Let F be a family of positive homothets (or translates) of a given convex body K in Rⁿ. We investigate two approaches to measuring the complexity of F. First, we find an upper bound on the transversal number τ(F) of F in terms of n and the independence number ν(F). This question is motivated by a problem of Grünbaum. Our bound τ(F)≤ 2ⁿ 2nn (n n + n + 5n) ν(F) is exponential in n, an improvement from the previously known bound of Kim, Nakprasit, Pelsmajer and Skokan, which was of order 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ünbaum: Show that the maximum dual VC-dimension of a family of positive homothets of a given convex body K in Rⁿ is n+1. This conjecture was disproved by Naiman and Wynn, who constructed a counterexample of dual VC-dimension 3n/2. Our result implies that no upper bound exists.