Ramsey and TuranType Theorems for Hypergraphs Open Access
Bhat, Vindya Vasanth (2015)
Published
Abstract
This dissertation includes Ramsey and Turantype results. Both topics involve finding substructures within hypergraphs under certain conditions.
Ramseytype results: The Induced Ramsey Theorem (1975) states that for c, r ≥ 2 and every rgraph G, there exists an rgraph H such that every ccoloring 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 FRamsey property. We give results on the FRamsey 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.
Turantype 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 ErdosStone Theorem for hypergraphs is known. Instead, we consider a variant of this question where we restrict to quasirandom 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 Ramseytype results. 4
1.2.1 Objects and results. 4
1.2.1.1 Hypergraphs. 5
1.2.1.2 Steiner Systems. 6
1.3 Turantype 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 FRamsey 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 Quasirandom 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
 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  
Degree  
Submission  
Language 

Research Field  
Keyword  
Committee Chair / Thesis Advisor  
Committee Members 
Primary PDF
Thumbnail  Title  Date Uploaded  Actions 

Ramsey and TuranType Theorems for Hypergraphs ()  20180828 15:51:03 0400 

Supplemental Files
Thumbnail  Title  Date Uploaded  Actions 
