pith. sign in

arxiv: 1506.02614 · v1 · pith:UEEEUSU3new · submitted 2015-06-08 · 🧮 math.CO

On expansion of G_(n, d) with respect to G_(m, d)

classification 🧮 math.CO
keywords graphexpansionfixedinftymetricrandomregularspace
0
0 comments X
read the original abstract

In several works, Mendel and Naor have introduced and developed theory surrounding a nonlinear expansion constant similar to the spectral gap for sequences of graphs, in which one considers embeddings of a graph $G$ into a metric space $X$ \cite{mendel2010towards, mendel2013nonlinear, mendel2014expanders}. Here, we investigate the open question of whether the random regular graph $G_{n, d}$ is an expander when embedded into the metric space of a random regular graph $G_{m, d}$ a.a.s., where $m\leq n$. We show that if $m$ is fixed, the answer is affirmative. In addition, when $m\to \infty$, we provide partial solutions to the problem in the case that $d$ is fixed or that $d\to \infty$ under the constraint $d=o(m^{1/2})$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.