URN: urn:nbn:de:kobv:83-opus-14169
URL: http://opus.kobv.de/tuberlin/volltexte/2006/1416/
Hell, Stephan
Tverberg-type theorems and the Fractional Helly property
Sätze vom Tverberg-Typ und die Fraktionale Helly-Eigenschaft
| pdf-Format: |
|
Kurzfassung in Englisch
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 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 Vućić and Zivaljević 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 Vućić and Zivaljević 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).
Kurzfassung in Deutsch
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
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 Vućić und
Zivaljević 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 Vućić and Zivaljević
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.
| Freie Schlagwörter (deutsch): | Tverberg , äquivariant , Birch , Schranke , Helly | |
| Freie Schlagwörter (englisch): | Tverberg , equivariant , Birch , bound , Helly | |
| Institut: | Institut für Stadt- und Regionalplanung | |
| Fakultät: | Fakultät II - Mathematik und Naturwissenschaften | |
| DDC-Sachgruppe: | Mathematik | |
| Dokumentart: | Dissertation | |
| Hauptberichter: | Ziegler, Günter M. (Prof. Dr.) | |
| Sprache: | Englisch | |
| Tag der mündlichen Prüfung: | 24.10.2006 | |
| Erstellungsjahr: | 2006 | |
| Publikationsdatum: | 10.11.2006 | |
| Lizenz: | Minimallizenz mit PoD (Print-on-Demand): Typ Dissertation |
