Vertex expander bounded

Question

Let $G_1$, $G_2$, . . . be a family of ε-vertex expanders on $n_1$, $n_2$, . . . vertices. Show that there is a constant c such that eventually the diameter of $G_j$ is bounded from above by c · log($n_j$).

The definition of ε-vertex expanders I am using is as following: a sequence $G_1$, $G_2$, . . . of k-regular graphs on vertex sets $V_1$, $V_2$, . . . is called a family of ε-vertex expanders if |$V_j$ | goes to infinity and for all sets S ⊂ Vj of at most half the vertices, we have |$N(S) \cup S$| ≥ (1 + ε)|$S$|.

So I have to show that any two vertices in $G_j$ are connected by a path of length at most c · log($n_j$ ) for ay graph in the family but I am not sure where to start. I am thinking of using eigenvalues as the max eigenvalue of k-regular graph is k. I'm not sure if lemma 4.22 in http://home.iiserb.ac.in/~kashyap/Group/thesis_ashwin.pdf is similar to what i am trying to show here; that is the only close result i found. Any hint or help is appreciated.

Answer 1

$\newcommand{\eps}{\varepsilon}$ $\newcommand{\diam}{\operatorname{diam}}$

There is actually no need to work with a sequence of graphs here. It suffices to fix a single graph $G$ and establish the following result.

Suppose that $G$ is an $\eps$-vertex expander, ie $|N(S) \cup S| \ge (1 + \eps) |S|$ with $|S| \le \tfrac12 |G|$. Then there exists a constant $c$, depending only on $\eps$, such that $\diam G \le c \log |G|$.

You missed the condition "$|S| \le \tfrac12 |G|$". This is crucial. Otherwise take $S := G$ and you get some set $N(G) \cup G$ of size larger than $|G|$!

Let's abbreviate $n := |G|$, as you have. We are going to define a sequence of nested sets $(B_k)_{k=0}^\infty$ and $(B'_k)_{k=0}^\infty$, each a subset of the vertex set of $G$.

• Fix an arbitrary $x \in G$ and set $B_0 := \{x\}$. In a rather obscure way of thinking about things, $B_0$ is the set of all vertices at distance at most $0$ from $x$.
• Now set $B_1 := N(\{x\}) \cup \{x\}$. This is the set of all vertices at distance at most $1$ from $x$, ie the neighbourhood of $x$ along with $x$ itself.
• The neighbourhood of the neighbourhood is all those at distance at most $2$. So set $B_2 := N(B_1) \cup B_1 = N^2(\{x\}) \cup N(\{x\}) \cup \{x\}$.
• Given $B_0, ..., B_{k-1}$, define $B_k := N(B_{k-1}) \cup B_{k-1}$.
• This way, $B_k$ is always the set of vertices at distance at most $k$ from $x$.

Similarly, fix an arbitrary $y \in G$ and define $(B'_k)_{k=0}^\infty$ analogously, but with respect to $y$. We want to find some $k$ so that $B_k \cap B'_k \ne \emptyset$. This means that there is a path from $x$ to $y$ of length at most $2k$.

Let's estimate the size of these sets. Suppose that $|B_{k-1}| \le \tfrac12 n$. Then our expander definition says that $$ |B_k| \ge (1 + \eps) |B_{k-1}| \ge \cdots \ge (1 + \eps)^k. $$ We always have $|B_k| \ge |B_{k-1}| + 1$ since $B_k \supsetneqq B_{k-1}$, unless $B_{k-1} = G$. Thus $$ |B_k| \ge \min\{\tfrac12 n +1, (1 + \eps)^k \}. $$ Now choose $k$ so that $(1 + \eps)^k \ge \tfrac23 n$; such a $k$ satisfies $k \le c \log n$ for some constant $c$ depending only on $\eps$. Now, for such a $k$, we have $$ \min\{ |B_k|, |B'_k| \} > \tfrac12 n. $$ Two sets taking up more than half of the vertices must intersect, ie $B_k \cap B'_k \ne \emptyset$. In particular, there is a path between $x$ and $y$ of length at most $2k \le 2 c \log n$. The proof is complete.