Extremal Problems for Graphs and Hypergraphs Öffentlichkeit

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

Rights statement

• Permission granted by the author to include this thesis or dissertation in this repository. All rights reserved by the author. Please contact the author for information regarding the reproduction and use of this thesis or dissertation.

School	Laney Graduate School
Department	Mathematics
Degree	PhD
Submission	Dissertation
Language	English
Research Field	Mathematics
Stichwort	Extremal Combinatorics Discrete Mathematics Chromatic Number
Committee Chair / Thesis Advisor	Rodl, Vojtech, Emory University Duffus, Dwight A, Emory University
Committee Members	Huang, Hao , Emory University

Zuletzt geändert

Primary PDF

Thumbnail	Title	Date Uploaded	Actions
	Extremal Problems for Graphs and Hypergraphs ()	2018-08-28 15:29:15 -0400	Press to Select an action Download

Supplemental Files

Thumbnail	Title	Date Uploaded	Actions
	ToC.pdf ()	2018-08-28 15:32:07 -0400	Press to Select an action Download