Results in Ramsey Theory and Probabilistic Combinatorics
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  to attack a geometric Ramsey problem due to Graham and Rothschild , 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  to the random setting. Finally, we consider a purely graphtheoretic problem, that of distance-uniform graphs, introduced by Alon et al. in . 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.