Sep. 22, 3:30pm, Wean 8220

Misha Lavrov, CMU

Improving lower and upper bounds

Misha Lavrov, CMU

Improving lower and upper bounds

Abstract:

(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*]^{n} 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).