Remarks on quasirandom graphs
Back to Resources for Quasirandom graphs

  • Andrew Thomason, Pseudo-random graphs, Annals of Discrete Mathematics 33 (1987), 307--331. It is is the same as the version in the Proceedings of the Poznan meeting in 1986.

    Abstract:

    We call a graph \(G\) \( (p, \alpha ) \) jumbled if, for every induced subgraph \( H \) of \(G\) , \( | e(H)-p \binom {|H|} 2 | \leq \alpha |H| \) holds; here \(p\) and \(\alpha\) are real numbers with \( 0 < p <1 \leq \alpha, \) and \(e(H)\) is the number of edges in \(H\). We show that a \( (p, \alpha)-\) jumbleed graph behaves in many ways like a random graph with edge probability \(p\), and some aspects of this similarity are examined.


  • Remark 1: The above paper is referred by many papers on quasirandom but Many authors likely have never read it and appeared not to know what is really in it.
    According to Thomason (as written in "Pseudo-random graphs"), his paper has very different perspectives from the notion of quasirandom (as defined by Chung, Graham and Wilson). The main spirit of quasirandom is to classify graph properties into equivalent classes, which was not the case in the above paper.

  • Remark 2. The difference of expansion property and eigenvalue property.

    Definitions of expanders
    A graph \(G\) on \(n\) vertices is an \( (\alpha, c)-\)expander if for every subset \(S\) of \(s\) vertices, the neighoborhood of \(S\) has at least \(\alpha s \) vertices, provided \( s \leq c n \).

  • Examples of expanders which do not satisfy the eigenvalue condition.