Radon numbers and the fractional Helly theorem
A convexity space is a pair \((X, \mathcal{C})\), where \(X\) is a non-empty set and \(\mathcal{C}\) is a family of subsets of \(X\) satisfying the following conditions: (i) \(\emptyset, X \in \mathcal{C}\); (ii) if \(\mathcal{D} \subset \mathcal{C}\) is non-empty, then \(\bigcap_{C \in \mathcal{D}} C \in \mathcal{C}\); (iii) if \(\mathcal{D} \subset \mathcal{C}\) is non-empty and totally ordered by inclusion, then \(\bigcup_{C \in \mathcal{D}} C \in \mathcal{C}\). The members of \(\mathcal{C }\) are called convex sets. Given a subset \(Y \subset X\), the convex hull of \(Y\), denoted by \(\operatorname{conv}(Y )\), is the intersection of all convex sets containing \(Y\). The Radon number of \(X\) is the smallest integer \(r_2\) (if it exists) such that any subset \(P \subset X\) with \(|r_2| \geq 2\) can be partitioned into two parts \(P_1\) and \(P_2\) such that \(\operatorname{conv}(P_1 )\cap \operatorname{conv}(P_2 )\neq \emptyset\). The following fractional Helly theorem for convexity spaces with bounded Radon number is the main result of the paper. For every \(r \geq 3\) and \(\alpha \in (0, 1)\) there exists an \(m = m(r)\) and a \(\beta = \beta(\alpha, r)\) with the following property: Let \(F\) be a finite family of \(n \geq m\) convex sets in a convexity space with Radon number at most \(r\). If at least \(\alpha \binom nm\) of the \(m\)-tuples of \(F\) have non-empty intersection, then there are at least \(\beta n\) members of \(F\) whose intersection is non-empty. As a consequence, a weak \(\varepsilon\)-net theorem for convexity spaces with bounded Radon number is obtained.
- -nets and simplex range queries
- A fractional Helly theorem for convex lattice sets
- A generalization of Caratheodory's theorem
- A Generalization of Radon's Theorem
- A Problem of Geometry in R n
- A topological colorful Helly theorem
- An upper-bound theorem for families of convex sets
- Beyond the Borsuk–Ulam Theorem: The Topological Tverberg Story
- Bounded VC-dimension implies a fractional Helly theorem
- Bounding the piercing number
- Colourful Linear Programming and its Relatives
- Helly’s theorem: New variations and applications
- scientific article; zbMATH DE number 439012 (Why is no real title available?)
- scientific article; zbMATH DE number 6016068 (Why is no real title available?)
- scientific article; zbMATH DE number 480237 (Why is no real title available?)
- scientific article; zbMATH DE number 1749054 (Why is no real title available?)
- scientific article; zbMATH DE number 2209723 (Why is no real title available?)
- scientific article; zbMATH DE number 3068278 (Why is no real title available?)
- Improved bounds on weak ε-nets for convex sets
- Intersection patterns of convex sets
- Large cliques in \(C_4\)-free graphs
- Large cliques in hypergraphs with forbidden substructures
- On stirling numbers of the second kind
- On weak \(\epsilon\)-nets and the Radon number
- Partition numbers for trees and ordered sets
- Piercing convex sets and the Hadwiger-Debrunner \((p,q)\)-problem
- Point Selections and Weak ε-Nets for Convex Hulls
- The colorful Helly theorem and colorful resolutions of ideals
- The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
- The partition conjecture
- Transversal numbers for hypergraphs arising in geometry
- Tverberg's theorem via number fields
- Tverberg’s theorem is 50 years old: A survey
- Bounded VC-dimension implies a fractional Helly theorem
- Colorful Carathéodory, Helly and sierksma numbers of convexity spaces
- On weak \(\epsilon\)-nets and the Radon number
- Radon numbers grow linearly
- Generalised Helly and Radon numbers
- On the Geometry and Computational Complexity of Radon Partitions in the Iinteger Lattice
- On weak -nets and the Radon number
- Radon and Helly numbers of segment spaces
- scientific article; zbMATH DE number 4182248 (Why is no real title available?)
- Helly-type problems
- Combinatorial properties of nonarchimedean convex sets
- Bounding Radon number via Betti numbers
- Fractional Helly theorem for Cartesian products of convex sets
- Embeddings of k-complexes into 2k-manifolds
- Discrete geometry. Abstracts from the workshop held January 21--26, 2024
- Some new results on geometric transversals
- Bounding Radon numbers via Betti numbers
- Orientation of convex sets
- Colorful two-piercing theorem for boxes
- An ( _0, k + 2)-theorem for k-transversals
- A sharper Ramsey theorem for constrained drawings
- Intersection patterns in spaces with a forbidden homological minor
- A note on smaller fractional Helly numbers
This page was built for publication: Radon numbers and the fractional Helly theorem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2022784)
