<p>This is a family of expander graphs: let $p$ be a prime, let the vertex set be $\{ 0,\ldots,p-1\}$, connect vertex $x$ to $x+ 1 \bmod p$, to $x-1 \bmod p$ and to $x^{-1} \bmod p$. Each such graph is a cycle, plus a matching over $p-3$ vertices. (The multiplicative inverse is undefined for $0$, and is the element itself for $p-1$ and $1$.)</p>

<p>This is a picture of what it looks like for $p=59$</p>

<p><img src="https://i.sstatic.net/JaxgN.png" alt="Simple expander"></p>

<p>There is no known elementary proof that this a family of expanders, but the construction is very simple.</p>

CC BY-SA 2.5
2011-03-13T19:22:15.237Z
it's a nice example, and illustrates how sparse you can be and still expand.
Suresh Venkat
CC BY-SA 2.5
2011-03-13T20:12:54.037Z
+1. Great, and very simple! Although it's quite surprising that no known elementary proof exists for it :=o
Sadeq Dousti
CC BY-SA 2.5
2011-03-14T01:24:16.813Z
I guess it is a trade-off: A simple construction comes with a complicated proof :P Do this family of expanders have a name?
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2011-03-15T00:20:19.813Z
I don't think that this family has a standard name. The reason it is a family of expanders is related to the reason why Ramanujan graphs are expanding, so we could call them "baby Ramanujan" graphs.
Luca Trevisan
CC BY-SA 2.5
2011-03-13T19:01:23.580Z
2011-03-13T19:01:23.580Z
Luca Trevisan
<p>Consider the following definition, taken from <a href="http://math.ucsd.edu/~fan/mypaps/fanpap/fc31concentrators.pdf" rel="nofollow">Chung's 1978 paper</a>:</p>

<blockquote>
  <p>An $(n, m)$-<strong>concentrator</strong> is a graph with $n$ input vertices and $m$ output vertices, 
  $n \ge m$, having the property that, for any set of $m$ or fewer inputs, a set of vertex-disjoint paths exists that join the given inputs in a one-to-one fashion to different outputs. If this graph is directed or acyclic, we call it a directed or acyclic $(n, m)$-concentrator, respectively.</p>
</blockquote>

<p>The paper includes definitions for <strong>superconcentrators</strong>, <strong>generalizers</strong>, and <strong>non-blocking networks</strong>. One may also encounter other types of graphs, such as <strong>expanders</strong> and <strong>Ramanujan graphs</strong> in the literature.</p>

<p>These types of graphs are usually studied as "families of graphs." There are a number of papers (such as Pinsker [1], <a href="http://portal.acm.org/citation.cfm?id=803752" rel="nofollow">Valiant</a>, <a href="http://link.aip.org/link/?SMJCAT/6/298/1" rel="nofollow">Pippenger</a>, and <a href="http://dx.doi.org/10.1109/SFCS.1979.16" rel="nofollow">Gabber-Galil</a>) which try to explicitly construct such families, while optimizing parameters like size, density, sparsity, and the like.</p>

<p>The problem is that while those papers are excellent for research, they don't help much pedagogically. Let's clarify: Consider a student who sees the definition of a <strong>concentrator</strong> (or any similar graph) for the first time. His best bet to understand the definition is to imagine it pictorially, or see an illustration of examples and non-examples of a concentrator.</p>

<p>I've been searching for such <strong>simple</strong> examples of <em>Special Graph Families</em> for quite a while, but didn't achieve much. So, the question is:</p>

<blockquote>
  <p>Could you describe simple constructions of special graph families? Illustrations are much appreciated.</p>
</blockquote>

<p>Note that the simple constructions need not be optimum in any sense, but they must not be trivial either (e.g. a complete graph is a trivial example for some graph families). I don't formalize the word <strong>trivial</strong>, and leave it to your judgement.</p>

<p>[1] M. S. Pinsker. "On the complexity of a concentrator", 7th International Teletraffic Conference, pages 318/1-318/4, 1973.</p>

CC BY-SA 2.5
2011-03-12T11:00:34.227Z
This question might be eligible to become CW, but I'm not sure.
Sadeq Dousti
CC BY-SA 2.5
2011-03-13T07:29:32.397Z
Why not just "take a random graph"?
arnab
CC BY-SA 2.5
2011-03-13T10:39:31.027Z
@arnab: Random graphs are used to show the mere **existence** of such families (using probabilistic method). They aren't constructive. Moreover, I'm after simple constructions which are apt for illustrative purposes.
Sadeq Dousti
CC BY-SA 2.5
2011-03-13T20:27:50.773Z
My point was more philosophical...Instead of viewing the fact that a random graph satisfies expansion conditions with high probability as a counting result showing existence, one could view it as a randomized algorithm.  In my opinion, we want deterministic construction algorithms because of our computational models, not because they give better intuition.
arnab
<graph-theory><co.combinatorics><soft-question><big-list><expanders>
Simple Constructions of Special Graph Families
Sadeq Dousti
# Simple Constructions of Special Graph Families

(Asked by: username_0 on 2011-03-12)

Consider the following definition, taken from [Chung's 1978 paper](http://math.ucsd.edu/~fan/mypaps/fanpap/fc31concentrators.pdf):

> An $(n, m)$-**concentrator** is a graph with $n$ input vertices and $m$ output vertices,
> $n \ge m$, having the property that, for any set of $m$ or fewer inputs, a set of vertex-disjoint paths exists that join the given inputs in a one-to-one fashion to different outputs. If this graph is directed or acyclic, we call it a directed or acyclic $(n, m)$-concentrator, respectively.

The paper includes definitions for **superconcentrators**, **generalizers**, and **non-blocking networks**. One may also encounter other types of graphs, such as **expanders** and **Ramanujan graphs** in the literature.

These types of graphs are usually studied as "families of graphs." There are a number of papers (such as Pinsker [1], [Valiant](http://portal.acm.org/citation.cfm?id=803752), [Pippenger](http://link.aip.org/link/?SMJCAT/6/298/1), and [Gabber-Galil](http://dx.doi.org/10.1109/SFCS.1979.16)) which try to explicitly construct such families, while optimizing parameters like size, density, sparsity, and the like.

The problem is that while those papers are excellent for research, they don't help much pedagogically. Let's clarify: Consider a student who sees the definition of a **concentrator** (or any similar graph) for the first time. His best bet to understand the definition is to imagine it pictorially, or see an illustration of examples and non-examples of a concentrator.

I've been searching for such **simple** examples of *Special Graph Families* for quite a while, but didn't achieve much. So, the question is:

> Could you describe simple constructions of special graph families? Illustrations are much appreciated.

Note that the simple constructions need not be optimum in any sense, but they must not be trivial either (e.g. a complete graph is a trivial example for some graph families). I don't formalize the word **trivial**, and leave it to your judgement.

[1] M. S. Pinsker. "On the complexity of a concentrator", 7th International Teletraffic Conference, pages 318/1-318/4, 1973.

**Tags:** graph-theory, co.combinatorics, soft-question, big-list, expanders

> **Comments:**
> **username_0**: This question might be eligible to become CW, but I'm not sure.  
> **username_1**: Why not just "take a random graph"?  
> **username_0**: @username_1: Random graphs are used to show the mere **existence** of such families (using probabilistic method). They aren't constructive. Moreover, I'm after simple constructions which are apt for illustrative purposes.  
> **username_1**: My point was more philosophical...Instead of viewing the fact that a random graph satisfies expansion conditions with high probability as a counting result showing existence, one could view it as a randomized algorithm.  In my opinion, we want deterministic construction algorithms because of our computational models, not because they give better intuition.  

---

## 1 answers

### Answer by username_2 on 2011-03-13. Score: 16 | Accepted answer

This is a family of expander graphs: let $p$ be a prime, let the vertex set be $\{ 0,\ldots,p-1\}$, connect vertex $x$ to $x+ 1 \bmod p$, to $x-1 \bmod p$ and to $x^{-1} \bmod p$. Each such graph is a cycle, plus a matching over $p-3$ vertices. (The multiplicative inverse is undefined for $0$, and is the element itself for $p-1$ and $1$.)

This is a picture of what it looks like for $p=59$

![Simple expander](https://i.sstatic.net/JaxgN.png)

There is no known elementary proof that this a family of expanders, but the construction is very simple.

> **Comments:**
> **username_3**: it's a nice example, and illustrates how sparse you can be and still expand.  
> **username_0**: +1. Great, and very simple! Although it's quite surprising that no known elementary proof exists for it :=o  
> **username_4**: I guess it is a trade-off: A simple construction comes with a complicated proof :P Do this family of expanders have a name?  
> **username_2**: I don't think that this family has a standard name. The reason it is a family of expanders is related to the reason why Ramanujan graphs are expanding, so we could call them "baby Ramanujan" graphs.  

---

