5
$\begingroup$

Consider the following definition, taken from Chung's 1978 paper:

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, Pippenger, and Gabber-Galil) 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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ This question might be eligible to become CW, but I'm not sure. $\endgroup$
    – Sadeq Dousti
    Mar 12, 2011 at 11:00
  • $\begingroup$ Why not just "take a random graph"? $\endgroup$
    – arnab
    Mar 13, 2011 at 7:29
  • $\begingroup$ @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. $\endgroup$
    – Sadeq Dousti
    Mar 13, 2011 at 10:39
  • 1
    $\begingroup$ 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. $\endgroup$
    – arnab
    Mar 13, 2011 at 20:27

1 Answer 1

Reset to default
16
$\begingroup$

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

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

Improve this answer
$\endgroup$
4
  • 3
    $\begingroup$ it's a nice example, and illustrates how sparse you can be and still expand. $\endgroup$
    – Suresh Venkat
    Mar 13, 2011 at 19:22
  • $\begingroup$ +1. Great, and very simple! Although it's quite surprising that no known elementary proof exists for it :=o $\endgroup$
    – Sadeq Dousti
    Mar 13, 2011 at 20:12
  • $\begingroup$ I guess it is a trade-off: A simple construction comes with a complicated proof :P Do this family of expanders have a name? $\endgroup$
    – Hsien-Chih Chang 張顯之
    Mar 14, 2011 at 1:24
  • $\begingroup$ 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. $\endgroup$
    – Luca Trevisan
    Mar 15, 2011 at 0:20

Your Answer

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

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