(Correct)
For an expander graph, there is some guarantee that
the neighborhood of each vertex-subset S is large, as long as
S is not too big.
In other words, "expander" means
neighborhood expansion.
Details.
(Bad) "A \(k\)-regular expander graph has
all eigenvalues of the adjacency matrix small (e.g., \( < c \sqrt{k})\) except for one eigenvalue \(k\)".
There are graphs with neighborhood expansion but not satisfy the eigenvalues
condition. It is true that graphs with the eigenvalue condition
are expanders, but the reverse direction is not true in general.
Here is a counter example.
Of course, you can choose your definition of expander to satisfy the eigenvalue condition, but it should be understood that the eigenvalue condition is NOT equivalent to the neighborhood expansion condition.
Mixing in graphs
-
(Correct)
The (typical) random walk on a graph converges to its stationary distribution
fast depending on the spectral gap (e.g., the first nontrivial eigenvalue of the normalized Laplacian).
-
(Bad) Various eigenvalue inequalities for graphs
are often
called "mixing" for the lack of better names but
have nothing to do with random walks.
These eigenvalue
inqualities could be "discrepancy inequalities" or "deviation inequalties" as
defined in the paper on
quasirandom set systems.
References with keyword search
(author, title, year, etc., case insensitive, partial words allowed)
Keyword search:
|
This page is still under construction.