Algorithms, Combinatorics and Optimization Seminar Misha Lavrov
Carnegie Melllon University
Title: 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]ⁿ 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 $\varepsilon$>0) if, for any vertex v, at least (1-$\varepsilon$)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 $\varepsilon$, prove matching upper bounds on d (joint work with Po-Shen Loh).

Date: Thursday, September 22, 2016
Time: 3:30 pm
Location: Wean Hall 8220