Quasi-random hypergraphs and extremal problems for hypergraphs [Elektronische Ressource] / Yury Person

Herr Dipl.-Math. Univ. Yury Person

Sujets

• Mathematics

Informations

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

Extrait

Quasi-Random Hypergraphs and Extremal Problems for
Hypergraphs
DISSERTATION
zur Erlangung des akademischen Grades
doctor rerum naturalium
(Dr. rer. nat.)
im Fach Informatik
eingereicht an der
Mathematisch-Naturwissenschaftlichen Fakultät II
Humboldt-Universität zu Berlin
von
Herr Dipl.-Math. Univ. Yury Person
Präsident der Humboldt-Universität zu Berlin:
Prof. Dr. Dr. h.c. Christoph Markschies
Dekan der Mathematisch-Naturwissenschaftlichen Fakultät II:
Prof. Dr. Peter Frensch
Gutachter:
1. PD Dr. Mihyun Kang
2. Prof. Dr. Mathias Schacht
3. Prof. Dr. Angelika Steger
eingereicht am: 23.06.2010
Tag der mündlichen Prüfung: 22.11.2010to my motherZusammenfassung
Das Regularitätslemma ist ein zentrales Werkzeug aus der Extremalen Graphen-
theorie mit Anwendungen in der Additiven Zahlentheorie, der Diskreten Geometrie
und der Theoretischen Informatik. Dieses Lemma war ein zentraler Hilfssatz in Sze-
merédis Beweis der zahlentheoretischen Vermutung von Erdős und Turán, dass jede
Teilmenge der natürlichen Zahlen mit positiver oberer Dichte arithmetische Progres-
sionen beliebiger endlicher Länge enthält.
Das Regularitätslemma besagt, dass man die Knotenmenge jedes Graphen in kon-
stant viele fast gleich große Teilmengen partitionieren kann, so dass die meisten auf
je zwei solcher Teilmengen induzierten bipartiten Graphen quasi-zufällig sind. Die
systematische Theorie quasi-zufälliger Graphen wurde von Thomason initiiert und
etwas später haben Chung, Graham und Wilson verschiedene Eigenschaften quasi-
zufälliger Graphen studiert und deren Äquivalenz im approximativen Sinne bewie-
sen. Im Weiteren wurde die Untersuchung der Quasi-Zufälligkeit auf andere diskre-
te Strukturen ausgedehnt. Heutzutage existieren mehrere Regularitätslemmata für
Graphen und Hypergraphen, die deren Zerlegung in quasi-zufällige Teile guarantie-
ren.DabeiwerdenunterschiedlicheAusprägungenvonquasi-zufälligenEigenschaften
zu Grunde gelegt.
In dieser Arbeit wird zuerst das Theorem von Chung, Graham und Wilson über
quasi-zufällige Graphen zur sogenannten schwachen Quasi-Zufälligkeit für k-uni-
forme Hypergraphen verallgemeinert und somit eine Reihe äquivalenter Eigenschaf-
ten bestimmt. Basierend auf diesen Resultaten werden nichtbipartite Graphen ge-
funden, welche die Quasi-Zufälligkeit für Graphen “forcieren”. Zuvor waren nur bi-
partite Graphen mit dieser Eigenschaft bekannt. Desweiteren ist ein konzeptionell
einfacher Algorithmus zum Verifizieren nicht erfüllbarer zufälliger k-SAT Formeln
angegeben.
Dann richtet sich der Fokus auf Anwendungen verschiedener Regularitätslemmata
für Hypergraphen. Zuerst wird die Menge aller bezeichneten 3-uniformen Hypergra-
phen auf n Knoten, die keine Kopie des Hypergraphen der Fano Ebene enthalten,
studiert. Es wird gezeigt, dass fast jedes Element aus dieser Menge ein bipartiter
Hypergraph ist. Dies führt zu einem Algorithmus, der in polynomiell erwarteter Zeit
einen zufälligen Fano-freien (und somit einen zufälligen bipartiten 3-uniformen) Hy-
pergraphen richtig färbt.
Schließlich wird die folgende extremale Funktion studiert. Es sind r Farben ge-
geben sowie ein k-uniformer Hypergraph F. Auf wie viele verschiedene Arten kann
man die Kanten einesk-uniformen HypergraphenH färben, so dass keine monochro-
matische Kopie von F entsteht? Welche Hypergraphen H maximieren die Anzahl
erlaubter Kantenfärbungen? Hier wird ein strukturelles Resultat für eine natürliche
Klasse von Hypergraphen bewiesen. Es wird für viele HypergraphenF, deren extre-
maler Hypergraph bekannt ist, gezeigt, dass im Falle von zwei oder drei Farben die
extremalen Hypergraphen die oben beschriebene Funktion maximieren, während für
vier oder mehr Farben andere Hypergraphen mehr Kantenfärbungen zulassen.
vAbstract
The regularity lemma was originally developed by Szemerédi in the seventies as a
tool to resolve a long standing conjecture of Erdős and Turán, that any subset of the
integers of positive upper density contains arbitrary long arithmetic progressions.
Soon this lemma was recognized as an important tool in extremal graph theory
and it also has had applications to additive number theory, discrete geometry and
theoretical computer science. It roughly says that one can partition a vertex set of
any graph into constantly many parts almost all of which look random-like. This
random-like behaviour is referred to as quasi-randomness. More generally, the sys-
tematicstudyofquasi-randomgraphswasinitiatedbyThomasonand, subsequently,
Chung, Graham and Wilson collected several disparate properties of random graphs
that all turned out to be equivalent in a deterministic sense. Later on, quasi-random
properties were studied for various discrete structures.
This thesis presents first one possible generalization of the result of Chung, Gra-
ham and Wilson to k-uniform hypergraphs, and studies the so-called weak quasi-
randomness. As applications we obtain a simple strong refutation algorithm for
random sparse k-SAT formulas and we identify first non-bipartite forcing pairs for
quasi-random graphs.
Our focus then shifts from the study of quasi-random objects to applications
of different versions of the hypergraph regularity lemmas; all these versions assert
decompositions of hypergraphs into constantly many quasi-random parts, where the
meaning of “quasi-random” takes different contexts in different situations.
We study the family of hypergraphs not containing the hypergraph of the Fano
plane as a subhypergraph, and show that almost all members of this family are bi-
partite. As a consequence an algorithm for coloring bipartite 3-uniform hypergraphs
with average polynomial running time is given.
Then the following combinatorial extremal problem is considered. Suppose one
is given r colors and a fixed hypergraph F. The question is: In at most how many
ways can one color the hyperedges of a hypergraph H on n vertices such that no
monochromatic copy of F is created? What are the extremal hypergraphs for this
function? Here a structural result for a natural family of hypergraphs F is proven.
For some special classes of hypergraphs we show that their extremal hypergraphs
(for large n) maximize the number of edge colorings for 2 and 3 colors, while for at
least 4 colors other hypergraphs are optimal.
viiContents
1 Introduction 1
1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Main results: a guide to the thesis . . . . . . . . . . . . . . . . . . . . . . 2
1.2.1 Weak quasi-randomness for uniform hypergraphs . . . . . . . . . . 2
1.2.2 Almost all hypergraphs without Fano planes are bipartite . . . . . 8
1.2.3 Restricted hyperedge coloring problems . . . . . . . . . . . . . . . 11
2 Tools 17
2.1 Notation and preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.1.1 Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.1.2 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.1.3 Hypergraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.1.4 Extremal problems for hypergraphs . . . . . . . . . . . . . . . . . 20
2.1.5 Some further conventions and notations . . . . . . . . . . . . . . . 22
2.2 Szemerédi’s regularity lemma . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3 The weak hypergraph regularity lemma . . . . . . . . . . . . . . . . . . . 25
2.4 The strong hypy of Rödl and Schacht . . . . . . . 27
2.4.1 Complexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.4.2 Partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.4.3 Equitability and regular hypergraphs . . . . . . . . . . . . . . . . . 29
2.4.4 The regularity and counting lemmas . . . . . . . . . . . . . . . . . 30
2.4.5 Cluster hypergraphs and slices . . . . . . . . . . . . . . . . . . . . 31
2.5 Tools from probability theory . . . . . . . . . . . . . . . . . . . . . . . . . 32
3 Weak quasi-randomness for uniform hypergraphs 35
3.1 Equivalent properties for weak quasi-randomness . . . . . . . . . . . . . . 35
3.1.1 Generalization of Theorem 1.1 . . . . . . . . . . . . . . . . . . . . 35
3.1.2 Forcing pairs for graphs . . . . . . . . . . . . . . . . . . . . . . . . 42
3.1.3 Hereditary subgraphs properties . . . . . . . . . . . . . . . . . . . 42
3.1.4 Partite versions of DISC . . . . . . . . . . . . . . . . . . . . . . . . 43
3.2 Proof of Theorem 1.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.2.1 Simple facts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.2.2 MIN implies DISC . . . . . . . . . . . . . . . . . . . . . . . . . . 47d d
3.2.3 DEV DISC . . . . . . . . . . . . . . . . . . . . . . . . . . 50d d
3.2.4 Equivalence of MIN and MDEG . . . . . . . . . . . . . . . . . . 52d d
3.2.5 DEV implies CL . . . . . . . . . . . . . . . . . . . . . . . . . . . 55d d
ixContents
3.3 Proof of Theorem 3.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.3.1 HCL implies HCL . . . . . . . . . . . . . . . . . . . . . . . 59d,F,α d,F
3.3.2 HCL DISC . . . . . . . . .