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. He defined a condition called "jumbledness": a graph G = ( V , E ) {\displaystyle G=(V,E)} is said to be ( p , α ) {\displaystyle (p,\alpha )} -jumbled for real p {\displaystyle p} and α {\displaystyle \alpha } with 0 < p < 1 ≤ α {\displaystyle 0<p<1\leq \alpha } if
| e ( U ) − p ( | U | 2 ) | ≤ α | U | {\displaystyle \left|e(U)-p{\binom {|U|}{2}}\right|\leq \alpha |U|}
for every subset U {\displaystyle U} of the vertex set V {\displaystyle V} , where e ( U ) {\displaystyle e(U)} is the number of edges among U {\displaystyle U} (equivalently, the number of edges in the subgraph induced by the vertex set U {\displaystyle U} ). It can be shown that the Erdős–Rényi random graph G ( n , p ) {\displaystyle G(n,p)} is almost surely ( p , O ( n p ) ) {\displaystyle (p,O({\sqrt {np}}))} -jumbled. However, graphs with less uniformly distributed edges, for example a graph on 2 n {\displaystyle 2n} vertices consisting of an n {\displaystyle n} -vertex complete graph and n {\displaystyle n} completely independent vertices, are not ( p , α ) {\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 codeg ( u , v ) {\displaystyle \operatorname {codeg} (u,v)} be the number of common neighbors of two vertices u {\displaystyle u} and v {\displaystyle v} , Thomason showed that, given a graph G {\displaystyle G} on n {\displaystyle n} vertices with minimum degree n p {\displaystyle np} , if codeg ( u , v ) ≤ n p 2 + ℓ {\displaystyle \operatorname {codeg} (u,v)\leq np^{2}+\ell } for every u {\displaystyle u} and v {\displaystyle v} , then G {\displaystyle G} is ( p , ( p + ℓ ) n ) {\displaystyle \left(p,{\sqrt {(p+\ell )n}}\,\right)} -jumbled. 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.
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: a graph G {\displaystyle G} on n {\displaystyle n} vertices with edge density p {\displaystyle p} and some ε > 0 {\displaystyle \varepsilon >0} can satisfy each of these conditions if
… excerpt ends here. Continue reading the full article.
