Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4624733 | Advances in Applied Mathematics | 2014 | 40 Pages |
Abstract
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 GnGn, for n=1,2,…n=1,2,…, converges to a graphlet of rank 2 (i.e., all normalized eigenvalues GnGn converge to 0 except for two eigenvalues converging to 1 and ρ>0ρ>0) if and only if the graphlet is the union of 2 quasirandom graphlets.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Applied Mathematics
Authors
Fan Chung,