4
$\begingroup$

Context

Reading about Expanders

Setup

A regular n,2d graph is generated as follows: generate d random permutations of [n] connect the edges; giving a n,2d regular graph

Question

How do I prove that this graph is a good expander?

Known:

Broder/Shamir has a paper "On the second eigenvalue of random regular graphs." that proves this statement. However, it uses martingales, which I do not understand.

Also Known:

Many texts provide a short proof for bipartite graphs; but not the general case.

Request

Is there an elementary (combinatorial) proof of the general case? [For the graphs generated above.]

Thanks!

Improve this question
$\endgroup$
3
  • $\begingroup$ There are several related but different definitions of an expander (the most popular ones are in terms of the spectral gap, vertex expansion, or edge expansion). Which one are you using? $\endgroup$
    – Emil Jeřábek
    Commented Nov 16, 2011 at 11:24
  • 3
    $\begingroup$ It's worth learning about martingales (in addition to looking for another proof), actually, since they are an extremely useful tool. The beginning of Chapter 7 in Alon and Spencer's book on the probabilistic method gives a nice introduction, and in a couple of pages it covers everything I think you need for the Broder and Shamir proof. $\endgroup$
    – Henry Cohn
    Commented Nov 16, 2011 at 14:37
  • 2
    $\begingroup$ Maybe it's time to learn about martingales... $\endgroup$
    – Ori Gurel-Gurevich
    Commented Nov 16, 2011 at 18:19

1 Answer 1

Reset to default
5
$\begingroup$

This is can be done by a counting argument -- if the graph is not a a good expander then there is a subset with a small boundary. Given any such subset there are relatively a few permutations which preserve it, and summing over all possible subsets one sees that only a few $d$ tuples of permutations give graphs which are not good expanders.

This breaks if $d$ is very small or your notion of a good expander is very strong. This argument can be found in Lubotzky's book.

Improve this answer
$\endgroup$
2
  • $\begingroup$ @kassabov: "Lubotzky's book" is not very specific... $\endgroup$
    – Igor Rivin
    Commented Nov 16, 2011 at 15:57
  • 1
    $\begingroup$ Igor: Lubotzky has only one book on expanders -- "Descrete Groups, Expanding graphs and invariant measures" Progress in mathematics 125 Birkhauser 1994 $\endgroup$
    – kassabov
    Commented Nov 16, 2011 at 16:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .