<p><a href="http://dx.doi.org/10.1109/CCC.2008.24">Eickmeyer and Grohe (2010)</a> prove that your candidate construction can be made explicit: take $d$ somewhat linearly independent linear hash functions $h_1,\dots,h_d$ and connect left vertices $v$ with right vertices $h_1(v),\dots,h_d(v)$. Eickmeyer and Grohe show that this construction gives $(k,\epsilon)$-expanders with left degree $d=k(t-1)/(2\epsilon)$, whenever $t$ is an integer, the left vertex set has size $n=q^t$, the right vertex set has size $m=dq$, and $q>d$ is a prime power. The hash functions $h_1,\dots,h_d$ are chosen in such a way that any $t$ of them are linearly independent.</p>

CC BY-SA 2.5
2010-09-30T11:35:03.527Z
2010-09-30T11:59:38.190Z
2010-09-30T11:59:38.190Z
Holger
<p>I thought that having a look at surveys/talks by Avi Wigderson may help with your question. Here are slides from a recent talk: <a href="http://math.ias.edu/~avi/TALKS/expander_tutorial_June2010.ppt" rel="nofollow noreferrer">Expander Tutorial, June 2010</a>. Constructions start on page 40.</p>

<p>Regarding the space complexity, I think it can be helpful if you specify the operations you need to perform on the graph. If I am not mistaken, some constructions allow operation like computing neighborhood in logspace.</p>

CC BY-SA 3.0
2010-09-27T19:44:53.833Z
2017-12-12T09:31:15.727Z
2017-12-12T09:31:15.727Z
Kaveh
<p>I am looking for unbalanced expanders that are "good" and "space-efficient". Specifically, a bipartite left-regular graph $G=(A,B,E)$, $|A|=n$, $|B|=m$, with left degree $d$ is a $(k,\epsilon)$-expander if for any $S \subset A$ of size at most $k$, the number of distinct neighbors of $S$ in $B$ is at least $(1-\epsilon)d|S|$. It is known that the probabilistic method yields such a graph with $d=O(\log (n/k)/\epsilon)$ and $m=O(k \log(n/k)/\epsilon^2)$. However, one needs $O(n d)$ space to store such a graph. Also one also needs to access this storage when doing anything with the graph, which can cost as well. Ideally, one would like an explicit construction. However, as far as I know, known constructions achieve parameters that are still somewhat far from the above (at least provably so). </p>

<p>My question: <em>are there any other constructions, possibly non-explicit, which achieve bounds "closer" to the ones above, yet use "significantly less" than $O(nd)$ space ?</em> </p>

<p>I am looking for answers in any of these three categories: (a) theorems (b) conjectures (c) observations and "war-stories" such as "we did this and it kind of seemed to work (sort of)". I.e., "industrial" expanders are OK. I prefer (a) over (b) and (b) over (c), but beggars cannot be choosers :) </p>

<p>Here is an example of a construction of type (c). Take $d$ random linear hash functions $h_i: [n] \to [m]$ (mod $m$), and connect each vertex $i$ to $h_1(i) \ldots h_d(i)$. Me and my student did some experiments on it, and it seemed to work "fine". Are there any theorems or conjectures about this or related constructions ?</p>

<p>Thanks!</p>

CC BY-SA 3.0
2012-02-21T08:25:04.577Z
Have you looked at the Guruswami-Umans-Vadhan construction? I am wondering why it does not satisfy your requirement.
Zeyu
CC BY-SA 2.5
2010-09-13T09:55:41.190Z
This is a great question, but there seem to be no answers!  Is no-one using expanders other than as a magic wand to make proofs work?  I thought some types of Ramanujan graphs were quite simple to construct.
András Salamon
CC BY-SA 2.5
2010-09-20T05:09:43.160Z
Ramanujan graphs are indeed relatively easy to construct, but they are *balanced*, i.e.,  m=n.
Piotr
<graph-theory><derandomization><expanders>
Space efficient "industrial" unbalanced expanders
Piotr
# Space efficient "industrial" unbalanced expanders

(Asked by: username_0 on 2010-08-25)

I am looking for unbalanced expanders that are "good" and "space-efficient". Specifically, a bipartite left-regular graph $G=(A,B,E)$, $|A|=n$, $|B|=m$, with left degree $d$ is a $(k,\epsilon)$-expander if for any $S \subset A$ of size at most $k$, the number of distinct neighbors of $S$ in $B$ is at least $(1-\epsilon)d|S|$. It is known that the probabilistic method yields such a graph with $d=O(\log (n/k)/\epsilon)$ and $m=O(k \log(n/k)/\epsilon^2)$. However, one needs $O(n d)$ space to store such a graph. Also one also needs to access this storage when doing anything with the graph, which can cost as well. Ideally, one would like an explicit construction. However, as far as I know, known constructions achieve parameters that are still somewhat far from the above (at least provably so).

My question: *are there any other constructions, possibly non-explicit, which achieve bounds "closer" to the ones above, yet use "significantly less" than $O(nd)$ space ?*

I am looking for answers in any of these three categories: (a) theorems (b) conjectures (c) observations and "war-stories" such as "we did this and it kind of seemed to work (sort of)". I.e., "industrial" expanders are OK. I prefer (a) over (b) and (b) over (c), but beggars cannot be choosers :)

Here is an example of a construction of type (c). Take $d$ random linear hash functions $h\_i: [n] \to [m]$ (mod $m$), and connect each vertex $i$ to $h\_1(i) \ldots h\_d(i)$. Me and my student did some experiments on it, and it seemed to work "fine". Are there any theorems or conjectures about this or related constructions ?

Thanks!

**Tags:** graph-theory, derandomization, expanders

> **Comments:**
> **username_2**: This is a great question, but there seem to be no answers!  Is no-one using expanders other than as a magic wand to make proofs work?  I thought some types of Ramanujan graphs were quite simple to construct.  
> **username_0**: Ramanujan graphs are indeed relatively easy to construct, but they are *balanced*, i.e.,  m=n.  
> **username_1**: Have you looked at the Guruswami-Umans-Vadhan construction? I am wondering why it does not satisfy your requirement.  

---

## 2 answers

### Answer by username_3 on 2010-09-30. Score: 10

[Eickmeyer and Grohe (2010)](http://dx.doi.org/10.1109/CCC.2008.24) prove that your candidate construction can be made explicit: take $d$ somewhat linearly independent linear hash functions $h\_1,\dots,h\_d$ and connect left vertices $v$ with right vertices $h\_1(v),\dots,h\_d(v)$. Eickmeyer and Grohe show that this construction gives $(k,\epsilon)$-expanders with left degree $d=k(t-1)/(2\epsilon)$, whenever $t$ is an integer, the left vertex set has size $n=q^t$, the right vertex set has size $m=dq$, and $q>d$ is a prime power. The hash functions $h\_1,\dots,h\_d$ are chosen in such a way that any $t$ of them are linearly independent.


---

### Answer by username_4 on 2010-09-27. Score: 5

I thought that having a look at surveys/talks by Avi Wigderson may help with your question. Here are slides from a recent talk: [Expander Tutorial, June 2010](http://math.ias.edu/~avi/TALKS/expander_tutorial_June2010.ppt). Constructions start on page 40.

Regarding the space complexity, I think it can be helpful if you specify the operations you need to perform on the graph. If I am not mistaken, some constructions allow operation like computing neighborhood in logspace.


---

