Resources for Quasirandom Graphs and Structures
History
The roots of quasirandom graphs
There are numerous earlier work on pseudo random graphs by R"odl, Frankl,
Thomason
, etc, (such as pointing out certain one directional implications of eigenvalues). The strong notion of equivalence among various disparate graph properties first was introduced in the paper
"Quasi-random graphs
by Chung, Graham and Wilson in 1989.
The concept of quasirandom graphs combines
extremal graph theory
(how graph properties are related) and
random graph theory (how random graphs behave)
. Many (but not all) properties of random graphs are shared by quasirandom graphs.
There are
two ways to define relations between various properties of graphs
The (basic) equivalence class of quasirandom graphs
Quasirandom heirarchy for graphs, hypergraphs and other combinatorial structures --- further problems
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, many of which can be found in Lovasz' book on graph limits, will not be included here.
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:
The
full reference list
on quasirandom graphs and other structures.
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.