On Problems in Extremal Graph Theory and Ramsey Theory 公开

La Fleur, Steven James (2013)

Permanent URL: https://etd.library.emory.edu/concern/etds/2b88qc35p?locale=zh
Published

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
Department
Submission
Language
  • English
Research Field
关键词
Committee Chair / Thesis Advisor
Committee Members
最新修改

Primary PDF

Supplemental Files