Ramsey and Turan-Type Theorems for Hypergraphs 公开

Abstract

This dissertation includes Ramsey and Turan-type results. Both topics involve finding substructures within hypergraphs under certain conditions.

Ramsey-type results: The Induced Ramsey Theorem (1975) states that for c, r ≥ 2 and every r-graph G, there exists an r-graph H such that every c-coloring of the edges of H contains a monochromatic induced copy of G. A natural question to ask is what other subgraphs F (besides edges) of G can be partitioned and have the F-Ramsey property. We give results on the F-Ramsey property of two types of objects: hypergraphs or partial Steiner systems. We find that while the restrictions on the Ramsey properties of hypergraphs are lifted by any linear ordering of the vertex set, the Ramsey properties for partial Steiner systems (with vertex set linearly ordered or unordered) are quite restricted.

Turan-type results: Turan's Theorem (1941) states that for 1 < k ≤ n, every graph G on n vertices not containing a Kk+1 has at most |E(Tk(n))| edges, where Tk(n) is the graph on n vertices obtained by partitioning n vertices into k classes of each size n/k and joining two vertices if and only if they are in two different classes. In 1946, Erdos and Stone showed that any sufficiently large dense graph will contain Tk(n). Nearly 75 years later, in spite of considerable interest and effort, no generalization of Turan's Theorem or Erdos-Stone Theorem for hypergraphs is known. Instead, we consider a variant of this question where we restrict to quasi-random hypergraphs and prove some partial results in this direction.

All results presented in this dissertation are joint work with Vojtech Rodl and some results are joint work with Jaroslav Nesetril.

Table of Contents

1 Introduction. 1

1.1 Ramsey theory and the Ramsey property . 1

1.2 Ramsey-type results. 4

1.2.1 Objects and results. 4

1.2.1.1 Hypergraphs. 5

1.2.1.2 Steiner Systems. 6

1.3 Turan-type results. 8

1.3.1 Results. 9

2 Ramsey Properties for Hypergraphs. 11

2.1 Introduction. 11

2.2 Positive result. 12

2.3 Negative result. 17

2.3.1 V (F) is not independent. 19

3 Ramsey Properties for Steiner Systems. 22

3.1 Introduction. 22

3.2 Positive results. 24

3.2.1 F-Ramsey property for S(r, t) and S<(r, t). 24

3.3 Negative results. 26

3.3.1 Negative results for S(r, t). 26

3.3.2 Negative results for S<(r, t). 29

3.4 Concluding remarks. 30

4 Alternative Positive Direction Proof of Theorem 3.1.5. 32

4.1 Positive results for S<(r, t) (direct proof). 33

4.1.1 The Partite Lemma. 33

4.1.2 The Partite Construction. 39

4.1.3 Proof of Theorem 3.1.5 for other positive cases: F is an edge and |V(F)| < t. 47

5 Upper Density of Quasi-random Hypergraphs 48 5.1 Introduction. 48

5.2 Proof of Theorem 5.1.3. 51

5.2.1 The lower bound. 51

5.2.2 The upper bound for l=3. 56

5.3 Proof of Theorem 5.1.6. 57

5.4 Concluding remarks. 59

Bibliography. 60

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
Degree	PhD
Submission	Dissertation
Language	English
Research Field	Mathematics
关键词	hypergraphs density quasi-random Ramsey theory Steiner systems
Committee Chair / Thesis Advisor	Rodl, Vojtech, Emory University
Committee Members	Duffus, Dwight A, Emory University Gould, Ronald J, Emory University

最新修改

Primary PDF

Thumbnail	Title	Date Uploaded	Actions
	Ramsey and Turan-Type Theorems for Hypergraphs ()	2018-08-28 15:51:03 -0400	Press to Select an action Download

Supplemental Files

Thumbnail	Title	Date Uploaded	Actions