The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
From MaRDI portal
Publication:5241224
DOI10.1090/bull/1653zbMath1460.52010arXiv1706.05975OpenAlexW2963628493MaRDI QIDQ5241224
Frédéric Meunier, Nabil H. Mustafa, Xavier Goaoc, Jesús A. De Loera
Publication date: 30 October 2019
Published in: Bulletin of the American Mathematical Society (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1706.05975
Convex programming (90C25) Applications of game theory (91A80) General low-dimensional topology (57M99) Helly-type theorems and geometric transversal theory (52A35)
Related Items
Isometric and affine copies of a set in volumetric Helly results, Stochastic Tverberg Theorems With Applications in Multiclass Logistic Regression, Separability, and Centerpoints of Data, Tolerance for colorful Tverberg partitions, A survey of mass partitions, Combinatorial properties of nonarchimedean convex sets, RELATIVE LERAY NUMBERS VIA SPECTRAL SEQUENCES, Inscribed Tverberg‐type partitions for orbit polytopes, Matching points with disks with a common intersection, New lower bounds for Tverberg partitions with tolerance in the plane, Colorful Helly-type theorems for the volume of intersections of convex bodies, Regular polygonal partitions of a Tverberg type, Quantitative fractional Helly and \((p,q)\)-theorems, Intermediate value theorem for simplices for simplicial approximation of fixed points and zeros, Algorithms for Radon partitions with tolerance, Different versions of the nerve theorem and colourful simplices, A Tverberg type theorem for collectively unavoidable complexes, Radon numbers and the fractional Helly theorem, Tverberg’s theorem is 50 years old: A survey, Function and colorful extensions of the KKM theorem, Envy-free cake division without assuming the players prefer nonempty pieces, Quantitative combinatorial geometry for concave functions, Optimal ℓ 1 Rank One Matrix Decomposition, Tverberg theorems over discrete sets of points, The complexity of finding fair independent sets in cycles, A type of algebraic structure related to sets of intervals, Combinatorial convexity in Hadamard manifolds: existence for equilibrium problems, The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich, No-dimensional Tverberg theorems and algorithms, Helly-type problems, Functional John ellipsoids
Uses Software
Cites Work
- Bisection of Circle Colorings
- Graph minor theory
- The Linear Complementarity Problem
- ETR-Completeness for Decision Versions of Multi-player (Symmetric) Nash Equilibria
- Settling the complexity of computing two-player Nash equilibria
- k-Centerpoints Conjectures for Pointsets in ℝd
- The LSB Theorem Implies the KKM Lemma
- Dual theorems on central points and their generalizations
- Topological methods in combinatorial geometry
- Simple proofs of some Borsuk-Ulam results
- On a notion of simplicial depth
- How to Cut A Cake Fairly
- A Problem of Geometry in R n
- How to Cut a Cake Fairly
- On a common generalization of Borsuk's and Radon's theorem
- The Game of Hex and the Brouwer Fixed-Point Theorem
- On a Topological Generalization of a Theorem of Tverberg
- Polynomial algorithms in linear programming
- Graphes Noyau-Parfaits
- A generalization of Radon's theorem II
- On the Geometry and Computational Complexity of Radon Partitions in the Iinteger Lattice
- A Colored Version of Tverberg's Theorem
- On the foundations of linear and integer linear programming I
- An observation on the structure of production sets with indivisibilities
- A Theorem Concerning the Integer Lattice
- Theoretical Properties of the Network Simplex Method
- A counterexample to an integer analogue of Carathéodory's theorem
- Point Selections and Weak ε-Nets for Convex Hulls
- Colourful Linear Programming and its Relatives
- Las Vegas algorithms for linear and integer programming when the dimension is small
- Algorithm AS 307: Bivariate Location Depth
- Regression Depth
- Sparse Approximation via Generating Point Sets
- Improved Deterministic Algorithms for Linear Programming in Low Dimensions
- The Rainbow at the End of the Line — A PPAD Formulation of the Colorful Carathéodory Theorem with Applications
- The Support of Integer Optimal Solutions
- Topology of the Grünbaum–Hadwiger–Ramos hyperplane mass partition problem
- Gerrymandering, Sandwiches, and Topology
- A Lower Bound Technique for Triangulations of Simplotopes
- Sublinear Bounds for a Quantitative Doignon--Bell--Scarf Theorem
- Beyond the Borsuk–Ulam Theorem: The Topological Tverberg Story
- Bounding Helly Numbers via Betti Numbers
- Sperner’s Colorings and Optimal Partitioning of the Simplex
- Thieves can make sandwiches
- Fair Division and Generalizations of Sperner- and KKM-type Results
- Beyond Chance-Constrained Convex Mixed-Integer Optimization: A Generalized Calafiore-Campi Algorithm and the notion of $S$-optimization
- Achieving Rental Harmony with a Secretive Roommate
- Robust Tverberg and Colourful Carathéodory Results via Random Choice
- Eliminating Tverberg Points, I. An Analogue of the Whitney Trick
- Tverberg’s theorem is 50 years old: A survey
- The Borsuk-Ulam Theorem and Bisection of Necklaces
- Quantitative Helly-Type Theorems
- Algorithmic Solutions for Envy-Free Cake Cutting
- <em>N</em>-Person Cake-Cutting: There May Be No Perfect Division
- Further Consequences of the Colorful Helly Hypothesis
- The complexity of splitting necklaces and bisecting ham sandwiches
- Consensus halving is PPA-complete
- Theorems of Carathéodory, Helly, and Tverberg without dimension
- Improved bounds on weak ε-nets for convex sets
- On the Multichromatic Number of s‐Stable Kneser Graphs
- The Scenario Approach to Robust Control Design
- TFNP: An Update
- A New Triangulation for Simplicial Algorithms
- Convex and Discrete Geometry
- Economics and computation. An introduction to algorithmic game theory, computational social choice, and fair division
- Hyperplane mass partitions via relative equivariant obstruction theory
- On a lower bound for the connectivity of the independence complex of a graph
- A simpler proof of the Boros-Füredi-Bárány-Pach-Gromov theorem
- A generalisation of Tverberg's theorem
- A new lower bound based on Gromov's method of selecting heavily covered points
- The colourful simplicial depth conjecture
- On the Erdős distinct distances problem in the plane
- On the chromatic number of general Kneser hypergraphs
- An exponential lower bound for Cunningham's rule
- Colorful subhypergraphs in uniform hypergraphs
- Quantitative combinatorial geometry for continuous parameters
- Quantitative Helly-type theorem for the diameter of convex sets
- Fixed points, Nash equilibria, and the existential theory of the reals
- Lower bounds for weak epsilon-nets and stair-convexity
- The chromatic number of almost stable Kneser hypergraphs
- A computational approach to Conway's thrackle conjecture
- Total dual integrality and integer polyhedra
- Hitting simplices with points in \(\mathbb R^{3}\)
- Tverberg-type theorems for intersecting by rays
- Optimal bounds for a colorful Tverberg-Vrećica type problem
- Oja centers and centers of gravity
- A topological colorful Helly theorem
- Singularities, expanders and topology of maps. II: From combinatorics to topology via algebraic isoperimetry
- Group actions and Helly's theorem
- On Gromov's method of selecting heavily covered points
- A note on smaller fractional Helly numbers
- Kneser's conjecture, chromatic number, and homotopy
- A new polynomial-time algorithm for linear programming
- Intersection patterns of convex sets
- Polyhedra with the integer Carathéodory property
- Constructive proof of the min-max theorem
- On kernels and semikernels of digraphs
- Equilibrium in a discrete exchange economy with money
- Extremal problems in discrete geometry
- Games of fixed rank: a hierarchy of bimatrix games
- Stabbing simplices by points and flats
- Understanding and using linear programming
- On the number of Tverberg partitions in the prime power case
- Sperner labellings: A combinatorial approach
- The clique complex and hypergraph matching
- An optimal generalization of the colorful Carathéodory theorem
- The intersection of a matroid and an oriented matroid
- Combinatorial complexity bounds for arrangements of curves and spheres
- An optimal extension of the centerpoint theorem
- Using volume to prove Sperner's Lemma
- Efficient algorithms for maximum regression depth
- Violator spaces: Structure and algorithms
- A note on kernels and Sperner's Lemma
- Triangulations. Structures for algorithms and applications
- Nonlinear discrete optimization. An algorithmic theory
- Combinatorial Stokes formulas via minimal resolutions
- On the number of Birch partitions
- Envy-free cake divisions cannot be found by finite protocols
- On the complexity of 2D discrete fixed point problem
- Hitting sets when the VC-dimension is small
- Points surrounding the origin
- Descriptive statistics for multivariate distributions
- Inequalities of Bernstein-Jackson-type and the degree of compactness of operators in Banach spaces
- An upper-bound theorem for families of convex sets
- An integer analogue of Carathéodory's theorem
- The number of triangles covering the center of an \(n\)-set
- \(\epsilon\)-nets and simplex range queries
- NP-completeness of the linear complementarity problem
- Splitting necklaces
- Perfect graphs are kernel solvable
- Decomposition of regular matroids
- A constructive proof of Tucker's combinatorial lemma
- Dividing a cake fairly
- A generalization of Caratheodory's theorem
- Une généralisation du théorème de Richardson sur l'existence de noyaux dans les graphes orientes
- Small-dimensional linear programming and convex hulls made easy
- Nash and correlated equilibria: Some complexity considerations
- Efficient partition trees
- The colored Tverberg's problem and complexes of injective functions
- Geometric medians
- Piercing convex sets and the Hadwiger-Debrunner \((p,q)\)-problem
- Cutting hyperplanes for divide-and-conquer
- n-tuple colorings and associated graphs
- Subjectivity and correlation in randomized strategies
- Transversals of latin squares and their generalizations
- On generalizations of Radon's theorem and the Ham sandwich theorem
- The combinatorics of timetabling
- On the complexity of the parity argument and other inefficient proofs of existence
- Algorithms for ham-sandwich cuts
- Helly-type theorems and generalized linear programming
- Computing a centerpoint of a finite planar set of points in linear time
- On a topological generalization of the Tverberg theorem
- Fractional kernels in digraphs
- Algorithms for bivariate medians and a Fermat-Torricelli problem for lines.
- Domination numbers and homology
- The best constant in Siegel's Lemma
- The Radon number of the three-dimensional integer lattice
- The complexity of hyperplane depth in the plane
- A partitioned version of the Erdős-Szekeres theorem for quadrilaterals
- The partition conjecture
- Mathematical problems for the next century
- Generalized Kneser coloring theorems with combinatorial proofs
- Hyperplane equipartitions plus constraints
- On Reay's relaxed Tverberg conjecture and generalizations of Conway's thrackle conjecture
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Polynomial partitioning for several sets of varieties
- KKM type theorems with boundary conditions
- Helly numbers of algebraic subsets of \(\mathbb{R}^{d}\) and an extension of Doignon's theorem
- Colorful linear programming, Nash equilibrium, and pivots
- A simple proof of optimal epsilon nets
- Optimality certificates for convex minimization and Helly numbers
- A quantitative Doignon-Bell-Scarf theorem
- New constructions of weak \(\varepsilon\)-nets
- Topological lower bounds for the chromatic number: a hierarchy
- Uncertain convex programs: randomized solutions and confidence levels
- Note on a conjecture of Sierksma
- Tverberg's theorem via number fields
- Consensus-halving via theorems of Borsuk-Ulam and Tucker
- New lower bounds for Hopcroft's problem
- New applications of random sampling in computational geometry
- Applications of random sampling in computational geometry. II
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Transversal numbers for hypergraphs arising in geometry
- A polytopal generalization of Sperner's lemma
- A fractional Helly theorem for convex lattice sets
- On depth and deep points: A calculus.
- Bounded VC-dimension implies a fractional Helly theorem
- A combinatorical proof of Kneser's conjecture
- A condition for matchability in hypergraphs
- Almost optimal set covers in finite VC-dimension
- A subexponential bound for linear programming
- The equivalence of linear programs and zero-sum games
- Oriented matroids and Ky Fan's theorem
- Implementation of a unimodularity test
- Regression depth and center points.
- Tverberg plus minus
- Barycenters of polytope skeleta and counterexamples to the topological Tverberg conjecture, via constraints
- 2-D Tucker is PPA complete
- Quantitative \((p, q)\) theorems in combinatorial geometry
- Extensions of Sperner and Tucker's lemma for manifolds
- Two-player envy-free multi-cake division
- Envy-free cake division without assuming the players prefer nonempty pieces
- Colorful coverings of polytopes and piercing numbers of colorful \(d\)-intervals
- Optimal bounds for the colored Tverberg problem
- Strengthening topological colorful results for graphs
- Tight bounds on discrete quantitative Helly numbers
- Combinatorial necklace splitting
- Very colorful theorems
- Fair splitting of colored paths
- Quantitative Tverberg theorems over lattices and other discrete sets
- A note on the Tolerant Tverberg Theorem
- Splitting multidimensional necklaces
- A course in topological combinatorics
- Helly numbers of acyclic families
- A proof of the Oja depth conjecture in the plane
- Envy-free two-player \(m\)-cake and three-player two-cake divisions
- Independent systems of representatives in weighted graphs
- Weak \(\varepsilon \)-nets have basis of size \(O(1/\varepsilon\log (1/\varepsilon))\) in any dimension
- Carathéodory bounds for integer cones
- Colourful simplicial depth
- A point in many triangles
- A point in an \(nd\)-polytope is the barycenter of \(n\) points in its \(d\)-faces
- Axiomatic convexity theory and relationships between the Carathéodory, Helly, and Radon numbers
- Normal hypergraphs and the perfect graph conjecture
- Convexity in cristallographical lattices
- A constructive proof of Ky Fan's generalization of Tucker's lemma
- The topological Tverberg theorem and winding numbers
- Homotopy invariants of covers and KKM-type lemmas
- Non-cooperative games
- A generalization of Tucker's combinatorial lemma with topological applications
- Solutions of irreflexive relations
- Generalized sandwich theorems
- Rental Harmony: Sperner's Lemma in Fair Division
- A Borsuk–Ulam Equivalent that Directly Implies Sperner’s Lemma
- Intersection Patterns of Convex Sets via Simplicial Complexes: A Survey
- A Further Generalization of the Colourful Carathéodory Theorem
- On Maximal $S$-Free Sets and the Helly Number for the Family of $S$-Convex Sets
- Algorithms for Tolerated Tverberg Partitions
- Weighted geometric set cover via quasi-uniform sampling
- Transversal numbers over subsets of linear spaces
- Tverberg plus constraints
- The complexity of computing a Nash equilibrium
- Approximating Nash Equilibria and Dense Bipartite Subgraphs via an Approximate Version of Caratheodory's Theorem
- Algorithmic construction of sets for k -restrictions
- Tverberg's Theorem at 50: Extensions and Counterexamples
- How to Divide Things Fairly
- Colorful theorems for strong convexity
- Helly’s theorem: New variations and applications
- Intersection patterns of finite sets and of convex sets
- A Subexponential Lower Bound for Zadeh’s Pivoting Rule for Solving Linear Programs and Games
- The Design of Approximation Algorithms
- On the Complexity of Nash Equilibria and Other Fixed Points
- Ray-Shooting Depth: Computing Statistical Data Depth of Point Sets in the Plane
- New Lower Bounds for ϵ-nets
- Centerpoints: A Link Between Optimization and Convex Geometry
- Computational Complexity
- Equilibrium Points of Bimatrix Games
- A Generalization of Radon's Theorem
- Polynomial partitioning for a set of varieties
- Sperner's Colorings, Hypergraph Labeling Problems and Fair Division
- Nerves, minors, and piercing numbers
- Colorful Simplicial Depth, Minkowski Sums, and Generalized Gale Transforms
- Polynomiality for Bin Packing with a Constant Number of Item Types
- The Expected Number of Nash Equilibria of a Normal Form Game
- On Range Searching with Semialgebraic Sets. II
- Combinatorial Matrix Theory
- Algorithmic Game Theory
- Generalizations of a theorem of Carathéodory
- Some Intersection Properties of Convex Bodies
- Simplicial maps from an orientable n-pseudomanifold into Sm with the octahedral triangulation
- The Approximation of Fixed Points of a Continuous Mapping
- Intersection and Covering Properties of Convex Sets
- The Core of an N Person Game
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- APPROXIMATING CENTER POINTS WITH ITERATIVE RADON POINTS
- Universality of Nash Equilibria
- Sparse Solutions of Linear Diophantine Equations
- Carathéodory, Helly, and Radon Numbers for Sublattice and Related Convexities
- A Linearly Convergent Variant of the Conditional Gradient Algorithm under Strong Convexity, with Applications to Online and Stochastic Optimization
- On the imbedding of systems of compacta in simplicial complexes
- Equilibrium points in n -person games
- Sur la division pragmatique
- On Sets of Distances of n Points
- A Theorem on General Measure
- On extreme points of regular convex sets
- An Improved Bound for Weak Epsilon-nets in the Plane
- Approximating Tverberg points in linear time for any fixed dimension
- Proofs from THE BOOK
- Solving convex programs by random walks
- Intersecting convex sets by rays
- Combinatorial algebraic topology
- Geometric discrepancy. An illustrated guide
- Komplexe in euklidischen Räumen
- Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry. Written in cooperation with Anders Björner and Günter M. Ziegler
- Models and solution techniques for frequency assignment problems
- Tverberg partitions and Borsuk-Ulam theorems.
- Partitions of points into simplices with \(k\)-dimensional intersection. I: The conic Tverberg's theorem
- On the complexity of recognizing the Hilbert basis of a linear Diophantine system
- Proof of a conjecture of Bárány, Katchalski and Pach
