Robust Tverberg and Colourful Carathéodory Results via Random Choice

DOI10.1017/S0963548317000591MaRDI QIDQ4635512zbMATH OpenFDO

Authors Pablo Soberón

Publication date 23 April 2018

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

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

zbMATH Keywords

probabilistic methodcolourful Carathéodory theoremTverberg's theorem with tolerance

Mathematics Subject Classification ID

Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Helly-type theorems and geometric transversal theory (52A35)

Abstract: We use the probabilistic method to obtain versions of the colorful Carath'eodory theorem and Tverberg's theorem with tolerance. In particular, we give bounds for the smallest integer $N=N(t,d,r)$ such that for any $N$ points in $R^d$, there is a partition of them into $r$ parts for which the following condition holds: after removing any $t$ points from the set, the convex hulls of what is left in each part intersect. We prove the bound $N=rt+O(sqrtt)$ for fixed $r,d$ which is polynomial in each parameters. Our bounds extend to colorful versions of Tverberg's theorem, as well as Reay-type variations of this theorem.

Recommendations

• An optimal generalization of the colorful Carathéodory theorem
• A further generalization of the colourful Carathéodory theorem
• Carathéodory-type selections and random fixed point theorems
• The coloured Tverberg theorem, extensions and new results
• scientific article; zbMATH DE number 940709
• Optimal bounds for a colorful Tverberg-Vrećica type problem
• scientific article; zbMATH DE number 4042216
• Computational aspects of the colorful Carathéodory theorem
• scientific article; zbMATH DE number 6789180
• Optimal bounds for the colored Tverberg problem

Cites work

• scientific article; zbMATH DE number 5080761 (Why is no real title available?)
• scientific article; zbMATH DE number 3541764 (Why is no real title available?)
• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• 10 points in dimension 4 not projectively equivalent to the vertices of a convex polytope
• A Colored Version of Tverberg's Theorem
• A Generalization of Radon's Theorem
• A deterministic view of random sampling and its use in geometry
• A generalisation of Tverberg's theorem
• A generalization of Caratheodory's theorem
• A note on the Tolerant Tverberg Theorem
• APPROXIMATING CENTER POINTS WITH ITERATIVE RADON POINTS
• Algorithms for tolerated Tverberg partitions
• Approximate center points with proofs
• Colourful Linear Programming and its Relatives
• Crossing Numbers and Hard Erdős Problems in Discrete Geometry
• Crossing-Free Subgraphs
• New applications of random sampling in computational geometry
• On Reay's relaxed Tverberg conjecture and generalizations of Conway's thrackle conjecture
• On Sets Projectively Equivalent to the Vertices of a Convex Polytope
• Optimal bounds for a colorful Tverberg-Vrećica type problem
• Optimal bounds for the colored Tverberg problem
• Points surrounding the origin
• Projective equivalences of \(k\)-neighbourly polytopes
• Several generalizations of Tverberg's theorem
• Some variations on Tverberg's theorem
• Tensors, colours, octahedra
• The intersection of a matroid and an oriented matroid
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Tolerance in Helly-type theorems
• Tverberg plus constraints
• Tverberg's theorem via number fields
• Very colorful theorems
• -nets and simplex range queries

Cited in

(11)

• Extensions of the colorful Helly theorem for d-collapsible and d-Leray complexes
• Stochastic Tverberg theorems with applications in multiclass logistic regression, separability, and centerpoints of data
• Tolerance for colorful Tverberg partitions
• New lower bounds for Tverberg partitions with tolerance in the plane
• A note on the Tolerant Tverberg Theorem
• Tverberg’s theorem is 50 years old: A survey
• Algorithms for Radon partitions with tolerance
• A sparse colorful polytopal KKM theorem
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
• An optimal generalization of the colorful Carathéodory theorem
• Fair distributions for more participants than allocations

This page was built for publication: Robust Tverberg and Colourful Carathéodory Results via Random Choice

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