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