Quasi-random graph

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 ${\displaystyle p\in (0,1)}$ be a fixed constant, and let ${\displaystyle \{G_{n}\}_{n=1}^{\infty }}$ be a sequence of graphs with ${\displaystyle \{G_{n}\}}$ having ${\displaystyle n}$ vertices and ${\displaystyle (p+o(1)){\binom {n}{2}}}$ edges, for fixed ${\displaystyle 0<p<1}$. Denote ${\displaystyle G_{n}}$ by ${\displaystyle G}$. Then, the following graph properties are equivalent:

1. (Discrepancy condition): ${\displaystyle |e(X,Y)-p|X||Y||=o(n^{2})}$ for all vertex sets ${\displaystyle X,Y\subset V(G)}$.
2. (Alternative discrepancy condition): ${\displaystyle \left|e(X)-p{\binom {|X|}{2}}\right|=o(n^{2})}$ for all vertex set ${\displaystyle X\subset V(G)}$.
3. (Graph counting condition): For each graph ${\displaystyle H}$, the number of labelled copies of ${\displaystyle H}$ in ${\displaystyle G}$ (i.e. vertices in ${\displaystyle H}$ are distinguished) is ${\displaystyle (p^{e(H)}+o(1))n^{v(H)}}$. The ${\displaystyle o(1)}$ term may depend on ${\displaystyle H}$.
4. (4-cycle counting condition): The number of labelled copies of ${\displaystyle C_{4}}$ is at most ${\displaystyle (p^{4}+o(1))n^{4}}$.
5. (Codegree condition): Let ${\displaystyle \operatorname {codeg} (u,v)}$ denote the number of common neighbors of two vertices ${\displaystyle u}$ and ${\displaystyle v}$ in ${\displaystyle G}$. Then, ${\displaystyle \sum _{u,v\in V(G)}|\operatorname {codeg} (u,v)-p^{2}n|=o(n^{3})}$.
6. (Eigenvalue condition): If ${\displaystyle \lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{v(G)}}$ are the eigenvalues of the adjacency matrix of ${\displaystyle G}$, then ${\displaystyle \lambda _{1}=pn+o(n)}$ and ${\displaystyle \max _{i\neq 1}|\lambda _{i}|=o(n)}$.

If any of the above conditions is satisfied, then we say that the sequence of graphs ${\displaystyle \{G_{n}\}_{n=1}^{\infty }}$ is quasi-random.

Sketch of proof

In what follows, ${\displaystyle v(H)=|V(H)|}$ and ${\displaystyle e(H)=|E(H)|}$.

Discrepancy condition ${\displaystyle \implies }$ Alternative discrepancy condition.

Simply take ${\displaystyle Y=X}$.

Alternative discrepancy condition ${\displaystyle \implies }$ Discrepancy condition.

By the inclusion–exclusion principle, we can write ${\displaystyle e(X,Y)}$ in terms of the edge counts of individual vertex sets: ${\displaystyle e(X,Y)=e(X\cup Y)+e(X\cap Y)-e(X\setminus Y)-e(Y\setminus X).}$ Then, by the alternative discrepancy condition,

${\displaystyle p\left({\binom {|X\cup Y|}{2}}+{\binom {|X\cap Y|}{2}}+{\binom {|X\setminus Y|}{2}}+{\binom {|Y\setminus X|}{2}}+o(n^{2})\right)=p|X||Y|+o(n^{2}).}$

Discrepancy condition ${\displaystyle \implies }$ Graph counting condition

This follows from the graph counting lemma, taking ${\displaystyle V_{i}=G}$ for ${\displaystyle i=1,\ldots ,v(H)}$.

Graph counting condition ${\displaystyle \implies }$ 4-cycle counting condition

The 4-cycle ${\displaystyle C_{4}}$ is just a special case of ${\displaystyle H}$.

4-cycle counting condition ${\displaystyle \implies }$ Codegree condition

Using the idea of the second moment method from probabilistic combinatorics, we can show that the variance of ${\displaystyle \operatorname {codeg} (u,v)}$ is ${\displaystyle o\left(n^{3}\right)}$.

Codegree condition ${\displaystyle \implies }$ Discrepancy condition

This follows from Cauchy-Schwarz and the definition of codegree.

Eigenvalue condition ${\displaystyle \implies }$ 4-cycle counting condition

The number of labelled 4-cycles in ${\displaystyle G_{n}}$ is within ${\displaystyle O(n^{3})}$ of the number of closed walks of length 4 in ${\displaystyle G_{n}}$, which is ${\displaystyle \operatorname {tr} (A_{G}^{4})}$, where ${\displaystyle A_{G}}$ denote the adjacency matrix of ${\displaystyle G}$. From linear algebra, we know that ${\displaystyle \operatorname {tr} (A_{G}^{4})=\sum _{i=1}^{n}\lambda _{i}^{4}}$. The dominating term is ${\displaystyle \lambda _{1}}$: by assumption, ${\displaystyle \lambda _{1}^{4}=p^{4}n^{4}+o(n^{4})}$. It remains to check that the sum of the other ${\displaystyle \lambda _{i}^{4}}$s are not too big. Indeed, ${\displaystyle \sum _{i\geq 2}\lambda _{i}^{4}\leq \max _{i\neq 2}|\lambda _{i}|^{2}\sum _{i\geq 1}\lambda _{i}^{2}=\max _{i\neq 2}|\lambda _{i}|^{2}\operatorname {tr} (A_{G}^{2})=\max _{i\neq 2}|\lambda _{i}|^{2}\cdot 2e(G)=o(n^{4}).}$

4-cycle counting condition ${\displaystyle \implies }$ Eigenvalue condition

By the min-max theorem, ${\displaystyle \lambda _{1}\geq {\frac {{\boldsymbol {1}}^{T}A_{G}{\boldsymbol {1}}}{{\boldsymbol {1}}^{T}{\boldsymbol {1}}}}={\frac {2e(G)}{n}}=\left(p+o(1)\right)n}$, where ${\displaystyle {\boldsymbol {1}}}$ denote the vector in ${\displaystyle \mathbb {R} ^{v(G)}}$ whose entries are all 1. On the other hand, by the 4-cycle counting condition ${\displaystyle \lambda _{1}^{4}\leq \sum _{i=1}^{n}\lambda _{i}^{4}=\operatorname {tr} A_{G}^{4}\leq p^{4}n^{4}+o(n^{4}).}$Thus, ${\displaystyle \lambda _{1}=pn+o(n)}$, and ${\displaystyle \max _{i\neq 1}|\lambda _{i}|^{4}\leq \operatorname {tr} (A_{G}^{4})-\lambda _{1}^{4}\leq p^{4}n^{4}-p^{4}n^{4}+o(n^{4})=o(n^{4}).}$

References

• Chung, F. R. K.; Graham, R. L.; Wilson, R. M. (February 1988). "Quasi-random graphs". Proceedings of the National Academy of Sciences of the United States of America. 85: 969–970. doi:10.1073/pnas.85.4.969. PMC 279681. PMID 16593909.
• Chung, F. R. K.; Graham, R. L.; Wilson, R. M. (December 1989). "Quasi-random graphs". Combinatorica. 9: 345–362. doi:10.1007/BF02125347.
• Thomason, Andrew (1987). "Pseudorandom graphs". Random graphs '85 (Poznań, 1985). North-Holland Math. Stud. 144. North-Holland, Amsterdam. pp. 307–331. MR 0930498.
• Thomason, Andrew (1987). "Random graphs, strongly regular graphs and pseudorandom graphs". Surveys in combinatorics 1987 (New Cross, 1987). London Math. Soc. Lecture Note Ser. 123. Cambridge Univ. Press, Cambridge. pp. 173–195. MR 0905280.
• Zhao, Yufei. "Graph Theory and Additive Combinatorics" (PDF). pp. 71–76. Retrieved 23 November 2019.