In graph theory, a graph is said to be a pseudorandom graph if it obeys certain properties that random graphs obey with high probability. There is no concrete definition of graph pseudorandomness, but there are many reasonable characterizations of pseudorandomness one can consider.

Pseudorandom properties were first formally considered by Andrew Thomason in 1987.^[1][2] He defined a condition called "jumbledness": a graph ${\displaystyle G=(V,E)}$ is said to be ${\displaystyle (p,\alpha )}$-jumbled for real ${\displaystyle p}$ and ${\displaystyle \alpha }$ with ${\displaystyle 0<p<1\leq \alpha }$ if

${\displaystyle \left|e(U)-p{\binom {|U|}{2}}\right|\leq \alpha |U|}$

for every subset ${\displaystyle U}$ of the vertex set ${\displaystyle V}$, where ${\displaystyle e(U)}$ is the number of edges among ${\displaystyle U}$ (equivalently, the number of edges in the subgraph induced by the vertex set ${\displaystyle U}$). It can be shown that the Erdős–Rényi random graph ${\displaystyle G(n,p)}$ is almost surely ${\displaystyle (p,O({\sqrt {np}}))}$-jumbled.^[2]: 6 However, graphs with less uniformly distributed edges, for example a graph on ${\displaystyle 2n}$ vertices consisting of an ${\displaystyle n}$-vertex complete graph and ${\displaystyle n}$ completely independent vertices, are not ${\displaystyle (p,\alpha )}$-jumbled for any small ${\displaystyle \alpha }$, making jumbledness a reasonable quantifier for "random-like" properties of a graph's edge distribution.

Connection to local conditions

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

Chung–Graham–Wilson theorem

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]

Connections to graph regularity

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]

Sparse pseudorandomness

References