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

2017/06/16 by Jesus A. De Loera, Jesús A. De Loera, De Loera, Jesus A. +7 · 6 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Management and Algorithms #cs.DM #math.CO #math.OC #msc:05Cxx #msc:52Cxx #msc:57Mxx #msc:90C99 #msc:91Axx

paper · pdf · doi:10.48550/arxiv.1706.05975

arxiv created 2018/10/08 · arxiv updated 2018/10/09

Abstract

We discuss five discrete results: the lemmas of Sperner and Tucker from combinatorial topology and the theorems of Carathéodory, Helly, and Tverberg from combinatorial geometry. We explore their connections and emphasize their broad impact in application areas such as game theory, graph theory, mathematical optimization, computational geometry, etc.

Citations

• Settling the complexity of computing two-player Nash equilibria

Cited by

• Hall's theorem for reconfigurations and higher dimensional topological connectedness
• Colorful circuits and colorful topes in oriented matroids
• Covering and labeling generalizations of the Borsuk-Ulam theorem
• No-dimensional Tverberg-type problems
• Tverberg's theorem, disks, and Hamiltonian cycles
• Computational Complexity of the α-Ham-Sandwich Problem

Related

• Helly-type Problems
• Lovasz' Conjecture and Other Applications of Topological Methods in Discrete Mathematics
• Carathéodory, Helly and the others in the max-plus world
• Generalized chessboard complexes and discrete Morse theory
• Geometric, Algebraic, and Topological Combinatorics