Results in Ramsey Theory and Probabilistic Combinatorics.pdf (683.88 kB)

Results in Ramsey Theory and Probabilistic Combinatorics

Download (683.88 kB)
thesis
posted on 01.04.2017 by Mikhail Lavrov

This thesis addresses several questions in Ramsey theory and in probabilistic combinatorics. We begin by considering several questions related to the Hales–Jewett Theorem, a central result in the study of Ramsey theory. We use bounds due to Shelah [46] to attack a geometric Ramsey problem due to Graham and Rothschild [28], improving on the the previous bound known as Graham’s number (which at one point held the Guinness world record for the largest number used in a mathematical proof). Extending ideas developed in studying that question, we obtain a bound of less than1011 on the Hales–Jewett number HJ(4; 2). Next, we consider problems in random graphs, and especially the use of random structures in solving extremal problems. We begin by a classical random graph result, analyzing an invariant called the game chromatic number for the random 3-regular graph Gn,3. Then, we extend the increasing paths problem posed by Graham and Kleitman [27] to the random setting. Finally, we consider a purely graphtheoretic problem, that of distance-uniform graphs, introduced by Alon et al. in [2]. Here, we prove a marked difference between the behavior of random graphs which are distance-uniform, and worst-case behavior of distance-uniform graphs, constructing a family of distance-uniform graphs which are separated by an exponential gap from the random example.

History

Date

01/04/2017

Degree Type

Dissertation

Department

Mathematical Sciences

Degree Name

Doctor of Philosophy (PhD)

Advisor(s)

Po-Shen Loh

Exports

Exports