Robust Tverberg and Colourful Carathéodory Results via Random Choice

DOI10.1017/S0963548317000591zbMATH Open1387.52012arXiv1606.08790MaRDI QIDQ4635512FDOQ4635512

Pablo Soberón

Publication date: 23 April 2018

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

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.

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

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

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)

Cites Work

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

Cited In (10)

• Tolerance for colorful Tverberg partitions
• New lower bounds for Tverberg partitions with tolerance in the plane
• Tverberg’s theorem is 50 years old: A survey
• Stochastic Tverberg Theorems With Applications in Multiclass Logistic Regression, Separability, and Centerpoints of Data
• 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
• Fair distributions for more participants than allocations
• An optimal generalization of the colorful Carathéodory theorem
• Extensions of the colorful Helly theorem for d-collapsible and d-Leray complexes

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)