Ramsey and Turan-Type Theorems for Hypergraphs Public
Bhat, Vindya Vasanth (2015)
Published
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
School | |
---|---|
Department | |
Degree | |
Submission | |
Language |
|
Research Field | |
Mot-clé | |
Committee Chair / Thesis Advisor | |
Committee Members |
Primary PDF
Thumbnail | Title | Date Uploaded | Actions |
---|---|---|---|
|
Ramsey and Turan-Type Theorems for Hypergraphs () | 2018-08-28 15:51:03 -0400 |
|
Supplemental Files
Thumbnail | Title | Date Uploaded | Actions |
---|