Pseudorandom graph
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 formula_1 is said to be formula_2-"jumbled" for real formula_3 and formula_4 with formula_5 for every subset formula_6 of the vertex set formula_7, where formula_8 is the number of edges among formula_6 (equivalently, the number of edges  in the subgraph induced by the vertex set formula_6). It can be shown that the Erdős–Rényi random graph formula_11 is almost surely formula_12-jumbled. However, graphs with less uniformly distributed edges, for example a graph on formula_13 vertices consisting of an formula_14-vertex complete graph and formula_14 completely independent vertices, are not formula_2-jumbled for any small formula_4, 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 formula_18 be the number of common neighbors of two vertices formula_19 and formula_20, Thomason showed that, given a graph formula_21 on formula_14 vertices with minimum degree formula_23, if formula_24 for every formula_19 and formula_20, then formula_21 is formula_28-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 formula_21 on formula_14 vertices with edge density formula_3 and some formula_32 can satisfy each of these conditions if These conditions may all be stated in terms of a sequence of graphs formula_63 where formula_64 is on formula_14 vertices with formula_66 edges. For example, the 4-cycle counting condition becomes that the number of copies of any graph formula_44 in formula_64 is formula_69 as formula_70, and the discrepancy condition becomes that formula_71, 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 formula_72. A sequence of graphs which satisfies those conditions is called quasi-random. It is considered particularly surprising 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 formula_73, 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: 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 formula_77 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 formula_21 is, up to formula_79 stemming from degenerate 4-cycles, formula_80, where formula_81 is the adjacency matrix of formula_21. The two conditions can then be shown to be equivalent by invocation of the Courant–Fischer theorem. 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 formula_32, a pair of vertex sets formula_33 is called formula_72-regular, if for all subsets formula_86 satisfying formula_87, it holds that where formula_89 denotes the "edge density" between formula_35 and formula_36: the number of edges between formula_35 and formula_36 divided by formula_94. This condition implies a bipartite analogue of the discrepancy condition, and essentially states that the edges between formula_95 and formula_96 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. Sparse pseudorandomness. Chung–Graham–Wilson theorem analogues. The Chung–Graham–Wilson theorem, specifically the implication of subgraph counting from discrepancy, does not follow for sequences of graphs with edge density approaching formula_97, or, for example, the common case of formula_98-regular graphs on formula_14 vertices as formula_70. 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 formula_98-regular graph and a formula_111-vertex complete graph has two eigenvalues of exactly formula_98 but is likely to satisfy the discrepancy property. However, as proven by David Conlon and Yufei Zhao in 2017, slight variants of the discrepancy and eigenvalue conditions for formula_98-regular Cayley graphs are equivalent up to linear scaling in formula_72. 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. Consequences of eigenvalue bounding. A formula_98-regular graph formula_21 on formula_14 vertices is called an "formula_118-graph" if, letting the eigenvalues of the adjacency matrix of formula_21 be formula_120, formula_121. The Alon-Boppana bound gives that formula_122 (where the formula_79 term is as formula_70), and Joel Friedman proved that a random formula_98-regular graph on formula_14 vertices is formula_118 for formula_128. In this sense, how much formula_129 exceeds formula_130 is a general measure of the non-randomness of a graph. There are graphs  with formula_131, which are termed Ramanujan graphs. They have been studied extensively and there are a number of open problems relating to their existence and commonness. Given an formula_118 graph for small formula_129, many standard graph-theoretic quantities can be bounded to near what one would expect from a random graph. In particular, the size of formula_129 has a direct effect on subset edge density discrepancies via the expander mixing lemma. Other examples are as follows, letting formula_21 be an formula_118 graph: Connections to the Green–Tao theorem. Pseudorandom graphs factor prominently in the proof of the Green–Tao theorem . 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 formula_97 in the integers). 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. 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. Pseudorandom graph