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

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

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

Sketch of proof

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

Discrepancy condition $⟹$ Alternative discrepancy condition.

Simply take $Y=X$.

Alternative discrepancy condition $⟹$ Discrepancy condition.

By the inclusion–exclusion principle, we can write $e(X,Y)$ in terms of the edge counts of individual vertex sets: $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,

$p((\genfrac{}{}{0ex}{}{|X\cup Y|}{2})+(\genfrac{}{}{0ex}{}{|X\cap Y|}{2})+(\genfrac{}{}{0ex}{}{|X\setminus Y|}{2})+(\genfrac{}{}{0ex}{}{|Y\setminus X|}{2})+o(n^2))=p|X||Y|+o(n^2).$

Discrepancy condition $⟹$ Graph counting condition

This follows from the graph counting lemma, taking $V_i=G$ for $i=1,\dots ,v(H)$.

Graph counting condition $⟹$ 4-cycle counting condition

The 4-cycle $C_4$ is just a special case of $H$.

4-cycle counting condition $⟹$ Codegree condition

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

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 $G_n$ is within $O(n^3)$ of the number of closed walks of length 4 in $G_n$, which is $\mathrm{tr}(A_G^4)$, where $A_G$ denote the adjacency matrix of $G$. From linear algebra, we know that $\mathrm{tr}(A_G^4)=\sum _{i=1}^n{\lambda }_i^4$. The dominating term is ${\lambda }_1$: by assumption, ${\lambda }_1^4=p^4{n}^4+o(n^4)$. It remains to check that the sum of the other ${\lambda }_i^4$s are not too big. Indeed, $\sum _{i\ge 2}{\lambda }_i^4\le \underset{i\ne 2}{\max }|{\lambda }_i{|}^2\sum _{i\ge 1}{\lambda }_i^2=\underset{i\ne 2}{\max }|{\lambda }_i{|}^2\mathrm{tr}(A_G^2)=\underset{i\ne 2}{\max }|{\lambda }_i{|}^2\cdot 2e(G)=o(n^4).$

4-cycle counting condition $⟹$ Eigenvalue condition

By the min-max theorem, ${\lambda }_1\ge \frac{{\mathit{1}}^T{A}_G\mathit{1}}{{\mathit{1}}^T\mathit{1}}=\frac{2e(G)}{n}=(p+o(1))n$, where $\mathit{1}$ denote the vector in ${\mathbb{ℝ}}^{v(G)}$ whose entries are all 1. On the other hand, by the 4-cycle counting condition ${\lambda }_1^4\le \sum _{i=1}^n{\lambda }_i^4=\mathrm{tr}{A}_G^4\le p^4{n}^4+o(n^4).$Thus, ${\lambda }_1=pn+o(n)$, and $\underset{i\ne 1}{\max }|{\lambda }_i{|}^4\le \mathrm{tr}(A_G^4)-{\lambda }_1^4\le 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. 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. 
• 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. 
• Zhao, Yufei. "Graph Theory and Additive Combinatorics" (PDF). pp. 71–76. http://yufeizhao.com/gtac/fa17/gtac.pdf.