Mathematics – Metric Geometry
Scientific paper
2009-07-29
Disc.Math. 310.1 (2010) 77-82
Mathematics
Metric Geometry
7 pages. 3 figures.
Scientific paper
10.1016/j.disc.2009.07.030
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/2\rfloor$. Our result implies that no upper bound exists.
NaszÓdi MÁrton
Taschuk Steven
No associations
LandOfFree
On the Transversal Number and VC-Dimension of Families of Positive Homothets of a Convex Body does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On the Transversal Number and VC-Dimension of Families of Positive Homothets of a Convex Body, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Transversal Number and VC-Dimension of Families of Positive Homothets of a Convex Body will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-468470