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.

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

$\endgroup$
  • 3
    $\begingroup$ it's a nice example, and illustrates how sparse you can be and still expand. $\endgroup$ – Suresh Venkat Mar 13 '11 at 19:22
  • $\begingroup$ +1. Great, and very simple! Although it's quite surprising that no known elementary proof exists for it :=o $\endgroup$ – M.S. Dousti Mar 13 '11 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 '11 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 '11 at 0:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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