Some clarification about quasirandom graphs
Why quasirandom?
When we first started our work on
quasi-random graphs
in 1988, the term people mostly used was pseudo random, which did not have a definite meaning (and still doesn't). We chose the name quasirandom because of the following two reasons.
Quasirandom is rigorously defined.
Quasirandom is an equivalence class of graph properties.
Some words of caution!
There are numerous earlier work on pseudo random graphs by R"odl, Frankl, Thomason, among others. However, for example, the (p,\alpha)-nimble property introduced by
Thomason
in 1987 is NOT quasirandom since the defined error bound is too small to derive equivalence.
Many (but not all) properties of random graphs are shared by quasirandom graphs.
Expander graphs usually means neighborhood expansion. However, the property of neighborhood expansion is NOT a quasirandom property. For example, there are bipartite expanders which are definitely not quasirandom.
Remarks
There are
two ways to define relations between various properties of graphs
The (basic) equivalence class of quasirandom graphs
Quasirandom heirarchy can be for any combinatorial structures such as graphs, hypergraphs, tournaments, permutations ...
Lecture notes on quasirandom graphs ----
Tim Gowers' lecture notes
,
Fan Chung's lecture notes.
Quasirandom graphs in
book chapters
---- Alon/Spencer, Handbook of Combinatorics;
surveys
---
Mohar
,
Komlos/Simonovitz
,
Merris
,
Graph limits is one area that was influenced by quasirandom graphs. The related references can be found in Lovasz' book on graph limits.
Clarification of several terminologies that are often misused.
(Of course, it is much preferred not to use the same name for two different properties that are
NOT
equivalent.)
Pseudo random graphs
(Correct)
A pseudo random graph usually mean that it satisfies some properties of random graphs (which are known to have many properties ranging from weak to strong). So, pseudo random has many different interpretations by different authors. More discussion can be found in
the link to remarks
(Wrong) "Pseudo random graphs are like quasirandom graphs."
Quasirandom graphs are rigorously defined, referring to graphs satisfying graph properties in a large equivalence class that happen to be shared by random graphs. Pseudo random graphs do not concern any notion of equivalence.
Expanders
(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:
Early references
before the introduction of quasirandom graphs.
The 14 articles
on quasirandom graphs between 1989 -- 1993.
Quasirandom graphs for general degree distributions
Quasirandom hypergraphs
Quasirandom sequences
Quasirandom permutations
Quasirandom groups
Quasirandom graphs and graph limits
Algorithmic aspects of quasirandom graphs
This page is still under construction.