## Abstract

It is shown that there exist a sequence of 3-regular graphs {G_{n}}^{∞}_{n}=1 and a Hadamard space X such that {G_{n}}^{∞}_{n}=1 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 are also shown to be expanders with respect to random regular graphs, yielding a deterministic sublineartime 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.

Original language | English (US) |
---|---|

Pages (from-to) | 1471-1548 |

Number of pages | 78 |

Journal | Duke Mathematical Journal |

Volume | 164 |

Issue number | 8 |

DOIs | |

State | Published - 2015 |

## All Science Journal Classification (ASJC) codes

- Mathematics(all)