Talk:Expander graph

From Wikipedia, the free encyclopedia

The final paras here hang by a very tenuous thread from the rest.

Charles Matthews 18:29, 6 Sep 2004 (UTC)

Is the notation / S for the complement of a vertex set standard? It makes my eyes sore to look at E(S, / S) / | S | - Gauge 23:55, 5 Jan 2005 (UTC)

isn't it the second eigenvalue of the admittance matrix rather than adjacency matrix that matters ? --Vastinnocentaims 19:04, 10 August 2005 (UTC)

If M is the adjacency matrix, and A is the admittance/Laplacian matrix, then every eigenvalue λ of M corresponds to an eigenvalue (d-λ) of A, where d is the degree, so they are essentially equivalent concepts. There are also some bounds related to expanders that are expressed not in terms of the 2nd eigenvalue λ₂, but in terms of the 2nd largest eigenvalue magnitude, i.e, max{λ₂, | λ_n | } (λ₁ is always d, and is always the largest) Blokhead 03:25, 12 October 2005 (UTC)

[edit] Spectral expansion section

Hi,

In the spectral expansion section, you mention that lamba = max_{1 <= i <= n}(lambda_1, ..., lambda_{n-1}) but we have lambda_{i+1} >= lambda_i. So is lambda = lambda_1 ? In that case, how is the spectral gap d - lambda_1 different from d - lambda?

Claude-Guy

[edit] Directed graph as bipartite

A directed graph can also be interpreted as a balanced bipartite graph (with all edges going from one copy of V to another copy).

I don't understand. 1 cannot be interpreted as 2, I must be missing something, seems like you're making a wholly different graph. MotherFunctor 18:39, 8 August 2006 (UTC)