Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-852
Main Title: Combinatorial Curvatures, Group Actions, and Colourings: Aspects of Topological Combinatorics
Author(s): Lange, Carsten Eberhard Martin Christoph
Advisor(s): Ziegler, Günter M.
Granting Institution: Technische Universität Berlin, Fakultät II - Mathematik und Naturwissenschaften
Type: Doctoral Thesis
Language: English
Language Code: en
Abstract: Im ersten Teil untersuche ich die Fragestellung, wie klassische Krümmungsbegriffe der Differentialgeometrie auf diskrete Strukturen übertragen werden können. Dabei interessieren mich grundlegende strukturelle Analogien; Konvergenzfragen werden nicht diskutiert. Kapitel 1 ist durch differentialgeometrischen Konstruktionen motiviert. Das fundamentale Objekt, der Differenzenoperator, ermöglicht einerseits die Berechnung eines dem 'rough Laplacian' nach-empfundenen Operators, andererseits ein Analogon zum Riemannschen Krümmungstensor. Um ein Analogon zur Riccikrümmung zu erhalten, wird wie im glatten Fall eine geeignete Spur des diskreten Riemannschen Krümmungstensor gebildet. Kapitel 2 diskutiert Anwendungen der Objekte aus Kapitel 1. Zunächst wird eine kombinatorische Weitzenböckformel bewiesen, die in Spezialfällen mit einer von Forman postulierten Weitzenböckzerlegung übereinstimmt. Für kombinatorische 2-Mannigfaltigkeit wird dann eine kombinatorische Version des Satzes von Gauß-Bonnet bewiesen, wobei den Zellen bestimmte Gewichte zugeordnet werden. Diese Gewichte liefern ein Beispiel einer Weitzenböckformel, die von Formans Vorschlag abweicht. In seinem Kontext ist ein Satz von Gauß-Bonnet nicht möglich. In den folgenden Abschnitten untersuche ich, ob sich Formans kombinatorische Version des Satzes von Bochner für 1-Ketten auf meine modifizierte Riccikrümmung verallgemeinern läßt. Weiterhin diskutiere ich einen Ansatz für eine kombinatorische Version des Satz von Bochner für 2-Ketten. Das Kapitel endet mit einer Verallgemeinerung von Formans Ansatz einer Durchmesserabschätzung auf die im ersten Kapitel eingeführte verallgemeinerte Riccikrümmung. Es werden einige einfache Beispiele diskutiert, die zeigen, dass Formans Ansatz tatsächlich verallgemeinert wird. Im zweiten Teil werden untere Schranken für die chromatische Zahl von Graphen und Hypergraphen mit Hilfe topologischer Hilfsmittel untersucht. Die von Lovasz stammende Idee ist, einem (Hyper-)Graphen einen CW-Komplex mit einer Gruppenwirkung zu assoziieren und geeignete topologische Invarianten dieses Komplexes als untere Schranken für die chromatische Zahl des ursprünglichen (Hyper-)Graphen zu isolieren. In Kapitel 3, eine gemeinsame Arbeit mit Csorba, Schurr und Waßmer, wird die 'shore subdivision' eines Simplizialkomplexes beschrieben, die es ermöglicht, den ursprünglich von Lovasz betrachteten Komplex als Z_2-Unterkomplex eines Boxkomplexes zu realisieren. Insbesondere wird der Lovaszkomplex damit als starker Z_2-äquivarianter Deformationsretrakt des Boxkomplexes identifiziert. Die Retraktion geben wir explizit an. Weiter wird die 'shore subdivision' dann benutzt, um ein Ergebnis von Walker zu verallgemeinern: Die topologische untere Schranke kann nicht größer als l + m + 2 werden, wenn kein vollständiger bipartiter Untergraph auf l und m Ecken existiert. In Kapitel 4 wird die topologische Methode auf r-uniforme Hypergraphen erweitert. Dabei ist prinzipiell erlaubt, dass mehrfache Kopien einer Ecke in einer Hyperkante vorkommen. Von speziellem Interesse sind dabei s-disjunkte r-uniforme Kneserhypergraphen. Ich zeige anhand von Beispielen, dass der s-disjunkte r-Färbungsdefekt keine untere Schranke für die chromatische Zahl eines s-disjunkten r-uniformen Kneserhypergraphen ohne Vielfachheiten ist. Demgegenüber handelt es sich um eine untere Schranke, falls s-disjunkte r-uniforme Kneserhypergraphen mit Vielfach-heiten betrachtet werden. Ist r eine Primzahl ist, so gebe ich einen neuen Beweis. Dabei wird ein Ansatz von Matousek verallgemeinert. Eine Induktion soll laut Ziegler (in Spezialfällen laut Sarkaria) einen Schluß vom Primzahlfall auf beliebige ganze Zahlen ermöglichen: Die Induktion wird erläutert und auf eine bestehende Lücke hingewiesen.
The first part asks whether classical notions of curvature known from differential geometry can be carried over to discrete structures. Of particular interest are analogies on a structural level; questions of convergence are not considered. Chapter 1 is motivated by constructions well-known in differential geometry. The basic object, a difference operator, makes the computation of a discrete analogue of the rough Laplacian and of the Riemannian curvature tensor possible. A trace of the latter yields a discrete notion of Ricci curvature. Applications to the objects introduced in chapter 1 are discussed in chapter 2. The first application is the proof of a combinatorial formula of Weitzenböck-type that coincides with a decomposition of Weitzenböck-type postulated by Forman in many cases. Second, a combinatorial version of the theorem due to Gauß and Bonnet is proved for combinatorial 2-manifolds. For this theorem a special choice of weights has to be assigned to the cells that yield a Weitzenböck-formula different from the one postulated by Forman. The following sections discuss whether Forman's combinatorial version of a theorem of Bochner for 1-chains can be generalised to the weighted notion of Ricci curvature introduced in chapter 1 ar to p-chains with p>1. The chapter ends with a generalisation of Forman's diameter estimate to the weighted notion of Ricci curvature and simple examples show that his approach is indeed generalised. Part 2 asks for lower bounds for the chromatic number of graphs and hypergraphs obtained using topological methods. Lovasz's original idea is to associate a CW-complex with a group action to a (hyper)graph and to identify topological invariants of this complex as lower bounds for the chromatic number. In chapter 3, which is joint work with Csorba, Schurr, and Wassmer, the 'shore subdivsion' of a simplicial complex is described which is used to reaslise Lovasz's original complex as Z_2-subcomplex of a box complex. On the way, the Lovasz complex is identified as a strong Z_2-deformation retract of the box complex. The retraction is explicitly described. Then the 'shore subdivision' is used to generalise a result of Walker: The topological lower bound can never become larger than l + m + 2 if no complete bipartite subgraph on l and m vertices exists. The topological method is generalised to r-uniform hypergraphs in chapter 4. A hyperedge in this setting may contain multiple copies of a vertex. Of particular interest are s-disjoint r-uniform Kneserhypergraphs. Examples show that the s-disjoint r-colourability defect is not a lower bound of the chromatic number of s-disjoint r-uniform Kneserhypergraphs without multiplicities. But for Knesergraphs with multiplicities this is a lower bound: I present a new proof if r ia prime. This proof generalises an approach of Matousek. Inductions described by Sarkaria and by Ziegler that generalise an induction of Alon, Frankl, and Lovasz is supposed to prove the claim for any r. The induction and a gap within the induction is described.
URI: urn:nbn:de:kobv:83-opus-7536
http://depositonce.tu-berlin.de/handle/11303/1149
http://dx.doi.org/10.14279/depositonce-852
Exam Date: 25-Nov-2004
Issue Date: 18-Jan-2005
Date Available: 18-Jan-2005
DDC Class: 510 Mathematik
Subject(s): Chromatische Zahl von Graphen
Chromatische Zahl von Hyper
Diskrete Diffentialgeometrie
Diskrete Weitzenböckformel
Diskreter Satz von Gauß-Bonnet
Chromatic number for graphs
Chromatic number for hyperg
Discrete differential geometry
Discrete Gauß-Bonnet theorem
Discrete Weitzenböck formula
Usage rights: Terms of German Copyright Law
Appears in Collections:Technische Universität Berlin » Fakultäten & Zentralinstitute » Fakultät 2 Mathematik und Naturwissenschaften » Publications

Files in This Item:
File Description SizeFormat 
Dokument_9.pdf928.69 kBAdobe PDFThumbnail
View/Open


Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.