This is an old revision of this page, as edited by David Eppstein(talk | contribs) at 21:21, 13 July 2020(→References: Thomason is widely credited as initiating the study of quasirandom graphs, so we should cite his early papers). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
Revision as of 21:21, 13 July 2020 by David Eppstein(talk | contribs)(→References: Thomason is widely credited as initiating the study of quasirandom graphs, so we should cite his early papers)
In graph theory, there are several notions as to what it means for a sequence of graphs to be "random-like". Roughly speaking, we would like to call a sequence of graphs "random-like" if certain graph properties of the sequence are reasonably similar to those of a sequence of Erdős–Rényi random graphs. In the late 1980s, Fan Chung, Ronald Graham and Richard Wilson showed that many of the notions are in fact equivalent.
Statement
Let be a fixed constant, and let be a sequence of graphs with having vertices and edges, for fixed . Denote by . Then, the following graph properties are equivalent:
(Discrepancy condition): for all vertex sets .
(Alternative discrepancy condition): for all vertex set .
(Graph counting condition): For each graph , the number of labelled copies of in (i.e. vertices in are distinguished) is . The term may depend on .
(4-cycle counting condition): The number of labelled copies of is at most .
(Codegree condition): Let denote the number of common neighbors of two vertices and in . Then, .
(Eigenvalue condition): If are the eigenvalues of the adjacency matrix of , then and .
If any of the above conditions is satisfied, then we say that the sequence of graphs is quasi-random.
Sketch of proof
In what follows, and .
Discrepancy condition Alternative discrepancy condition.
Simply take .
Alternative discrepancy condition Discrepancy condition.
By the inclusion–exclusion principle, we can write in terms of the edge counts of individual vertex sets: Then, by the alternative discrepancy condition,
Using the idea of the second moment method from probabilistic combinatorics, we can show that the variance of is .
Codegree condition Discrepancy condition
This follows from Cauchy-Schwarz and the definition of codegree.
Eigenvalue condition 4-cycle counting condition
The number of labelled 4-cycles in is within of the number of closed walks of length 4 in , which is , where denote the adjacency matrix of . From linear algebra, we know that . The dominating term is : by assumption, . It remains to check that the sum of the other s are not too big. Indeed,
4-cycle counting condition Eigenvalue condition
By the min-max theorem, , where denote the vector in whose entries are all 1. On the other hand, by the 4-cycle counting condition Thus, ,
and