The discrete yet ubiquitous theorems of Carath 'eodory, Helly, Sperner,\n Tucker, and Tverberg

2017/06/16 by Jesús A. De Loera, Xavier Goaoc, De Loera, Jesus A. +5 · 5 citations
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Management and Algorithms

paper · pdf · doi:10.48550/arxiv.1706.05975

Abstract

We discuss five discrete results: the lemmas of Sperner and Tucker from\ncombinatorial topology and the theorems of Carath 'eodory, Helly, and Tverberg\nfrom combinatorial geometry. We explore their connections and emphasize their\nbroad impact in application areas such as game theory, graph theory,\nmathematical optimization, computational geometry, etc.\n

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

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