On Problems in Extremal Graph Theory and Ramsey Theory Public

Abstract

Extremal graph theory and Ramsey theory are two topics in graph theory with many problems which are being actively investigated. Both subjects involve finding substructures within graphs, or general graph-like structures, under certain conditions.

Table of Contents

1 Introduction 1

1.1 Basic concepts 1

1.2 Extremal Graph Theory 2

1.3 Ramsey Theory 5

1.3.1 Induced Ramsey Numbers 7

1.3.2 Ramsey theory for hypergraphs 7

2 Jumps and non-jumps in multigraphs 8

2.1 Introduction 8

2.2 Preliminaries 10

2.2.1 Globally dense graphs 11

2.2.2 Irreducible Graphs 16

2.3 Proof of Theorem 2.4 17

2.4 Order type 24

2.5 Spectral Prerequisites 29

2.6 Proof of Theorem 2.5 30

3 Ramsey and induced Ramsey results for k-graphs 34

3.1 Introduction 34

3.2 Non-induced Ramsey Numbers 36

3.3 Some Preliminaries 39

3.4 Proof of Theorem 3.2 43

3.5 Proof of Lemma 3.14 45

3.5.1 Proof of Claim 3.21 54

3.6 Proof of Embedding Lemma 56

3.7 A Theorem of Erdos 58

Bibliography 63

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	Math and Computer Science
Submission	Dissertation
Language	English
Research Field	Mathematics
Mot-clé	Extremal Graph Theory Graph Theory Multigraphs Hypergraphs Combinatorics Ramsey Theory
Committee Chair / Thesis Advisor	Rodl, Vojtech, Emory University
Committee Members	Duffus, Dwight A, Emory University Rucinski, Andrzej , Emory University Gould, Ronald J, Emory University

Dernière modification

Primary PDF

Thumbnail	Title	Date Uploaded	Actions
	On Problems in Extremal Graph Theory and Ramsey Theory ()	2018-08-28 11:05:22 -0400	Press to Select an action Download

Supplemental Files

Thumbnail	Title	Date Uploaded	Actions