Pseudorandom Graph

A pseudorandom graph is a deterministic graph whose edge distribution or other selected properties imitate those of a random graph. For dense graphs, one standard quasirandom condition is that every pair of vertex subsets has approximately the number of edges between them predicted by a fixed edge density. Several such conditions, including spectral and subgraph-count conditions, are asymptotically equivalent for dense graph sequences.