edoc-Server der Humboldt-Universität zu Berlin

Habilitationsschrift

Autor(en): Mathias Schacht
Titel: Regular partitions of hypergraphs and property testing
Gutachter: Mihyun Kang; Noga Alon; Susanne Albers
Erscheinungsdatum: 28.10.2010
Volltext: pdf (urn:nbn:de:kobv:11-100181885)
Fachgebiet(e): Informatik
Schlagwörter (ger): randomisierte Testalgorithmen, Regularitätslemmata für Graphen, Regularitätslemmata für Hypergraphen, size-Ramsey Zahl
Schlagwörter (eng): property testing, regularity lemmas for graphs, regularity lemma for hypergraphs, size-Ramsey number
Einrichtung: Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II
Zitationshinweis: Schacht, Mathias: Regular partitions of hypergraphs and property testing; Habilitationsschrift, Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II , publiziert am 28.10.2010, urn:nbn:de:kobv:11-100181885
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.

Abstract (ger):
Die Regularitätsmethode für Graphen wurde vor über 30 Jahren von Szemerédi, für den Beweis seines Dichteresultates über Teilmengen der natürlichen Zahlen, welche keine arithmetischen Progressionen enthalten, entwickelt. Grob gesprochen besagt das Regularitätslemma, dass die Knotenmenge eines beliebigen Graphen in konstant viele Klassen so zerlegt werden kann, dass fast alle induzierten bipartiten Graphen quasi-zufällig sind, d.h. sie verhalten sich wie zufällige bipartite Graphen mit derselben Dichte. Das Regularitätslemma hatte viele weitere Anwendungen, vor allem in der extremalen Graphentheorie, aber auch in der theoretischen Informatik und der kombinatorischen Zahlentheorie, und gilt mittlerweile als eines der zentralen Hilfsmittel in der modernen Graphentheorie. Vor wenigen Jahren wurden Regularitätslemmata für andere diskrete Strukturen entwickelt. Insbesondere wurde die Regularitätsmethode für uniforme Hypergraphen und dünne Graphen verallgemeinert. Ziel der vorliegenden Arbeit ist die Weiterentwicklung der Regularitätsmethode und deren Anwendung auf Probleme der theoretischen Informatik. Im Besonderen wird gezeigt, dass vererbbare (entscheidbare) Hypergrapheneigenschaften, das sind Familien von Hypergraphen, welche unter Isomorphie und induzierten Untergraphen abgeschlossen sind, testbar sind. D.h. es existiert ein randomisierter Algorithmus, der in konstanter Laufzeit mit hoher Wahrscheinlichkeit zwischen Hypergraphen, welche solche Eigenschaften haben und solchen die „weit“ davon entfernt sind, unterscheidet.
Abstract (eng):
About 30 years ago Szemerédi developed the regularity method for graphs, which was a key ingredient in the proof of his famous density result concerning the upper density of subsets of the integers which contain no arithmetic progression of fixed length. Roughly speaking, the regularity lemma asserts, that the vertex set of every graph can be partitioned into a constant number of classes such that almost all of the induced bipartite graphs are quasi-random, i.e., they mimic the behavior of random bipartite graphs of the same density. The regularity lemma had have many applications mainly in extremal graph theory, but also in theoretical computer science and additive number theory, and it is considered one of the central tools in modern graph theory. A few years ago the regularity method was extended to other discrete structures. In particular extensions for uniform hypergraphs and sparse graphs were obtained. The main goal of this thesis is the further development of the regularity method and its application to problems in theoretical computer science. In particular, we will show that hereditary, decidable properties of hypergraphs, that are properties closed under isomorphism and vertex removal, are testable. I.e., there exists a randomised algorithm with constant running time, which distinguishes between Hypergraphs displaying the property and those which are “far” from it.
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.
Startseite: 2 Zugriffe PDF: 5 Zugriffe PDF: 1 Zugriffe Startseite: 5 Zugriffe PDF: 1 Zugriffe Startseite: 2 Zugriffe PDF: 7 Zugriffe Startseite: 3 Zugriffe Startseite: 5 Zugriffe PDF: 1 Zugriffe Startseite: 2 Zugriffe PDF: 1 Zugriffe PDF: 2 Zugriffe Startseite: 2 Zugriffe PDF: 6 Zugriffe Startseite: 7 Zugriffe PDF: 7 Zugriffe Startseite: 2 Zugriffe PDF: 10 Zugriffe Startseite: 1 Zugriffe PDF: 9 Zugriffe PDF: 5 Zugriffe Startseite: 6 Zugriffe PDF: 16 Zugriffe Startseite: 5 Zugriffe PDF: 19 Zugriffe PDF: 5 Zugriffe PDF: 13 Zugriffe PDF: 14 Zugriffe Startseite: 2 Zugriffe PDF: 13 Zugriffe PDF: 12 Zugriffe PDF: 13 Zugriffe PDF: 8 Zugriffe Startseite: 3 Zugriffe PDF: 9 Zugriffe Startseite: 9 Zugriffe PDF: 14 Zugriffe PDF: 7 Zugriffe Startseite: 2 Zugriffe PDF: 5 Zugriffe Startseite: 3 Zugriffe PDF: 11 Zugriffe PDF: 18 Zugriffe Startseite: 2 Zugriffe PDF: 14 Zugriffe Startseite: 1 Zugriffe PDF: 38 Zugriffe PDF: 35 Zugriffe PDF: 16 Zugriffe PDF: 15 Zugriffe PDF: 12 Zugriffe Startseite: 2 Zugriffe PDF: 17 Zugriffe PDF: 8 Zugriffe Startseite: 2 Zugriffe PDF: 31 Zugriffe PDF: 35 Zugriffe
Jul
11
Aug
11
Oct
11
Nov
11
Dec
11
Jan
12
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
Apr
14
May
14
Jun
14
Jul
14
Aug
14
Sep
14
Oct
14
Monat Jul
11
Aug
11
Oct
11
Nov
11
Dec
11
Jan
12
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
Apr
14
May
14
Jun
14
Jul
14
Aug
14
Sep
14
Oct
14
Startseite 2   5 2 3 5 2   2 7 2 1   6 5       2       3 9   2 3   2 1         2   2  
PDF 5 1 1 7   1 1 2 6 7 10 9 5 16 19 5 13 14 13 12 13 8 9 14 7 5 11 18 14 38 35 16 15 12 17 8 31 35

Gesamtzahl der Zugriffe seit Jul 2011:

  • Startseite – 68 (1.79 pro Monat)
  • PDF – 453 (11.92 pro Monat)
 
 
Generiert am 26.11.2014, 06:46:00