EXPANDERS WITH RESPECT TO HADAMARD SPACES AND RANDOM GRAPHS

摘要

It is shown that there exist a sequence of 3-regular graphs {G(n)}(n=1)(infinity) and a Hadamard space X such that {G(n)}(n=1)(infinity) forms an expander sequence with respect to X, yet random regular graphs are not expanders with respect to X. This answers a question of the second author and Silberman. The graphs {G(n)}(n=1)(infinity) are also shown to be expanders with respect to random regular graphs, yielding a deterministic sublinear-time constant-factor approximation algorithm for computing the average squared distance in subsets of a random graph. The proof uses the Euclidean cone over a random graph, an auxiliary continuous geometric object that allows for the implementation of martingale methods.