edoc-Server der Humboldt-Universität zu Berlin

Dissertation

Autor(en): Yury Person
Titel: Quasi-random hypergraphs and extremal problems for hypergraphs
Gutachter: Mihyun Kang; Mathias Schacht; Angelika Steger
Erscheinungsdatum: 06.12.2010
Volltext: pdf (urn:nbn:de:kobv:11-100179106)
Fachgebiet(e): Mathematik
Schlagwörter (ger): Extremale Kombinatorik, Hypergraphen, Regularitätslemmata, Stabilitätsmethode, Quasi-Zufälligkeit
Schlagwörter (eng): extremal combinatorics, hypergraphs, regularity lemmas, stability method, quasi-randomness
Einrichtung: Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II
Lizenz: Namensnennung - Keine kommerzielle Nutzung - Keine Bearbeitung (CC BY NC ND)
Zitationshinweis: Person, Yury: Quasi-random hypergraphs and extremal problems for hypergraphs; Dissertation, Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II , publiziert am 06.12.2010, urn:nbn:de:kobv:11-100179106
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):
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-uniforme Hypergraphen verallgemeinert und somit eine Reihe äquivalenter Eigenschaften bestimmt. Basierend auf diesen Resultaten werden nichtbipartite Graphen gefunden, welche die Quasi-Zufälligkeit für Graphen ``forcieren''''. Zuvor waren nur bipartite 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 Hypergraphen 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) Hypergraphen richtig färbt. Schließlich wird die folgende extremale Funktion studiert. Es sind r Farben gegeben sowie ein k-uniformer Hypergraph F. Auf wie viele verschiedene Arten kann man die Kanten eines k-uniformen Hypergraphen H färben, so dass keine monochromatische 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 Hypergraphen F, deren extremaler 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.
Abstract (eng):
This thesis presents first one possible generalization of the result of Chung, Graham 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 bipartite. 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.
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: 28 Zugriffe PDF: 32 Zugriffe Startseite: 4 Zugriffe PDF: 6 Zugriffe Startseite: 2 Zugriffe PDF: 7 Zugriffe Startseite: 2 Zugriffe PDF: 11 Zugriffe PDF: 8 Zugriffe PDF: 17 Zugriffe PDF: 21 Zugriffe PDF: 20 Zugriffe PDF: 9 Zugriffe Startseite: 2 Zugriffe PDF: 6 Zugriffe PDF: 8 Zugriffe PDF: 4 Zugriffe PDF: 5 Zugriffe PDF: 11 Zugriffe PDF: 13 Zugriffe PDF: 32 Zugriffe PDF: 18 Zugriffe Startseite: 1 Zugriffe PDF: 26 Zugriffe PDF: 21 Zugriffe PDF: 21 Zugriffe PDF: 16 Zugriffe Startseite: 2 Zugriffe PDF: 15 Zugriffe Startseite: 3 Zugriffe PDF: 23 Zugriffe PDF: 22 Zugriffe Startseite: 2 Zugriffe PDF: 29 Zugriffe PDF: 28 Zugriffe Startseite: 2 Zugriffe PDF: 36 Zugriffe Startseite: 2 Zugriffe PDF: 26 Zugriffe PDF: 20 Zugriffe PDF: 19 Zugriffe Startseite: 1 Zugriffe PDF: 25 Zugriffe Startseite: 2 Zugriffe PDF: 37 Zugriffe PDF: 23 Zugriffe
Jul
11
Aug
11
Sep
11
Oct
11
Nov
11
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
Apr
14
May
14
Jun
14
Monat Jul
11
Aug
11
Sep
11
Oct
11
Nov
11
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
Apr
14
May
14
Jun
14
Startseite 2   4 2 2           2               1       2 3   2   2 2     1 2  
PDF 28 32 6 7 11 8 17 21 20 9 6 8 4 5 11 13 32 18 26 21 21 16 15 23 22 29 28 36 26 20 19 25 37 23

Gesamtzahl der Zugriffe seit Jul 2011:

  • Startseite – 27 (0.79 pro Monat)
  • PDF – 643 (18.91 pro Monat)
 
 
Generiert am 22.07.2014, 23:42:59