Regular partitions of hypergraphs and property testing [Elektronische Ressource] / Mathias Schacht. Gutachter: Susanne Albers ; Noga Alon ; Mihyun Kang

Mathias Schacht Ph.D.

Sujets

• Informatik

Informations

• Publié par: humboldt-universitat_zu_berlin
• Publié le: 01 janvier 2010
• Nombre de lectures: 24
• Langue: Deutsch
• Poids de l'ouvrage: 1 Mo

Extrait

Regular partitions of hypergraphs and property testing
H a b il i t a ti o n s sc h r i ft
zur Erlangung der Lehrbefähigung
für das Fach Informatik
vorgelegt
dem Rat der Mathematisch-Wissenschaftlichen Fakultät II
der Humboldt-Universität zu Berlin
von
Mathias Schacht, Ph.D.
geboren am 08.04.1977 in Berlin
Präsident der Humboldt-Universität zu Berlin:
Prof. Dr. Dr. h.c. Christoph Markschies
Dekan der Mathematisch-Wissenschaftlichen Fakultät II:
Prof. Dr. Peter Frensch
Gutachter:
1. Prof. Dr. Susanne Albers
2. Prof. Dr. Noga Alon
3. Priv.-Doz. Dr. Mihyun Kang
Antrag auf Zulassung zum Habilitationsverfahren: 25.06.2009
Zulassung zum Habilitationsverfahren: 06.07.2009
Annahme der schriftlichen Habilitationsleistung: 23.11.2009
Öffentlicher Vortrag: 15.01.2010Zusammenfassung
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 extre-
malen Graphentheorie, aber auch in der theoretischen Informatik und der kombina-
torischen Zahlen 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, un-
terscheidet.
iiAbstract
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 the-
ory, 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 reg-
ularity 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
anditsapplicationtoproblemsintheoreticalcomputerscience. Inparticular, wewill
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.
iiiContents
1 Introduction 1
1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 Regularity lemma for graphs . . . . . . . . . . . . . . . . . . . . . 2
1.1.2 Removal lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Summary of results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.1 Variants of the regularity lemma for graphs . . . . . . . . . . . . . 4
1.2.2 The weak regularity lemma for hypergraphs . . . . . . . . . . . . . 4
1.2.3 Strong regular partitions of hypergraphs . . . . . . . . . . . . . . . 8
1.2.4 Generalizations of the removal lemma . . . . . . . . . . . . . . . . 8
1.2.5 Property Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2.6 Regularity method for sparse graphs . . . . . . . . . . . . . . . . . 12
2 Regularity lemmas for graphs 17
2.1 The Frieze-Kannan lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2 Szemerédi’s regularity lemma . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3 The (ε,r)-regularity lemma . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.4 The regularity lemma of Alon et al. . . . . . . . . . . . . . . . . . . . . . . 28
2.5 The regular approximation lemma . . . . . . . . . . . . . . . . . . . . . . 29
2.6 An early version of the regularity lemma . . . . . . . . . . . . . . . . . . . 31
2.7 Reduced graph and counting lemmas . . . . . . . . . . . . . . . . . . . . . 32
2.8 The global counting lemma . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.9 The local counting lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.10 The removal lemma for graphs . . . . . . . . . . . . . . . . . . . . . . . . 39
2.11 Graph limits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3 The weak regularity lemma for hypergraphs 45
3.1 Counting lemma for linear hyp . . . . . . . . . . . . . . . . . . . 45
3.2 Quasi-random hypergraphs . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.3 Universal hypergraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.4 Non-universal hypergraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4 Strong regular partitions of hypergraphs 53
4.1 Statements of the regularity lemmas . . . . . . . . . . . . . . . . . . . . . 53
4.1.1 Regular complexes and partitions . . . . . . . . . . . . . . . . . . . 54
4.1.2 Hypergraph regularity lemmas . . . . . . . . . . . . . . . . . . . . 56
4.1.3 Hyp counting . . . . . . . . . . . . . . . . . . . . . 58
vContents
4.2 Auxiliary results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.2.1 The dense counting and extension lemma . . . . . . . . . . . . . . 60
4.2.2 Facts concerning regular hypergraphs . . . . . . . . . . . . . . . . 67
4.3 Outline of the proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.4 Proof of: RL(k) =⇒ RAL(k) . . . . . . . . . . . . . . . . . . . . . . . . . 75
4.4.1 Lemma 4.38 and RL(k) imply RAL(k) . . . . . . . . . . . . . . . . 75
4.4.2 RL(k) implies Lemma 4.38 . . . . . . . . . . . . . . . . . . . . . . 83
4.5 Proof of: RAL(k) =⇒ RL(k + 1) . . . . . . . . . . . . . . . . . . . . . . . 99
4.5.1 The index of a partition . . . . . . . . . . . . . . . . . . . . . . . . 99
4.5.2 Proof of RL(k + 1) . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
4.5.3 Proof of the index pumping lemma . . . . . . . . . . . . . . . . . . 114
4.6 Proofs of the counting lemmas . . . . . . . . . . . . . . . . . . . . . . . . 125
5 Property testing and the removal lemma 131
5.1 The Rödl-Skokan lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
5.1.1 Counting . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
5.1.2 Regularity lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
5.2 Auxiliary lemmas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
5.2.1 Cluster hypergraphs. . . . . . . . . . . . . . . . . . . . . . . . . . . 135
5.2.2 Index of a partition . . . . . . . . . . . . . . . . . . . . . . . . . . 140
5.3 Proof of the general removal lemma . . . . . . . . . . . . . . . . . . . . . 142
5.3.1 Proof of Theorem 1.19 . . . . . . . . . . . . . . . . . . . . . . . . . 142
5.3.2 Proof of Lemma 5.16 . . . . . . . . . . . . . . . . . . . . . . . . . . 146
6 Sparse partition universal graphs 155
6.1 The sparse regularity lemma . . . . . . . . . . . . . . . . . . . . . . . . . . 155
6.2 The hereditary nature of sparse regularity . . . . . . . . . . . . . . . . . . 156
6.3 Properties of the random graph . . . . . . . . . . . . . . . . . . . . . . . . 157
6.3.1 Uniform edge distribution . . . . . . . . . . . . . . . . . . . . . . . 157
6.3.2 Expansion properties of neighbourhoods . . . . . . . . . . . . . . . 157
6.3.3 Hereditary nature of (ε,α,p)-denseness . . . . . . . . . . . . . . . . 159
6.4 Ramsey universal graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
6.4.1 Proof of Theorem 1.23 . . . . . . . . . . . . . . . . . . . . . . . . . 165
6.4.2 Proof of Lemma 6.14 . . . . . . . . . . . . . . . . . . . . . . . . . . 166
vi1 Introduction
1.1 Background
Themainfocusofthisthesisconcernsthedevelopmentoftheso-calledregularitymethod
and its applications. Szemerédi’s regularity lemma for graphs is one of the most impor-
tant tools in extremal graph theory. It has many applications not only in graph theory,
but also in combinatorial number theory, discrete