The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg (Q5241224)

scientific article; zbMATH DE number 7124543

Language	Label	Description	Also known as
English	The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg	scientific article; zbMATH DE number 7124543

Statements

instance of

scholarly article

0 references

title

The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg (English)

0 references

0 references

0 references

0 references

0 references

Bulletin of the American Mathematical Society

0 references

publication date

30 October 2019

0 references

full work available at URL

https://arxiv.org/abs/1706.05975

0 references

zbMATH Keywords

Carathéodory

0 references

Helly

0 references

Sperner

0 references

Tucker

0 references

Tverberg

0 references

describes a project that uses

0 references

0 references

0 references

0 references

MaRDI publication profile

0 references

cites work

Models and solution techniques for frequency assignment problems

0 references

On a lower bound for the connectivity of the independence complex of a graph

0 references

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

0 references

Colorful Simplicial Depth, Minkowski Sums, and Generalized Gale Transforms

0 references

The equivalence of linear programs and zero-sum games

0 references

On Range Searching with Semialgebraic Sets. II

0 references

Independent systems of representatives in weighted graphs

0 references

Fractional kernels in digraphs

0 references

Q5692690

0 references

Proofs from THE BOOK

0 references

2-D Tucker is PPA complete

0 references

A quantitative Doignon-Bell-Scarf theorem

0 references

The Support of Integer Optimal Solutions

0 references

Sparse Solutions of Linear Diophantine Equations

0 references

Colorful subhypergraphs in uniform hypergraphs

0 references

On the chromatic number of general Kneser hypergraphs

0 references

Strengthening topological colorful results for graphs

0 references

Fair splitting of colored paths

0 references

Splitting necklaces

0 references

Point Selections and Weak ε-Nets for Convex Hulls

0 references

Transversal numbers for hypergraphs arising in geometry

0 references

Piercing convex sets and the Hadwiger-Debrunner $(p,q)$-problem

0 references

Algorithmic construction of sets for k -restrictions

0 references

The Borsuk-Ulam Theorem and Bisection of Necklaces

0 references

Algorithms for bivariate medians and a Fermat-Torricelli problem for lines.

0 references

Helly-type theorems and generalized linear programming

0 references

Regression depth and center points.

0 references

Helly’s theorem: New variations and applications

0 references

Very colorful theorems

0 references

Computational Complexity

0 references

On Reay's relaxed Tverberg conjecture and generalizations of Conway's thrackle conjecture

0 references

Fair Division and Generalizations of Sperner- and KKM-type Results

0 references

Subjectivity and correlation in randomized strategies

0 references

On Maximal $S$-Free Sets and the Helly Number for the Family of $S$-Convex Sets

0 references

Tight bounds on discrete quantitative Helly numbers

0 references

Transversal numbers over subsets of linear spaces

0 references

An exponential lower bound for Cunningham's rule

0 references

Q2959048

0 references

On a common generalization of Borsuk's and Radon's theorem

0 references

A generalization of Caratheodory's theorem

0 references

Q3138751

0 references

Tverberg's Theorem at 50: Extensions and Counterexamples

0 references

Quantitative Helly-Type Theorems

0 references

A Colored Version of Tverberg's Theorem

0 references

A fractional Helly theorem for convex lattice sets

0 references

Q4352311

0 references

Colourful Linear Programming and its Relatives

0 references

On a Topological Generalization of a Theorem of Tverberg

0 references

Tverberg plus minus

0 references

Tverberg’s theorem is 50 years old: A survey

0 references

Approximating Nash Equilibria and Dense Bipartite Subgraphs via an Approximate Version of Caratheodory's Theorem

0 references

Q4790110

0 references

Hitting simplices with points in $\mathbb R^{3}$

0 references

Optimality certificates for convex minimization and Helly numbers

0 references

Centerpoints: A Link Between Optimization and Convex Geometry

0 references

A Theorem Concerning the Integer Lattice

0 references

Q3452586

0 references

Solving convex programs by random walks

0 references

The Radon number of the three-dimensional integer lattice

0 references

Q3264648

0 references

Q4871782

0 references

Polynomial partitioning for several sets of varieties

0 references

Topology of the Grünbaum–Hadwiger–Ramos hyperplane mass partition problem

0 references

Hyperplane mass partitions via relative equivariant obstruction theory

0 references

Tverberg plus constraints

0 references

Barycenters of polytope skeleta and counterexamples to the topological Tverberg conjecture, via constraints

0 references

Optimal bounds for a colorful Tverberg-Vrećica type problem

0 references

Optimal bounds for the colored Tverberg problem

0 references

Thieves can make sandwiches

0 references

Beyond the Borsuk–Ulam Theorem: The Topological Tverberg Story

0 references

Sparse Approximation via Generating Point Sets

0 references

The number of triangles covering the center of an $n$-set

0 references

Perfect graphs are kernel solvable

0 references

On the imbedding of systems of compacta in simplicial complexes

0 references

Q4821526

0 references

Q4338900

0 references

N-Person Cake-Cutting: There May Be No Perfect Division

0 references

How to Divide Things Fairly

0 references

Quantitative Helly-type theorem for the diameter of convex sets

0 references

Almost optimal set covers in finite VC-dimension

0 references

Combinatorial Matrix Theory

0 references

A counterexample to an integer analogue of Carathéodory's theorem

0 references

A point in many triangles

0 references

Lower bounds for weak epsilon-nets and stair-convexity

0 references

Stabbing simplices by points and flats

0 references

Uncertain convex programs: randomized solutions and confidence levels

0 references

The Scenario Approach to Robust Control Design

0 references

Inequalities of Bernstein-Jackson-type and the degree of compactness of operators in Banach spaces

0 references

Some Intersection Properties of Convex Bodies

0 references

Intersection and Covering Properties of Convex Sets

0 references

Q5501289

0 references

Improved Deterministic Algorithms for Linear Programming in Low Dimensions

0 references

Q5743501

0 references

Cutting hyperplanes for divide-and-conquer

0 references

Q4515159

0 references

Improved bounds on weak ε-nets for convex sets

0 references

Oja centers and centers of gravity

0 references

On the Multichromatic Number of s‐Stable Kneser Graphs

0 references

On the complexity of 2D discrete fixed point problem

0 references

Settling the complexity of computing two-player Nash equilibria

0 references

Sublinear Bounds for a Quantitative Doignon--Bell--Scarf Theorem

0 references

NP-completeness of the linear complementarity problem

0 references

New applications of random sampling in computational geometry

0 references

Las Vegas algorithms for linear and integer programming when the dimension is small

0 references

Combinatorial complexity bounds for arrangements of curves and spheres

0 references

APPROXIMATING CENTER POINTS WITH ITERATIVE RADON POINTS

0 references

Applications of random sampling in computational geometry. II

0 references

Two-player envy-free multi-cake division

0 references

An integer analogue of Carathéodory's theorem

0 references

The Linear Complementarity Problem

0 references

Theoretical Properties of the Network Simplex Method

0 references

Constructive proof of the min-max theorem

0 references

Q5341481

0 references

The complexity of computing a Nash equilibrium

0 references

Universality of Nash Equilibria

0 references

Q5452284

0 references

Q4904855

0 references

Quantitative combinatorial geometry for continuous parameters

0 references

Beyond Chance-Constrained Convex Mixed-Integer Optimization: A Generalized Calafiore-Campi Algorithm and the notion of $S$-optimization

0 references

Helly numbers of algebraic subsets of $\mathbb{R}^{d}$ and an extension of Doignon's theorem

0 references

Quantitative Tverberg theorems over lattices and other discrete sets

0 references

A polytopal generalization of Sperner's lemma

0 references

Triangulations. Structures for algorithms and applications

0 references

A course in topological combinatorics

0 references

Splitting multidimensional necklaces

0 references

Helly numbers of acyclic families

0 references

The combinatorics of timetabling

0 references

Algorithmic Solutions for Envy-Free Cake Cutting

0 references

Colourful simplicial depth

0 references

Q5315023

0 references

A point in an $nd$-polytope is the barycenter of $n$ points in its $d$-faces

0 references

Q4331785

0 references

Convexity in cristallographical lattices

0 references

Simple proofs of some Borsuk-Ulam results

0 references

Q3949617

0 references

How to Cut A Cake Fairly

0 references

Graphes Noyau-Parfaits

0 references

Q3787039

0 references

Une généralisation du théorème de Richardson sur l'existence de noyaux dans les graphes orientes

0 references

On the complexity of recognizing the Hilbert basis of a linear Diophantine system

0 references

An upper-bound theorem for families of convex sets

0 references

Q4274009

0 references

The partition conjecture

0 references

Q4149476

0 references

Carathéodory bounds for integer cones

0 references

On Sets of Distances of n Points

0 references

New lower bounds for Hopcroft's problem

0 references

On the Complexity of Nash Equilibria and Other Fixed Points

0 references

Hitting sets when the VC-dimension is small

0 references

A generalization of Tucker's combinatorial lemma with topological applications

0 references

Simplicial maps from an orientable n-pseudomanifold into Sm with the octahedral triangulation

0 references

Group actions and Helly's theorem

0 references

Consensus halving is PPA-complete

0 references

The complexity of splitting necklaces and bisecting ham sandwiches

0 references

Q5365109

0 references

A constructive proof of Tucker's combinatorial lemma

0 references

Intersection patterns of finite sets and of convex sets

0 references

Achieving Rental Harmony with a Secretive Roommate

0 references

Colorful coverings of polytopes and piercing numbers of colorful $d$-intervals

0 references

A Subexponential Lower Bound for Zadeh’s Pivoting Rule for Solving Linear Programs and Games

0 references

Intersecting convex sets by rays

0 references

A computational approach to Conway's thrackle conjecture

0 references

The Game of Hex and the Brouwer Fixed-Point Theorem

0 references

Equilibrium in a discrete exchange economy with money

0 references

On kernels and semikernels of digraphs

0 references

A Linearly Convergent Variant of the Conditional Gradient Algorithm under Strong Convexity, with Applications to Online and Stochastic Optimization

0 references

A note on the Tolerant Tverberg Theorem

0 references

ETR-Completeness for Decision Versions of Multi-player (Symmetric) Nash Equilibria

0 references

Violator spaces: Structure and algorithms

0 references

Polyhedra with the integer Carathéodory property

0 references

Geometric medians

0 references

Total dual integrality and integer polyhedra

0 references

Bounding Helly Numbers via Betti Numbers

0 references

Polynomiality for Bin Packing with a Constant Number of Item Types

0 references

Bisection of Circle Colorings

0 references

TFNP: An Update

0 references

On the foundations of linear and integer linear programming I

0 references

Singularities, expanders and topology of maps. II: From combinatorics to topology via algebraic isoperimetry

0 references

Q3142503

0 references

Convex and Discrete Geometry

0 references

Polynomial partitioning for a set of varieties

0 references

Q3178604

0 references

On the Erdős distinct distances problem in the plane

0 references

Q4168622

0 references

Q4352272

0 references

Combinatorial Stokes formulas via minimal resolutions

0 references

$\epsilon$-nets and simplex range queries

0 references

A condition for matchability in hypergraphs

0 references

Q3116045

0 references

On the number of Tverberg partitions in the prime power case

0 references

On the number of Birch partitions

0 references

Q3951161

0 references

The intersection of a matroid and an oriented matroid

0 references

Points surrounding the origin

0 references

Q4400994

0 references

Colorful theorems for strong convexity

0 references

Nerves, minors, and piercing numbers

0 references

Computing a centerpoint of a finite planar set of points in linear time

0 references

Intersection patterns of convex sets

0 references

Q4866086

0 references

Q4550929

0 references

A topological colorful Helly theorem

0 references

Games of fixed rank: a hierarchy of bimatrix games

0 references

Dual theorems on central points and their generalizations

0 references

Topological methods in combinatorial geometry

0 references

Tverberg-type theorems for intersecting by rays

0 references

A simpler proof of the Boros-Füredi-Bárány-Pach-Gromov theorem

0 references

A new polynomial-time algorithm for linear programming

0 references

A Problem of Geometry in R n

0 references

Axiomatic convexity theory and relationships between the Carathéodory, Helly, and Radon numbers

0 references

Polynomial algorithms in linear programming

0 references

A note on kernels and Sperner's Lemma

0 references

Q4051879

0 references

Combinatorial algebraic topology

0 references

A new lower bound based on Gromov's method of selecting heavily covered points

0 references

Q4828983

0 references

New Lower Bounds for ϵ-nets

0 references

The complexity of hyperplane depth in the plane

0 references

Envy-free two-player $m$-cake and three-player two-cake divisions

0 references

Equilibrium Points of Bimatrix Games

0 references

On a notion of simplicial depth

0 references

Algorithms for ham-sandwich cuts

0 references

Normal hypergraphs and the perfect graph conjecture

0 references

Kneser's conjecture, chromatic number, and homotopy

0 references

Graph minor theory

0 references

Q3395507

0 references

On extreme points of regular convex sets

0 references

Eliminating Tverberg Points, I. An Analogue of the Whitney Trick

0 references

Further Consequences of the Colorful Helly Hypothesis

0 references

Efficient partition trees

0 references

Geometric discrepancy. An illustrated guide

0 references

Q4530626

0 references

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

0 references

A combinatorical proof of Kneser's conjecture

0 references

Bounded VC-dimension implies a fractional Helly theorem

0 references

Q3570078

0 references

Understanding and using linear programming

0 references

Topological lower bounds for the chromatic number: a hierarchy

0 references

A subexponential bound for linear programming

0 references

New constructions of weak $\varepsilon$-nets

0 references

On Gromov's method of selecting heavily covered points

0 references

Q4369429

0 references

The Expected Number of Nash Equilibria of a Normal Form Game

0 references

Using volume to prove Sperner's Lemma

0 references

The clique complex and hypergraph matching

0 references

Domination numbers and homology

0 references

Sperner labellings: A combinatorial approach

0 references

The chromatic number of almost stable Kneser hypergraphs

0 references

A Further Generalization of the Colourful Carathéodory Theorem

0 references

The Rainbow at the End of the Line — A PPAD Formulation of the Colorful Carathéodory Theorem with Applications

0 references

Colorful linear programming, Nash equilibrium, and pivots

0 references

Envy-free cake division without assuming the players prefer nonempty pieces

0 references

Q2768366

0 references

Sperner's Colorings, Hypergraph Labeling Problems and Fair Division

0 references

Sperner’s Colorings and Optimal Partitioning of the Simplex

0 references

On depth and deep points: A calculus.

0 references

Q5817857

0 references

Algorithms for Tolerated Tverberg Partitions

0 references

Q5368675

0 references

Approximating Tverberg points in linear time for any fixed dimension

0 references

Q3827224

0 references

Extensions of Sperner and Tucker's lemma for manifolds

0 references

Homotopy invariants of covers and KKM-type lemmas

0 references

KKM type theorems with boundary conditions

0 references

A simple proof of optimal epsilon nets

0 references

Weak $\varepsilon $-nets have basis of size $O(1/\varepsilon\log (1/\varepsilon))$ in any dimension

0 references

An optimal extension of the centerpoint theorem

0 references

An optimal generalization of the colorful Carathéodory theorem

0 references

Ray-Shooting Depth: Computing Statistical Data Depth of Point Sets in the Plane

0 references

k-Centerpoints Conjectures for Pointsets in ℝd

0 references

A proof of the Oja depth conjecture in the plane

0 references

Equilibrium points in n -person games

0 references

Non-cooperative games

0 references

Proof of a conjecture of Bárány, Katchalski and Pach

0 references

Algorithmic Game Theory

0 references

Q5726007

0 references

A Borsuk–Ulam Equivalent that Directly Implies Sperner’s Lemma

0 references

Descriptive statistics for multivariate distributions

0 references

On the Geometry and Computational Complexity of Radon Partitions in the Iinteger Lattice

0 references

Nonlinear discrete optimization. An algorithmic theory

0 references

Q4339095

0 references

Combinatorial necklace splitting

0 references

On the complexity of the parity argument and other inefficient proofs of existence

0 references

A note on smaller fractional Helly numbers

0 references

A partitioned version of the Erdős-Szekeres theorem for quadrilaterals

0 references

A constructive proof of Ky Fan's generalization of Tucker's lemma

0 references

Carathéodory, Helly, and Radon Numbers for Sublattice and Related Convexities

0 references

A Theorem on General Measure

0 references

Generalizations of a theorem of Carathéodory

0 references

Solutions of irreflexive relations

0 references

Q4221107

0 references

Quantitative $(p, q)$ theorems in combinatorial geometry

0 references

Q3497967

0 references

Economics and computation. An introduction to algorithmic game theory, computational social choice, and fair division

0 references

Partitions of points into simplices with $k$-dimensional intersection. I: The conic Tverberg's theorem

0 references

Algorithm AS 307: Bivariate Location Depth

0 references

Regression Depth

0 references

An Improved Bound for Weak Epsilon-nets in the Plane

0 references

Tverberg's theorem via number fields

0 references

Tverberg partitions and Borsuk-Ulam theorems.

0 references

The colourful simplicial depth conjecture

0 references

The Approximation of Fixed Points of a Continuous Mapping

0 references

The Core of an N Person Game

0 references

An observation on the structure of production sets with indivisibilities

0 references

Fixed points, Nash equilibria, and the existential theory of the reals

0 references

The topological Tverberg theorem and winding numbers

0 references

Q3869375

0 references

Q4221106

0 references

Combinatorial optimization. Polyhedra and efficiency (3 volumes)

0 references

A Lower Bound Technique for Triangulations of Simplotopes

0 references

Small-dimensional linear programming and convex hulls made easy

0 references

Decomposition of regular matroids

0 references

Q2925334

0 references

Consensus-halving via theorems of Borsuk-Ulam and Tucker

0 references

Hyperplane equipartitions plus constraints

0 references

Mathematical problems for the next century

0 references

Gerrymandering, Sandwiches, and Topology

0 references

Robust Tverberg and Colourful Carathéodory Results via Random Choice

0 references

A generalisation of Tverberg's theorem

0 references

The LSB Theorem Implies the KKM Lemma

0 references

n-tuple colorings and associated graphs

0 references

Transversals of latin squares and their generalizations

0 references

Sur la division pragmatique

0 references

Generalized ''sandwich'' theorems

0 references

How to Cut a Cake Fairly

0 references

Envy-free cake divisions cannot be found by finite protocols

0 references

Rental Harmony: Sperner's Lemma in Fair Division

0 references

Extremal problems in discrete geometry

0 references

Intersection Patterns of Convex Sets via Simplicial Complexes: A Survey

0 references

A New Triangulation for Simplicial Algorithms

0 references

Q4117205

0 references

A Generalization of Radon's Theorem

0 references

A generalization of Radon's theorem II

0 references

On generalizations of Radon's theorem and the Ham sandwich theorem

0 references

The best constant in Siegel's Lemma

0 references

Q3141898

0 references

Komplexe in euklidischen Räumen

0 references

Efficient algorithms for maximum regression depth

0 references

On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities

0 references

Weighted geometric set cover via quasi-uniform sampling

0 references

Q4258215

0 references

On a topological generalization of the Tverberg theorem

0 references

Q2892811

0 references

Note on a conjecture of Sierksma

0 references

Implementation of a unimodularity test

0 references

The Design of Approximation Algorithms

0 references

Dividing a cake fairly

0 references

Q3424895

0 references

Generalized Kneser coloring theorems with combinatorial proofs

0 references

Q3001813

0 references

Oriented matroids and Ky Fan's theorem

0 references

Q4401001

0 references

The colored Tverberg's problem and complexes of injective functions

0 references

Identifiers

zbMATH Open document ID

1460.52010

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:5241224