Department of Computer Science | Institute of Theoretical Computer Science | CADMO
Theory of Combinatorial Algorithms
Prof. Emo Welzl and Prof. Bernd Gärtner
Department of Computer Science | Institute of Theoretical Computer Science | CADMO
Prof. Emo Welzl and Prof. Bernd Gärtner
Learning and Optimization Group
Teaching and Research Group Bernd Gärtner
Institut für Theoretische Informatik
Departement Informatik
ETH Zürich
CH–8092 Zürich
| phone | +41–44–632 73 92 |
| fax | +41–44–632 10 63 |
(Financed by the Swiss National Science Foundation). Combinatorial questions about possibly high-dimensional point sets are at the core of the research field of discrete and computational geometry, a field that lies in the intersection of mathematics and computer science and incorporates many ideas and concepts from both areas. A fundamental theorem about the combinatorics of point sets is Tverberg’s theorem, named after Helge Tverberg who presented the first proof 60 years ago. Tverberg’s theorem states that any set of (r − 1)(d + 1) + 1 points in Rd can be partitioned into r parts such that the convex hulls of the parts have a point in common.
Tverberg’s theorem has many connections to deep and fundamental results in discrete and computational geometry. For example, it generalizes Radon’s Lemma, one of the most important results about convexity. It also implies the centerpoint theorem and is related to the colorful Caratheodory theorem. It is further a crucial ingredient in proofs of the first selection lemma as well as the existence of weak ε-nets, two deep results that play an important role in discrete geometry, as witnessed for example by the celebrated proof of the (p,q)-Theorem by Alon and Kleitman. More generally, Tverberg’s theorem is intimately related to the study of geometric transversals, in particular Helly-type theorems and intersection patterns of convex sets, an area that has recently regained attention through its importance in the emerging field of topological data analysis. As such, it is not surprising that Tverberg’s theorem has also found applications in the theory of data science and machine learning.
Due to its importance in discrete and computational geometry, many variants of Tverberg’s theorem have been proposed and studied. Examples of such variants include colorful versions, and versions with tolerance, where the convex hulls should still intersect even after removing some of the points. Maybe most famously, the topological Tverberg conjecture was one of the main drivers in the development of topological methods in discrete geometry and has only been disproven a few years ago.
Despite a significant body of work, many fundamental questions about Tverberg’s theorem are still not well- understood. These questions are both of a combinatorial nature, e.g., understanding the structure of Tverberg partitions, but also computational, like understanding the computational complexity of finding Tverberg partitions. Our project intends to fill many of these gaps in our understanding of Tverberg’s theorem. In particular, by bringing together a team with diverse background ranging from algebraic topology to combinatorial optimization, and employing several novel ideas and approaches based on very recent advances and new viewpoints in the area, we will prove new structural theorems as well as develop more efficient algorithms and better complexity bounds around Tverberg’s theorem. Our work connects to several important conjectures in the field that have been open since more than 20 years, and we expect that our work will resolve some of them.
Contact: B. Gärtner
Duration: 4 years (from Feb 2026)
