Expanders with respect to Hadamard spaces and random graphs

Abstract

It is shown that there exists a sequence of 3-regular graphs $\{G_n{\}}_{n=1}^{\infty }$ and a Hadamard space $X$ such that $\{G_n{\}}_{n=1}^{\infty }$ forms an expander sequence with respect to $X$, yet random regular graphs are not expanders with respect to $X$. This answers a question of \cite{NS11}. $\{G_n{\}}_{n=1}^{\infty }$ 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.

incorporated Referees' comments

References in corpus (4)

• Nonlinear spectral calculus and super-expanders
• Euclidean quotients of finite metric spaces
• Spectral calculus and Lipschitz extension for barycentric metric spaces
• L_1 embeddings of the Heisenberg group and fast estimation of graph isoperimetry

Cited by in corpus (13)

• Nonlinear spectral calculus and super-expanders
• Spectral calculus and Lipschitz extension for barycentric metric spaces
• An average John theorem
• Nonpositive curvature is not coarsely universal
• Logarithmic girth expander graphs of $S{L}_n({\mathbb{F}}_p)$
• Snowflake universality of Wasserstein spaces
• Group approximation in Cayley topology and coarse geometry, Part II: Fibered coarse embeddings
• Rigidity of warped cones and coarse geometry of expanders
• Metric $X_p$ inequalities
• On expansion of $G_{n,d}$ with respect to $G_{m,d}$
• Bounds on Geometric Eigenvalues of Graphs
• Talagrand's influence inequality revisited
• From Average Embeddings To Nearest Neighbor Search