Extremal Problems for Graphs and Hypergraphs Público
Kay, William Walter (2017)
Abstract
We discuss a pair of problems in extremal combinatorics. One establishes asymptotically the chromatic number for a certain family of graphs, and the other investigates a property of oriented k-graphs (Property O).
Table of Contents
Contents
1 Introduction
1.1. Graphs and Hypergraphs . . . . . . . . . . . . . . . . . . . .
. . . . 1
1.1.1Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . 1
1.1.2 Hypergraphs . . . . . . . . . . . . . . . . . . . . . . . . .
. . . 2
1.2 Extremal Combinatorics and an Overview of Results . . . . . . .
. . 2
1.2.1 Chromatic Number . . . . . . . . . . . . . . . . . . . . . .
. . 2
1.2.2 Edge Cardinality . . . . . . . . . . . . . . . . . . . . . .
. . . 3
1.2.3 Overview of Results . . . . . . . . . . . . . . . . . . . . .
. . . 4
1.2.4 Oriented k-Graphs . . . . . . . . . . . . . . . . . . . . . .
. . 5
1.3 Glossary of Technical Terms . . . . . . . . . . . . . . . . . .
. . . . . 6
2 Type Graphs 7
2.1 Preliminaries and Basic Definitions . . . . . . . . . . . . . .
. . . . . 8
2.2 The Block Algorithm . . . . . . . . . . . . . . . . . . . . . .
. . . . . 12
2.3 The Lower Bound - Noncolorability . . . . . . . . . . . . . . .
. . . . 17
2.4 The Upper Bound - Constructing Colorings . . . . . . . . . . .
. . . 19
2.4.1 Embedding Type-Graphs . . . . . . . . . . . . . . . . . . . .
. 20
2.4.2 Coloring the Auxiliary Graphs Gb (n) . . . . . . . . . . . .
. . 22
2.5 Reducible Types . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . 32
2.5.1 Concluding Remarks . . . . . . . . . . . . . . . . . . . . .
. . 35
3 Property O 37
3.1 Property B . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . 37
3.2 Definitions and Overview . . . . . . . . . . . . . . . . . . .
. . . . . . 39
3.3 Proof of Theorem 3.2 . . . . . . . . . . . . . . . . . . . . .
. . . . . . 41
3.4 Proof of Theorem 3.4 . . . . . . . . . . . . . . . . . . . . .
. . . . . . 43
3.4.1 Phase 1: reveal consistent edges . . . . . . . . . . . . . .
. . . 44
3.4.2 Phase 2: reveal inconsistent edges . . . . . . . . . . . . .
. . . 45
3.5 A Construction, Small Values of n, and Problems . . . . . . . .
. . . 47
3.5.1 Concluding Remarks . . . . . . . . . . . . . . . . . . . . .
. .50
Bibliography 51
About this Dissertation
School | |
---|---|
Department | |
Degree | |
Submission | |
Language |
|
Research Field | |
Palabra Clave | |
Committee Chair / Thesis Advisor | |
Committee Members |
Primary PDF
Thumbnail | Title | Date Uploaded | Actions |
---|---|---|---|
Extremal Problems for Graphs and Hypergraphs () | 2018-08-28 15:29:15 -0400 |
|
Supplemental Files
Thumbnail | Title | Date Uploaded | Actions |
---|---|---|---|
ToC.pdf () | 2018-08-28 15:32:07 -0400 |
|