Pseudorandom properties were first formally considered by Andrew Thomason in 1987.
[1][2] He defined a condition called "jumbledness": a graph
(equivalently, the number of edges in the subgraph induced by the vertex set
, making jumbledness a reasonable quantifier for "random-like" properties of a graph's edge distribution.
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.
[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
For example, the 4-cycle counting condition becomes that the number of copies of any graph
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
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.
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: Given 4-cycles, the sum of squares of codegrees is bounded: Therefore, the Cauchy–Schwarz inequality gives which can be expanded out using our bounds on the first and second moments of
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 two conditions can then be shown to be equivalent by invocation of the Courant–Fischer theorem.
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] The Chung–Graham–Wilson theorem, specifically the implication of subgraph counting from discrepancy, does not follow for sequences of graphs with edge density approaching
The following sparse analogues of the discrepancy and eigenvalue bounding conditions are commonly considered: It is generally true that this eigenvalue condition implies the corresponding discrepancy condition, but the reverse is not true: the disjoint union of a random large
However, as proven by David Conlon and Yufei Zhao in 2017, slight variants of the discrepancy and eigenvalue conditions for
-regular Cayley graphs are equivalent up to linear scaling in
[5] One direction of this follows from the expander mixing lemma, while the other requires the assumption that the graph is a Cayley graph and uses the Grothendieck inequality.
), and Joel Friedman proved that a random
is a general measure of the non-randomness of a graph.
They have been studied extensively and there are a number of open problems relating to their existence and commonness.
, many standard graph-theoretic quantities can be bounded to near what one would expect from a random graph.
has a direct effect on subset edge density discrepancies via the expander mixing lemma.
The theorem is proven by transferring Szemerédi's theorem, the statement that a set of positive integers with positive natural density contains arbitrarily long arithmetic progressions, to the sparse setting (as the primes have natural density
The transference to sparse sets requires that the sets behave pseudorandomly, in the sense that corresponding graphs and hypergraphs have the correct subgraph densities for some fixed set of small (hyper)subgraphs.
[9] It is then shown that a suitable superset of the prime numbers, called pseudoprimes, in which the primes are dense obeys these pseudorandomness conditions, completing the proof.