edoc-Server der Humboldt-Universität zu Berlin

Dissertation

Autor(en): Hiêp Hàn
Titel: Extremal hypergraph theory and algorithmic regularity lemma for sparse graphs
Gutachter: Mihyun Kang; Anuschirawan Taraz; Hanno Lefmann
Erscheinungsdatum: 18.10.2011
Volltext: pdf (urn:nbn:de:kobv:11-100196575)
Fachgebiet(e): Informatik
Schlagwörter (ger): Hypergraphen, Hamiltonkreise, perfekte Matchings, algorithmisches Regularitätslemma, Quasizufälligkeit, Eigenwertseparation, Diskrepanz
Schlagwörter (eng): quasi-randomness, hypergraphs, Hamilton cycles, perfect matchings, algorithmic regularity lemma, eigenvalue separation, discrepancy
Einrichtung: Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II
Lizenz: Namensnennung - Keine Bearbeitung (CC BY ND)
Zitationshinweis: Hàn, Hiêp: Extremal hypergraph theory and algorithmic regularity lemma for sparse graphs; Dissertation, Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II , publiziert am 18.10.2011, urn:nbn:de:kobv:11-100196575
Metadatenexport: Um den gesamten Metadatensatz im Endnote- oder Bibtex-Format zu speichern, klicken Sie bitte auf den entsprechenden Link. Endnote   Bibtex  
print on demand: Wenn Sie auf dieses Icon klicken, können Sie ein Druckexemplar dieser Publikation bestellen.
Diese Seite taggen: Diese Icons führen auf so genannte Social-Bookmark-Systeme, auf denen Sie Lesezeichen anlegen, persönliche Tags vergeben und Lesezeichen anderer Nutzer ansehen können.
  • connotea
  • del.icio.us
  • Furl
  • RawSugar

Abstract (ger):
Einst als Hilfssatz für Szemerédis Theorem entwickelt, hat sich das Regularitätslemma in den vergangenen drei Jahrzehnten als eines der wichtigsten Werkzeuge der Graphentheorie etabliert. Im Wesentlichen hat das Lemma zum Inhalt, dass dichte Graphen durch eine konstante Anzahl quasizufälliger, bipartiter Graphen approximiert werden können, wodurch zwischen deterministischen und zufälligen Graphen eine Brücke geschlagen wird. Da letztere viel einfacher zu handhaben sind, stellt diese Verbindung oftmals eine wertvolle Zusatzinformation dar. Vom Regularitätslemma ausgehend gliedert sich die vorliegende Arbeit in zwei Teile. Mit Fragestellungen der Extremalen Hypergraphentheorie beschäftigt sich der erste Teil der Arbeit. Es wird zunächst eine Version des Regularitätslemmas Hypergraphen angewandt, um asymptotisch scharfe Schranken für das Auftreten von Hamiltonkreisen in uniformen Hypergraphen mit hohem Minimalgrad herzuleiten. Nachgewiesen werden des Weiteren asymptotisch scharfe Schranken für die Existenz von perfekten und nahezu perfekten Matchings in uniformen Hypergraphen mit hohem Minimalgrad. Im zweiten Teil der Arbeit wird ein neuer, Szemerédis ursprüngliches Konzept generalisierender Regularitätsbegriff eingeführt. Diesbezüglich wird ein Algorithmus vorgestellt, welcher zu einem gegebenen Graphen ohne zu dichte induzierte Subgraphen eine reguläre Partition in polynomieller Zeit berechnet. Als eine Anwendung dieses Resultats wird gezeigt, dass das Problem MAX-CUT für die oben genannte Graphenklasse in polynomieller Zeit bis auf einen multiplikativen Faktor von (1+o(1)) approximierbar ist. Der Untersuchung von Chung, Graham und Wilson zu quasizufälligen Graphen folgend wird ferner der sich aus dem neuen Regularitätskonzept ergebende Begriff der Quasizufälligkeit studiert und in Hinsicht darauf eine Charakterisierung mittels Eigenwertseparation der normalisierten Laplaceschen Matrix angegeben.
Abstract (eng):
Once invented as an auxiliary lemma for Szemerédi''s Theorem the regularity lemma has become one of the most powerful tools in graph theory in the last three decades which has been widely applied in several fields of mathematics and theoretical computer science. Roughly speaking the lemma asserts that dense graphs can be approximated by a constant number of bipartite quasi-random graphs, thus, it narrows the gap between deterministic and random graphs. Since the latter are much easier to handle this information is often very useful. With the regularity lemma as the starting point two roads diverge in this thesis aiming at applications of the concept of regularity on the one hand and clarification of several aspects of this concept on the other. In the first part we deal with questions from extremal hypergraph theory and foremost we will use a generalised version of Szemerédi''s regularity lemma for uniform hypergraphs to prove asymptotically sharp bounds on the minimum degree which ensure the existence of Hamilton cycles in uniform hypergraphs. Moreover, we derive (asymptotically sharp) bounds on minimum degrees of uniform hypergraphs which guarantee the appearance of perfect and nearly perfect matchings. In the second part a novel notion of regularity will be introduced which generalises Szemerédi''s original concept. Concerning this new concept we provide a polynomial time algorithm which computes a regular partition for given graphs without too dense induced subgraphs. As an application we show that for the above mentioned class of graphs the problem MAX-CUT can be approximated within a multiplicative factor of (1+o(1)) in polynomial time. Furthermore, pursuing the line of research of Chung, Graham and Wilson on quasi-random graphs we study the notion of quasi-randomness resulting from the new notion of regularity and concerning this we provide a characterisation in terms of eigenvalue separation of the normalised Laplacian matrix.
Zugriffsstatistik: Die Daten für die Zugriffsstatistik der einzelnen Dokumente wurden aus den durch AWStats aggregierten Webserver-Logs erstellt. Sie beziehen sich auf den monatlichen Zugriff auf den Volltext sowie auf die Startseite. Die Zugriffsstatistik wird nicht standardisiert erfasst und kann maschinelle Zugriffe enthalten.
 
Bei Formatversionen eines Dokuments, die aus mehreren Dateien bestehen (insbesondere HTML), wird jeweils der monatlich höchste Zugriffswert auf eine der Dateien (Kapitel) des Dokuments angezeigt.
 
Um die detaillierten Zugriffszahlen zu sehen, fahren Sie bitte mit dem Mauszeiger über die einzelnen Balken des Diagramms.
PDF: 8 Zugriffe Startseite: 1 Zugriffe PDF: 5 Zugriffe PDF: 4 Zugriffe PDF: 13 Zugriffe Startseite: 4 Zugriffe PDF: 3 Zugriffe Startseite: 3 Zugriffe PDF: 12 Zugriffe Startseite: 1 Zugriffe PDF: 5 Zugriffe PDF: 7 Zugriffe PDF: 6 Zugriffe PDF: 8 Zugriffe PDF: 6 Zugriffe PDF: 11 Zugriffe Startseite: 1 Zugriffe PDF: 22 Zugriffe Startseite: 1 Zugriffe PDF: 26 Zugriffe Startseite: 1 Zugriffe PDF: 17 Zugriffe Startseite: 2 Zugriffe PDF: 22 Zugriffe Startseite: 2 Zugriffe PDF: 19 Zugriffe Startseite: 3 Zugriffe PDF: 21 Zugriffe Startseite: 1 Zugriffe PDF: 19 Zugriffe PDF: 19 Zugriffe Startseite: 3 Zugriffe PDF: 23 Zugriffe Startseite: 1 Zugriffe PDF: 14 Zugriffe PDF: 15 Zugriffe Startseite: 1 Zugriffe PDF: 31 Zugriffe PDF: 28 Zugriffe Startseite: 1 Zugriffe PDF: 24 Zugriffe
Dec
11
Feb
12
Apr
12
May
12
Jun
12
Jul
12
Aug
12
Sep
12
Oct
12
Nov
12
Dec
12
Jan
13
Feb
13
Mar
13
Apr
13
May
13
Jun
13
Jul
13
Aug
13
Sep
13
Oct
13
Nov
13
Dec
13
Jan
14
Feb
14
Mar
14
Monat Dec
11
Feb
12
Apr
12
May
12
Jun
12
Jul
12
Aug
12
Sep
12
Oct
12
Nov
12
Dec
12
Jan
13
Feb
13
Mar
13
Apr
13
May
13
Jun
13
Jul
13
Aug
13
Sep
13
Oct
13
Nov
13
Dec
13
Jan
14
Feb
14
Mar
14
Startseite   1     4 3 1           1 1 1 2 2 3 1   3 1   1   1
PDF 8 5 4 13 3 12 5 7 6 8 6 11 22 26 17 22 19 21 19 19 23 14 15 31 28 24

Gesamtzahl der Zugriffe seit Dec 2011:

  • Startseite – 26 (1.04 pro Monat)
  • PDF – 388 (14.92 pro Monat)
 
 
Generiert am 20.04.2014, 05:58:19