Theorems of Carathéodory, Helly, and Tverberg without dimension

DOI10.1007/S00454-020-00172-5MaRDI QIDQ2197682zbMATH OpenOpenAlexFDO

Authors Karim Adiprasito, Nabil H. Mustafa, Tamás Terpai, Imre Bárány

Publication date 1 September 2020

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

Tverberg theoremconvex approximationCarathéodory theorem

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Convex sets in (n) dimensions (including convex hypersurfaces) (52A20) Helly-type theorems and geometric transversal theory (52A35)

Abstract: We prove a no-dimensional version of Carath'edory's theorem: given an $n$-element set $PsubsetR{e}^d$, a point $ainconvP$, and an integer $rled$, $rlen$, there is a subset $QsubsetP$ of $r$ elements such that the distance between $a$ and $convQ$ is less than $diamP/sqrt2r$. A general no-dimension Helly type result is also proved with colourful and fractional consequences. Similar versions of Tverberg's theorem and some of their extensions are also established.

Recommendations

• Theorems of Carathéodory, Helly, and Tverberg without dimension
• scientific article; zbMATH DE number 480237
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
• On Bárány's theorems of Carathéodory and Helly type
• On a theorem of cartwright in higher dimensions
• On the Two “Dimension Theorems”
• \(n\)-distributivity, dimension and Carathéodory's theorem
• scientific article; zbMATH DE number 1567901
• scientific article; zbMATH DE number 4060005
• scientific article; zbMATH DE number 3957550

Cites work

• scientific article; zbMATH DE number 3772326 (Why is no real title available?)
• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• A Generalization of Radon's Theorem
• A Problem of Geometry in R n
• A Theorem on General Measure
• A generalization of Caratheodory's theorem
• A note on the colorful fractional Helly theorem
• Approximating Nash equilibria and dense bipartite subgraphs via an approximate version of Carathéodory's theorem
• Approximation of points of the convex hull of a sum of sets by points of the sum: an elementary approach
• Colourful and fractional \((p,q)\)-theorems
• Computing the volume is difficult
• Concentration phenomena in high dimensional geometry
• Concentration property on probability spaces.
• Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm
• Gelfand numbers of operators with values in a Hilbert space
• Inequalities of Bernstein-Jackson-type and the degree of compactness of operators in Banach spaces
• Intersection patterns of convex sets
• Measures of the non-convexity of sets and the Shapley–Folkman–Starr theorem
• On Bárány's theorems of Carathéodory and Helly type
• Optimal bounds for the colored Tverberg problem
• Piercing convex sets and the Hadwiger-Debrunner \((p,q)\)-problem
• Point Selections and Weak ε-Nets for Convex Hulls
• Points surrounding the origin
• Quasi-Equilibria in Markets with Non-Convex Preferences
• Sparse approximation via generating point sets
• The approximate rank of a matrix and its algorithmic applications
• The colored Tverberg's problem and complexes of injective functions
• The convexification effect of Minkowski summation
• Very colorful theorems
• Über eine Variante zum Hellyschen Satz

Cited in

(12)

• A quantitative version of Carathéodory's theorem for convex sets
• The Oka-Grauert principle without induction over the base dimension
• An even tighter bound for the Shapley-Folkman-Starr theorem
• Measuring the convexity of compact sumsets with the Schneider non-convexity index
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
• scientific article; zbMATH DE number 480237 (Why is no real title available?)
• No-dimensional Tverberg partitions revisited
• No-dimension Tverberg's theorem and its corollaries in Banach spaces of type \(P\)
• No-dimensional piercing of convex sets
• Efficient certifying algorithms for linear classification
• Theorems of Carathéodory, Helly, and Tverberg without dimension
• A mélange of diameter Helly-type theorems

This page was built for publication: Theorems of Carathéodory, Helly, and Tverberg without dimension

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