## 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: