From quasirandom graphs to graph limits and graphlets

We generalize the notion of quasirandomness which concerns a class of equivalent properties that random graphs satisfy. We show that the convergence of a graph sequence under the spectral distance is equivalent to the convergence using the (normalized) cut distance. The resulting graph limit is called graphlet. We then consider several families of graphlets and, in particular, we characterize quasirandom graphlets with low ranks for both dense and sparse graphs. For example, we show that a graph sequence G(n), for n = 1,2,..., converges to a graphlet of rank 2,(i.e., all normalized eigenvalues G(n) converge to 0 except for two eigenvalues converging to 1 and rho > 0) if and only if the graphlet is the union of 2 quasirandom graphlets. (C) 2014 Elsevier Inc. All rights reserved.