An $\epsilon$-distance-uniform graph is one in which from every vertex, all but an $\epsilon$-fraction of the remaining vertices are at some fixed distance $d$, called the critical distance. We consider the maximum possible value of $d$ in an $\epsilon$-distance-uniform graph with $n$ vertices. We show that for $\frac1n \le \epsilon \le \frac1{ \log n}$, there exist $\epsilon$-distance-uniform graphs with critical distance $2^{ \Omega(\frac{ \log n}{ \log \epsilon^{ -1}})}$, disproving a conjecture of Alon et al. that $d$ can be at most logarithmic in $n$. We also show that our construction is best possible, in the sense that an upper bound on $d$ of the form $2^{ O(\frac{ \log n}{ \log \epsilon^{ -1}})}$ holds for all $\epsilon$ and $n$.
Categories: math.CO