Tverberg-type theorems and the Fractional Helly property

Sätze vom Tverberg-Typ und die Fraktionale Helly-Eigenschaft

  • The main part of this thesis deals with Tverberg's theorem, the topological Tverberg theorem, and Sierksma's Dutch cheese conjecture. Using different approaches we obtain new Tverberg-type theorems: Lower bounds for the number of Tverberg partitions, and a Tverberg's theorem with constraints. The last chapter is devoted to the Fractional Helly property. There we obtain a topological Fractional Helly theorem. Possible generalizations of Kalai, Matoušek, and Meshulam towards families of bounded hoThe main part of this thesis deals with Tverberg's theorem, the topological Tverberg theorem, and Sierksma's Dutch cheese conjecture. Using different approaches we obtain new Tverberg-type theorems: Lower bounds for the number of Tverberg partitions, and a Tverberg's theorem with constraints. The last chapter is devoted to the Fractional Helly property. There we obtain a topological Fractional Helly theorem. Possible generalizations of Kalai, Matoušek, and Meshulam towards families of bounded homological VC-dimension are discussed. Helge Tverberg showed in 1966 that any set of (d+1)(q-1)+1 points in d-dimensional Euclidean space can be partitioned into q disjoint subsets such that their convex hulls have a non-empty intersection. Sierksma conjectured in 1979 that there is not only one such Tverberg partition, but at least ((q-1)!)^d many of them. Bárány, Shlosman, and Szücs generalized Tverberg's theorem for primes q towards the so-called topological Tverberg theorem for primes q. This result has been extended to prime powers q by several authors, e.g. Özyadin in 1986, and Volovikov in 1996. According to Matoušek, "the validity of the topological Tverberg theorem for arbitrary q is one of the most challenging problems in topological combinatorics". Chapter 1 comes with an extensive introduction to the subject, and to the tools needed in this thesis. In Chapter 2 we apply the equivariant method from topological combinatorics to obtain new Tverberg-type theorems. We show a lower bound for the number of Tverberg partitions for prime powers q combining the ansatz of Vucic and Zivaljevic with the method of Volovikov. Stimulated by the work of Schöneborn and Ziegler (2005), we introduce the concept of a constraint graph: Two adjacent vertices end up in different blocks of a Tverberg partition. This leads us to a generalization of the topological Tverberg theorem which we call "Tverberg's theorem with constraints". In our proof we obtain connectivity results of new chessboard-type complexes. A part from that, we extend the lower bound for the number of splittings of a generic necklace from Vucic and Zivaljevic to prime powers. In Chapter 3 we obtain for the first time a non-trivial lower bound for the number of Tverberg partitions that holds for arbitrary q. There we make use of a concept called Birch partitions which was introduced by Birch to prove Tverberg's theorem for d=2 in 1959. Birch and Tverberg partitions are closely related. We prove evenness and a lower bound for the number of Birch partitions. Parts of the result were stimulated by the results on the number of colorful simplices of Deza et al. (2005), and a computer project outlined in Chapter 4. Applying the topological Tverberg theorem with constraints, we show a lower bound for the number of Tverberg points for prime powers q. Combining this lower bound, and the lower bound for the number of Tverberg partitions from this chapter we improve once more the lower bound for the number of Tverberg partitions for prime powers q. This settles Sierksma's conjecture for a wide class of sets of points in the plane for q=3. Moreover, we discuss topological versions of the results on the number of Birch partitions. We come up with examples showing that these results do not immediately carry over to the topological setting. In Chapter 4 we discuss the outcome of a computer project which served us to look at many, many examples. This project motivated the results of Chapters 2 and 3, and it also led to a list of open problems. Chapter 5 is independent of the previous ones, and it deals with generalizations of the Fractional Helly theorem for finite families of convex sets due to Katchalski and Liu (1979). Our main result is a topological Fractional Helly theorem extending a result of Alon et al. (2003). The proof is based on a spectral sequence argument. On our way, we come up with a nice and short proof of the homological version of the nerve theorem due to Björner (2003). Moreover, we study the relation of the Fractional Helly property, and homological VC-dimension. This discussion is motivated by the Fractional Helly theorem for finite families of bounded VC-dimension due to Bárány and Matoušek (2003), and a technical report of Kalai (2004).show moreshow less
  • Der Hauptteil dieser Arbeit handelt von Tverbergs Satz, dem topologischen Satz von Tverberg und der dazugehörigen "Dutch cheese"-Vermutung von Sierksma. Unter Verwendung unterschiedlicher Ansätze erhalten wir neue Sätze vom Tverberg-Typ: Untere Schranken für die Anzahl von Tverberg-Partitionen und ein "Tverberg's theorem with constraints". Das letzte Kapitel ist der Fraktionalen Helly-Eigenschaft gewidmet. Dort zeigen wir ein topologisches "Fractional Helly theorem". Mögliche VerallgemeinerungenDer Hauptteil dieser Arbeit handelt von Tverbergs Satz, dem topologischen Satz von Tverberg und der dazugehörigen "Dutch cheese"-Vermutung von Sierksma. Unter Verwendung unterschiedlicher Ansätze erhalten wir neue Sätze vom Tverberg-Typ: Untere Schranken für die Anzahl von Tverberg-Partitionen und ein "Tverberg's theorem with constraints". Das letzte Kapitel ist der Fraktionalen Helly-Eigenschaft gewidmet. Dort zeigen wir ein topologisches "Fractional Helly theorem". Mögliche Verallgemeinerungen, die auf Kalai, Matoušek und Meshulam zurückgehen, für Familien mit beschränkter VC-Dimension werden diskutiert. Helge Tverberg zeigte 1966, dass sich jede Menge von (d+1)(q-1)+1 Punkten im d-dimensionalen euklischen Raum so in q disjunkte Teilmengen zerlegen läßt, dass deren konvexe Hüllen einen nicht-leeren Durchschnitt haben. Sierksma vermutete 1979, dass es nicht nur eine solche Tverberg-Partition sondern sogar mindestens ((q-1)!)^d viele davon gibt. Bárány, Shlosman und Szücs verallgemeinerten Tverbergs Satz für Primzahlen q zum sogenannten "topologischen Satz von Tverberg" für Primzahlen q. Dieses Resultat wurde von mehreren Autoren für Primpotenzen q erweitert, z.B. Özyadin (1986) und Volovikov (1996). Matoušek zufolge ist die Gütigkeit des topologischen Satzes von Tverberg für beliebiges q eine der großen offenen Probleme der topologischen Kombinatorik. Kapitel 1 enthält eine ausführliche Einführung in die Themengebiete und Methoden dieser Arbeit. In Kapitel 2 erhalten wir neue Sätze vom Tverberg-Typ unter Verwendung der äquivarianten Methode. Wir zeigen eine untere Schranke für die Anzahl von Tverberg-Partitionen für Primpotenzen q, indem wir den Ansatz von Vucic und Zivaljevic mit der Methode von Volovikov kombinieren. Angeregt durch die aktuellen Resultate von Schöneborn und Ziegler (2005) führen wir das Konzept des Constraint-Graphen ein: Adjazente Ecken landen dadurch in verschiedenen Blöcken einer Tverberg-Partition. Dies führt zu einer Verallgemeinerung des topologischen Satzes von Tverberg, die wir "Tverberg's theorem with constraints" nennen. Im Beweis zeigen wir neue Ergebnisse über den Zusammenhang Schachbrett-artiger Komplexe. Außerdem erweitern wir die untere Schranke für die Anzahl von fairen Unterteilungen einer generischer Halskette von Vucic and Zivaljevic auf Primpotenzen q. In Kapitel 3 zeigen wir erstmals eine nicht-triviale untere Schranke für die Anzahl von Tverberg-Partitionen, die für beliebiges q gilt. Dabei verwenden das Konzept der Birch-Partition, das von Birch (1959) eingeführt wurde, um Tverbergs Satz in Dimension d=2 zu zeigen. Birch- und Tverberg-Partition sind stark miteinander verwandt. Wir zeigen ein Paritätsresultat und eine untere Schranke für die Anzahl von Birch-Partitionen. Diese Resultate wurden zum Teil durch die Arbeit von Deza et al. (2005) über die Anzahl von Regenbogensimplexen und ein Computerprojekt, das wir in Kapitel 4 beschreiben, motiviert. Anschließend zeigen wir eine untere Schranke für die Anzahl von Tverberg-Punkten durch geschicktes Anwenden des Resultats "Tverberg's theorem with constraints". Durch Kombination dieser unteren Schranke und der unteren Schranke für die Anzahl von Tverberg-Partitionen dieses Kapitels verbessern wir die untere Schranke für die Anzahl von Tverberg-Partitionen für Primpotenzen q nochmals. Dies bestätigt Sierksma's Vermutung für eine große Klasse von planaren Punktmengen für q=3. Des weiteren diskutieren wir, in wie weit sich die Resultate für die Anzahl von Birch-Partition auch in eine topologischen Version übertragen lassen. An Beispielen zeigen wir, dass diese Übertragung auf Anhieb nicht möglich ist. In Kapitel 4 diskutieren wir das Ergebnis eines Computerprojekts, durch welches wir viele, viele Beispiele studiert haben. Dieses Projekt hat die Resultate aus Kapitel 2 und 3 zum Teil motiviert. Außerdem hat es zu einer Liste von offenen Problemen geführt. Kapitel 5 ist unabhängig von den vorangegangenen Kapiteln. Es beschäftigt sich mit Verallgemeinerungen des "Fractional Helly theorem" für endliche Familien von konvexen Mengen, das auf Katchalski und Liu (1979) zurückgeht. Unser Hauptergebnis ist ein topologisches "Fractional Helly theorem", welches ein Resultat von Alon et al. (2003) erweitert. Im Beweis verwenden wir eine Spektralsequenz, und dabei erhalten wir einen kurzen und schönen Beweis einer homologischen Version des Nervensatzes von Björner (2003). Außerdem untersuchen wir die Beziehung der Fraktionalen Helly-Eigenschaft und homologischer VC-Dimension. Diese Diskussion geht auf ein "Fractional Helly theorem" für endliche Familien von beschränkter VC-Dimension von Bárány and Matoušek (2003) und einen Report von Kalai (2004) zurück.show moreshow less

Download full text files

Export metadata

  • Export Bibtex
  • Export RIS

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author: Stephan Hell
URN:urn:nbn:de:kobv:83-opus-14169
Advisor:Prof. Dr. Günter M. Ziegler
Document Type:Doctoral Thesis
Language:English
Date of Publication (online):2006/11/10
Publishing Institution:Technische Universität Berlin
Granting Institution:Technische Universität Berlin, Fakultät II - Mathematik und Naturwissenschaften
Date of final exam:2006/10/24
Release Date:2006/11/10
Tag:Birch; Helly; Schranke; Tverberg; äquivariant
Birch; Helly; Tverberg; bound; equivariant
Institutes:Institut für Stadt- und Regionalplanung
Dewey Decimal Classification:510 Mathematik
Licence (German):License LogoDeutsches Urheberrecht mit Print on Demand (u.a. für Dissertationen empfohlen)