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 [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 than10¹¹ 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 G_n,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.