The ACO Seminar (2016–2017)

(1) A version of the Hales-Jewett theorem says that for any t there exists a dimension on such that any two-coloring of the grid [t]ⁿ contains t points on a line that are the same color. Generalizations of this problem lead to the Graham-Rothschild parameter sets theorem; the well-known Graham's number is an upper bound on the dimension required for the first nontrivial instance of the parameter sets theorem.

We prove tighter bounds on the Hales-Jewett number for t=4 as well as on the problem for which Graham's number is an upper bound (the latter is joint work with John Mackey and Mitchell Lee).

(2) An n-vertex graph is considered to be distance-uniform (for a distance d and a tolerance ε>0) if, for any vertex v, at least (1-ε)n of the vertices in the graph are at distance exactly d from v. Random graphs provide easy examples of distance-uniform graphs, with d = O(log n); Alon, Demaine, Hajiaghayi, and Leighton conjectured that this is true for all distance-uniform graphs.

We provide examples of distance-uniform graphs with much larger d, and for sufficiently small ε, prove matching upper bounds on d (joint work with Po-Shen Loh).