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

2018/06/22 by Adiprasito, Karim, Bárány, Imre, Mustafa, Nabil H. +1 · 2 citations
#Combinatorics (math.CO) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics #Metric Geometry (math.MG) #Probability (math.PR)

paper · doi:10.48550/arxiv.1806.08725

Abstract

We prove a no-dimensional version of Carathédory's theorem: given an n-element set P⊂ \Re^d, a point a ∈ \conv P, and an integer r≤ d, r ≤ n, there is a subset Q⊂ P of r elements such that the distance between a and \conv Q is less than \diam P/√ 2r. 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.

Cited by

• Quantum error correction beyond SU(2): spin, bosonic, and permutation-invariant codes from convex geometry
• No-dimensional Tverberg-type problems

Related

• A remark on sets with few distances in ℝ^d
• Caratheodory's Theorem in Depth
• Helly theorem for affine spaces without dimensions
• Bounding the Dimension of Points on a Line
• Distances in sparse sets of large Hausdorff dimension