0
$\begingroup$

I'll be as intuitive and hand-wavy as possible so as to get to what I am looking for. Suppose we have a graph $G=(V,E)$. One notion of expansion, namely vertex expansion, can be intuitively described as how much a subset $A$ (of size at most $\|V\|/2$) grows within the graph. Here growth is described using edge connections of the graph, that is

$inf_{A} \frac{\|N_1(A)\|}{\|A\|}$

where $N_1(A)$ is the set of all vertices that can be reached from a vertex in $A$ using atmost one step (edge). This notion of expansion is useful and well-studied.

Is there a generalization of this using two steps, say? That is, let $N_2(A)$ be the vertices reachable from $A$ using at most two steps (or a length 2 path of edges). Then we can define a $2$-expansion $inf_{A} \frac{\|N_2(A)\|}{\|N_1(A)\|}$ In a sense, this describes how much better two steps would be compared to one step. Now for instance if the graph expands and also 2-expands, its like the growth is pretty rapid. We can of course, generalize this to $i$-steps, and if the graph $i$-expands for $i=1,2,3,\dots$, then its a kind of "super" expander where sets grow like crazy.

Now all of this is just an intuition, so I'm curious if any of this makes sense and has been studied. Or its possible its all trivial and useless, reducing to the standard expansion. Please do let me know any references or directions in this regard.

$\endgroup$
2
  • 1
    $\begingroup$ Probably the characterization of expanders in terms of the eigenvalues of the adjacency matrix means that any expander is an $i$-step expander, since control of the eigenvalues of the adjacency matrix gives control of the eigenvalues of its $i$th power. $\endgroup$
    – Will Sawin
    Dec 28, 2021 at 15:21
  • 1
    $\begingroup$ I don't think eigenvalues give good control of vertex expansion. In particular, many CS applications requires expanders with near optimal vertex expansion. That is, d-regular graphs with d(1-eps) vertex expansion. However, there are examples of very good spectral expanders which only reach d/2 vertex expansion. It is an open problem if some spectral notions can guarantee better vertex expansion. $\endgroup$
    – Shachar
    Dec 29, 2021 at 15:25

1 Answer 1

1
$\begingroup$

The relation between vertex expansion and eigenvalues is due to Kahale, and you should look at his full paper in the journal of the ACM (https://www.researchgate.net/publication/2782658_Eigenvalues_and_Expansion_of_Regular_Graphs). There are also shorter versions which do not contain some results.

Let us focus on "small sets", which means that $|A| = o(|V|)$, but it can be more precise. If $A$ is as large as $|V|/2$ the results will be different for obvious reasons. Let $N(A)$ be the set of neighbors of $A$ (including from a set $A$ itself) and let $N^t(A) = N(N^{t-1}(A))$ which is a little different from your notations. Finally, assume that the graph is $d$-regular and is the best spectral expander, i.e., a Ramanujan graph.

Under these conditions, Kahale proves:

  1. (Theorem 2 in the paper) $|N(A)| \ge (d/2-o(1)) |A|$. This is the vertex expansion result Shachar mentioned, and says that the vertex expansion of a ball of radius 1 is the best possible, up to factor 2.
  2. (Theorem 5) $|N^t(A)| \ge (d(d-2)(d-1)^{t-2}/2-o(1))|A|$ (or a bit better than this). If you let $d$ to be large for simplicity, this will say that the vertex expansion of a ball of radius $t$ is the best possible, up to a factor of 2.

The second result implies that if $|N(A)|/|A|$ is $d/2$, then $N(N(A))/N(A)$ should expand by essentially $d-O(1)$, which is the best possible.

Kahale also proves in Theorem 6 that always $|N^2(A)| \ge (2d/3-o(1))|N(A)|$.

He does not generalize this to $|N^t(A)|/|N^{t-1}(A)|$, but it is quite obvious you should expect it to be close to $d-O(1)$ for large $t$. You should perhaps expect bounds of the type $|N^t(A)|/|N^{t-1}(A)| \ge (t/(t+1)+o(1))d$ but I'm not familiar with such a result in the literature.

Stated in other terms, while the vertex expansion of small sets can be quite "bad" even for Ramanujan graphs, the vertex expansion of balls around small sets is quite good.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.