Misha Lavrov (Carnegie Mellon University) Distanceuniform graphs with large diameter Abstract: We say that a graph is epsilondistanceuniform if there is a value d (called the critical distance) such that, for every vertex v, all but an epsilon fraction of the other vertices are at distance exactly d from v. Random graphs are distanceuniform with logarithmic critical distance, and it was conjectured by Alon, Demaine, Hajiaghayi, and Leighton that the critical distance (equivalently, the diameter) of a distanceuniform graph must always be logarithmic. In this talk, we use a generalization of the Towers of Hanoi puzzle to construct distanceuniform graphs with a much larger diameter: for constant epsilon, as large as n^O(1/log log n). We show that this construction is more or less worst possible for sufficiently small epsilon, leaving open the possibility that for large epsilon, much worse cases exist. This is joint work with PoShen Loh. 
