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

DOI10.1016/J.DISC.2009.07.030MaRDI QIDQ1045145zbMATH OpenOpenAlexFDO

Authors Márton Naszódi, Steven Taschuk

Publication date 15 December 2009

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

homothetstranslates of a convex settransversal numberVC-dimension

Mathematics Subject Classification ID

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

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.

Review text

Let \(\mathcal{F}\) be a family of positive homothets (or translates) of a given convex body \(K\) in \(\mathbb{R}^n\). The authors investigate two approaches to measuring of complexity of \(\mathcal{F}\). In particular, they present an upper bound on the transversal number \(\tau(\mathcal{F})\) of \(\mathcal{F}\) in terms of \(n\) and the independence number \(\nu(\mathcal{F})\). The second main result of the paper under review is related to another measure of complexity, the Vapnik-Červonenkis dimension (VC-dimension) of \(\mathcal{F}\). Namely, it is proved that \(vcdim(\mathcal{F})\leq 3\) if \(n=2\) and is infinite for some \(\mathcal{F}\) if \(n \geq 3\).

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

Cites work

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

Cited in

(10)

• Ball and spindle convexity with respect to a convex body
• On a problem by Dol'nikov
• 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 the VC-dimension of half-spaces with respect to convex sets
• scientific article; zbMATH DE number 970814 (Why is no real title available?)
• Improved bounds for the expected number of k-sets
• Piercing translates and homothets of a convex body
• Transversals to colorful intersecting convex sets

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)