Pseudorandom graph

Thomason showed that the "jumbled" condition is implied by a simpler-to-check condition, only depending on the codegree of two vertices and not every subset of the vertex set of the graph. Letting ${\displaystyle \operatorname {codeg} (u,v)}$ be the number of common neighbors of two vertices ${\displaystyle u}$ and ${\displaystyle v}$, Thomason showed that, given a graph ${\displaystyle G}$ on ${\displaystyle n}$ vertices with minimum degree ${\displaystyle np}$, if ${\displaystyle \operatorname {codeg} (u,v)\leq np^{2}+\ell }$ for every ${\displaystyle u}$ and ${\displaystyle v}$, then ${\displaystyle G}$ is ${\displaystyle \left(p,{\sqrt {(p+\ell )n}}\,\right)}$-jumbled.[2]^: 7 This result shows how to check the jumbledness condition algorithmically in polynomial time in the number of vertices, and can be used to show pseudorandomness of specific graphs.[2]^: 7

In the spirit of the conditions considered by Thomason and their alternately global and local nature, several weaker conditions were considered by Chung, Graham, and Wilson in 1989:[3] a graph ${\displaystyle G}$ on ${\displaystyle n}$ vertices with edge density ${\displaystyle p}$ and some ${\displaystyle \varepsilon >0}$ can satisfy each of these conditions if

• Discrepancy: for any subsets ${\displaystyle X,Y}$ of the vertex set ${\displaystyle V=V(G)}$, the number of edges between ${\displaystyle X}$ and ${\displaystyle Y}$ is within ${\displaystyle \varepsilon n^{2}}$ of ${\displaystyle p|X||Y|}$.
• Discrepancy on individual sets: for any subset ${\displaystyle X}$ of ${\displaystyle V}$, the number of edges among ${\displaystyle X}$ is within ${\displaystyle \varepsilon n^{2}}$ of ${\displaystyle p{\binom {|X|}{2}}}$.
• Subgraph counting: for every graph ${\displaystyle H}$, the number of labeled copies of ${\displaystyle H}$ among the subgraphs of ${\displaystyle G}$ is within ${\displaystyle \varepsilon n^{v(H)}}$ of ${\displaystyle p^{e(H)}n^{v(H)}}$.
• 4-cycle counting: the number of labeled ${\displaystyle 4}$-cycles among the subgraphs of ${\displaystyle G}$ is within ${\displaystyle \varepsilon n^{4}}$ of ${\displaystyle p^{4}n^{4}}$.
• Codegree: letting ${\displaystyle \operatorname {codeg} (u,v)}$ be the number of common neighbors of two vertices ${\displaystyle u}$ and ${\displaystyle v}$,

${\displaystyle \sum _{u,v\in V}{\big |}\operatorname {codeg} (u,v)-p^{2}n{\big |}\leq \varepsilon n^{3}.}$

• Eigenvalue bounding: If ${\displaystyle \lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n}}$ are the eigenvalues of the adjacency matrix of ${\displaystyle G}$, then ${\displaystyle \lambda _{1}}$ is within ${\displaystyle \varepsilon n}$ of ${\displaystyle pn}$ and ${\displaystyle \max \left(\left|\lambda _{2}\right|,\left|\lambda _{n}\right|\right)\leq \varepsilon n}$.

These conditions may all be stated in terms of a sequence of graphs ${\displaystyle \{G_{n}\}}$ where ${\displaystyle G_{n}}$ is on ${\displaystyle n}$ vertices with ${\displaystyle (p+o(1)){\binom {n}{2}}}$ edges. For example, the 4-cycle counting condition becomes that the number of copies of any graph ${\displaystyle H}$ in ${\displaystyle G_{n}}$ is ${\displaystyle \left(p^{e(H)}+o(1)\right)e^{v(H)}}$ as ${\displaystyle n\to \infty }$, and the discrepancy condition becomes that ${\displaystyle \left|e(X,Y)-p|X||Y|\right|=o(n^{2})}$, using little-o notation.

A pivotal result about graph pseudorandomness is the Chung–Graham–Wilson theorem, which states that many of the above conditions are equivalent, up to polynomial changes in ${\displaystyle \varepsilon }$[3]. A sequence of graphs which satisfies those conditions is called quasi-random. It is considered particularly surprising[2]^: 9 that the weak condition of having the "correct" 4-cycle density implies the other seemingly much stronger pseudorandomness conditions. Graphs such as the 4-cycle, the density of which in a sequence of graphs is sufficient to test the quasi-randomness of the sequence, are known as forcing graphs.

Some implications in the Chung–Graham–Wilson theorem are clear by the definitions of the conditions: the discrepancy on individual sets condition is simply the special case of the discrepancy condition for ${\displaystyle Y=X}$, and 4-cycle counting is a special case of subgraph counting. In addition, the graph counting lemma, a straightforward generalization of the triangle counting lemma, implies that the discrepancy condition implies subgraph counting.

The fact that 4-cycle counting implies the codegree condition can be proven by a technique similar to the second-moment method. Firstly, the sum of codegrees can be upper-bounded:

${\displaystyle \sum _{u,v\in G}\operatorname {codeg} (u,v)=\sum _{x\in G}\deg(x)^{2}\geq n\left({\frac {2e(G)}{n}}\right)^{2}=\left(p^{2}+o(1)\right)n^{3}.}$

Given 4-cycles, the sum of squares of codegrees is bounded:

${\displaystyle \sum _{u,v}\operatorname {codeg} (u,v)^{2}={\text{Number of labeled copies of }}C_{4}+o(n^{4})\leq \left(p^{4}+o(1)\right)n^{4}.}$

Therefore, the Cauchy–Schwarz inequality gives

${\displaystyle \sum _{u,v\in G}|\operatorname {codeg} (u,v)-p^{2}n|\leq n\left(\sum _{u,v\in G}\left(\operatorname {codeg} (u,v)-p^{2}n\right)^{2}\right)^{1/2},}$

which can be expanded out using our bounds on the first and second moments of ${\displaystyle \operatorname {codeg} }$ to give the desired bound. A proof that the codegree condition implies the discrepancy condition can be done by a similar, albeit trickier, computation involving the Cauchy–Schwarz inequality.

The eigenvalue condition and the 4-cycle condition can be related by noting that the number of labeled 4-cycles in ${\displaystyle G}$ is, up to ${\displaystyle o(1)}$ stemming from degenerate 4-cycles, ${\displaystyle \operatorname {tr} \left(A_{G}^{4}\right)}$, where ${\displaystyle A_{G}}$ is the adjacency matrix of ${\displaystyle G}$. The two conditions can then be shown to be equivalent by invocation of the Courant–Fischer theorem.[3]

The concept of graphs that act like random graphs connects strongly to the concept of graph regularity used in the Szemerédi regularity lemma. For ${\displaystyle \varepsilon >0}$, a pair of vertex sets ${\displaystyle X,Y}$ is called ${\displaystyle \varepsilon }$-regular, if for all subsets ${\displaystyle A\subset X,B\subset Y}$ satisfying ${\displaystyle |A|\geq \varepsilon |X|,|B|\geq \varepsilon |Y|}$, it holds that

${\displaystyle \left|d(X,Y)-d(A,B)\right|\leq \varepsilon ,}$

where ${\displaystyle d(X,Y)}$ denotes the edge density between ${\displaystyle X}$ and ${\displaystyle Y}$: the number of edges between ${\displaystyle X}$ and ${\displaystyle Y}$ divided by ${\displaystyle |X||Y|}$. This condition implies a bipartite analogue of the discrepancy condition, and essentially states that the edges between ${\displaystyle A}$ and ${\displaystyle B}$ behave in a "random-like" fashion. In addition, it was shown by Miklós Simonovits and Vera T. Sós in 1991 that a graph satisfies the above weak pseudorandomness conditions used in the Chung–Graham–Wilson theorem if and only if it possesses a Szemerédi partition where nearly all densities are close to the edge density of the whole graph.[4]