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

DOI10.1016/J.DISC.2009.07.030zbMATH Open1192.52006arXiv0907.5223OpenAlexW2160761829MaRDI QIDQ1045145FDOQ1045145

Authors: Márton Naszódi, Steven Taschuk 

Publication date: 15 December 2009

Published in: Discrete Mathematics (Search for Journal in Brave)

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 $au(F)$ of F in terms of $n$ and the independence number $u(F)$. This question is motivated by a problem of Gr"unbaum. Our bound $$ 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 $lfloor3n/2floor$. Our result implies that no upper bound exists.

Full work available at URL: https://arxiv.org/abs/0907.5223

Recommendations

• Transversal numbers of translates of a convex body
• Piercing Translates and Homothets of a Convex Body
• Piercing translates and homothets of a convex body
• scientific article; zbMATH DE number 1342017
• scientific article; zbMATH DE number 970814

zbMATH Keywords

VC-dimensiontransversal numberhomothetstranslates of a convex set

Mathematics Subject Classification ID

Convex sets in (n) dimensions (including convex hypersurfaces) (52A20) Inequalities and extremum problems involving convexity in convex geometry (52A40)

Cites Work

• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• The difference body of a convex body
• \(\epsilon\)-nets and simplex range queries
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Venn Diagrams and Independent Families of Sets
• Bounded VC-dimension implies a fractional Helly theorem
• A note on coverings
• Covering convex bodies by translates of convex bodies
• Title not available (Why is that?)
• Transversal numbers of translates of a convex body
• Strictly antipodal sets
• No Helly theorem for stabbing translates by lines in \(\mathbb{R}^3\)
• Transversals for families of translates of a two-dimensional convex compact set
• Title not available (Why is that?)
• Independent collections of translates of boxes and a conjecture due to Grünbaum

Cited In (7)

• Piercing Translates and Homothets of a Convex Body
• Improved bounds for the expected number of \(k\)-sets
• Transversal numbers of translates of a convex body
• On non-separable families of positive homothetic convex bodies
• Piercing translates and homothets of a convex body
• On a problem by Dol'nikov
• Ball and spindle convexity with respect to a convex body

This page was built for publication: On the transversal number and VC-dimension of families of positive homothets of a convex body

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1045145)