On weak -nets and the Radon number
The main results of this paper involve a finite set \(X\), a family \(C\) of subsets of \(X\) and probability measures \(\mu\) on \(X\). The family \(C\) is said to have a weak \(\epsilon\)-net of size \(\beta\) over \(\mu\) if there exists a subset \(S\) of \(X\) of size \(\beta\) whose intersection with every member of \(C\) that has the \(\mu\)-measure at least \(\epsilon\) is non-empty. The pair \((X,C)\) is called a convexity space if \(C\) is closed under intersections and both the empty sets and the whole \(X\) are elements of \(C\). In this case, sets from \(C\) are said to be convex sets of the convexity space \((X,C)\). The convex hull \(\mathrm{conv }Y\) of a subset \(Y\) of \(X\) in the convexity space \((X,C)\) is defined as the intersection of all elements of \(C\) that contain \(A\) as a subset. A convexity space \((X,C)\) is called separable if for every convex set \(Y\in C\) and a point \(p\in X\setminus Y\) there exists a partition of \(X\) into convex sets \(X_1\in C\) and \(X_2\in C\) that satisfies \(Y\subseteq X_1\) and \(p\in X_2\). The Radon number of a convexity space \((X,C)\) is the minimal number \(r\) with the property that every subset \(Y\) of \(X\) with \(r\) elements can be partitioned into sets \(Y_1\) and \(Y_2\) whose convex hulls have a non-empty intersection. The main theorem of this paper is about the interplay of the Radon number and the size of weak \(\epsilon\)-nets for \(X\). The theorem states that for a finite convexity space \((X,C)\) the following assertions hold: \begin{itemize} \item[(a)] if \((X,C)\) is separable and has Radon number at most \(r\), then, for every \(\epsilon>0\) and every probability measure \(\mu\) on \(X\), the family \(C\) has a weak \(\epsilon\)-net over \(\mu\) of size at most \((120 r^2/\epsilon) ^{4 r^2\ln(1/\epsilon)}\) \item[(b)] If \((X,C)\) has Radon number at least \(r\), then for some choice of a probability measure \(\mu\) on \(X\), every 1/4-net for \(C\) over \(\mu\) has size at least \(r/2\). \end{itemize} The authors mention that meanwhile Holmsen and Lee (2019) have derived an upper bound on the size of the weak \(\epsilon\)-net of finite convexity spaces \((X,C)\) without any use of the separability assumption on \((X,C)\).
- -nets and simplex range queries
- A lower bound for weak \(\varepsilon\)-nets in high dimension
- A non-linear lower bound for planar epsilon-nets
- A note about weak -nets for axis-parallel boxes in d-space
- Axiomatic convexity theory and relationships between the Carathéodory, Helly, and Radon numbers
- Families of Non-disjoint subsets
- scientific article; zbMATH DE number 439012 (Why is no real title available?)
- scientific article; zbMATH DE number 5764800 (Why is no real title available?)
- scientific article; zbMATH DE number 3214278 (Why is no real title available?)
- scientific article; zbMATH DE number 3243116 (Why is no real title available?)
- scientific article; zbMATH DE number 3068278 (Why is no real title available?)
- Improved bounds on weak \(\varepsilon\)-nets for convex sets
- Kneser's conjecture, chromatic number, and homotopy
- Learnability and the Vapnik-Chervonenkis dimension
- Maximal convex sets
- On Components in Some Families of Sets
- On the Geometry and Computational Complexity of Radon Partitions in the Iinteger Lattice
- On the number of halving planes
- Piercing convex sets and the Hadwiger-Debrunner \((p,q)\)-problem
- Point Selections and Weak ε-Nets for Convex Hulls
- Separation of two convex sets in convexity structures
- Some special Vapnik-Chervonenkis classes
- Sphere packing numbers for subsets of the Boolean \(n\)-cube with bounded Vapnik-Chervonenkis dimension
- The probabilistic method. With an appendix on the life and work of Paul Erdős.
- The structure of semispaces
- Transversal numbers for hypergraphs arising in geometry
- Understanding machine learning. From theory to algorithms
- Über eine Variante zum Hellyschen Satz
- Weak -nets for points on a hypersphere
- Radon numbers and the fractional Helly theorem
- Radon numbers grow linearly
- Weak ε-nets and interval chains
- A note about weak -nets for axis-parallel boxes in d-space
- On weak -nets and the Radon number
- scientific article; zbMATH DE number 4182248 (Why is no real title available?)
- Helly-type problems
- First-order logic axiomatization of metric graph theory
- Discrete geometry. Abstracts from the workshop held January 21--26, 2024
- Some new results on geometric transversals
- Bounding Radon numbers via Betti numbers
- An ( _0, k + 2)-theorem for k-transversals
This page was built for publication: On weak \(\epsilon\)-nets and the Radon number
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2223615)
