Loading ...
Sorry, an error occurred while loading the content.

[My Computational Complexity Web Log] Expanders from Epsilon-Biased Sets

Expand Messages
  • Lance Fortnow
    Expander graphs informally are graphs that given any subset S that is not too large, the set of vertices connected to S contains a large number of vertices
    Message 1 of 1 , Jun 30, 2003
    • 0 Attachment
      Expander graphs informally are graphs that given any subset S that is not too large, the set of vertices connected to S contains a large number of vertices outside of S. There are many constructions and applications for expander graphs leading to entire courses on the subject.

      The adjacency matrix A of a graph G of n vertices is an n×n matrix such that ai,j is 1 if there is an edge between vertices i and j and 0 otherwise. Noga Alon noticed that a graph that has a large gap between the first and second eigenvalue of the adjacency matrix will be a good expander.

      We can use ε-biased sets to get expanders. Let S be a ε-biased set for Fm for F the field of 2 elements. Consider the graph G consisting of 2m vertices labelled with the elements of Fm and an edge from x to y if y=x+s or x=y+s. This kind of graph G is known as a Cayley graph.

      By looking at the eigenvalues the adjacency matrix A of G we can show G is an expander. The eigenvectors v are just the vectors corresponding to the functions g in L described earlier. For any vector a we have

      (Ag)(a) = Σs in S g(a+s) = g(a) Σs in S g(s)
      since g(a+s) = g(a)g(s). Let g(S) = Σs in S g(s). We now have that
      Ag = g(S) g.
      So g is an eigenvector with eigenvalue g(S). If g is the constant one function then g(S)=|S|. Since S is an ε-biased set, g(S)≤ε|S| for every other g, so the second eigenvalue is much smaller than the largest eigenvalue and G must be an expander.

      --
      Posted by Lance Fortnow to My Computational Complexity Web Log at 6/30/2003 01:16:04 PM

      Powered by Blogger Pro

    Your message has been successfully submitted and would be delivered to recipients shortly.