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

preprint2010arXivOpen access

Abstract

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 τ(F)τ(F) of F in terms of nn and the independence number ν(F)ν(F). This question is motivated by a problem of Grünbaum. Our bound τ(F)≤2n(2nn)(nlog⁡n+log⁡log⁡n+5n)ν(F)τ(F)\le 2^n \binom{2n}{n} (n \log n + \log\log 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^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^n is n+1. This conjecture was disproved by Naiman and Wynn, who constructed a counterexample of dual VC-dimension ⌊3n/2⌋\lfloor 3n/2\rfloor. Our result implies that no upper bound exists.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.