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.[1][2] He defined a condition called "jumbledness": a graph is said to be -jumbled for real and with if

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

Connection to local conditionsEdit

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 be the number of common neighbors of two vertices and , Thomason showed that, given a graph on vertices with minimum degree , if for every and , then is -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 theoremEdit

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   on   vertices with edge density   and some   can satisfy each of these conditions if

  • Discrepancy: for any subsets   of the vertex set  , the number of edges between   and   is within   of  .
  • Discrepancy on individual sets: for any subset   of  , the number of edges among   is within   of  .
  • Subgraph counting: for every graph  , the number of labeled copies of   among the subgraphs of   is within   of  .
  • 4-cycle counting: the number of labeled  -cycles among the subgraphs of   is within   of  .
  • Codegree: letting   be the number of common neighbors of two vertices   and  ,
 
  • Eigenvalue bounding: If   are the eigenvalues of the adjacency matrix of  , then   is within   of   and  .

These conditions may all be stated in terms of a sequence of graphs   where   is on   vertices with   edges. For example, the 4-cycle counting condition becomes that the number of copies of any graph   in   is   as  , and the discrepancy condition becomes that  , 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  [3]. 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.

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  , 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   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   is, up to   stemming from degenerate 4-cycles,  , where   is the adjacency matrix of  . The two conditions can then be shown to be equivalent by invocation of the Courant–Fischer theorem.[3]

Connections to graph regularityEdit

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  , a pair of vertex sets   is called  -regular, if for all subsets   satisfying  , it holds that

 

where   denotes the edge density between   and  : the number of edges between   and   divided by  . This condition implies a bipartite analogue of the discrepancy condition, and essentially states that the edges between   and   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 pseudorandomnessEdit

Chung–Graham–Wilson theorem analoguesEdit

The Chung–Graham–Wilson theorem, specifically the implication of subgraph counting from discrepancy, does not follow for sequences of graphs with edge density approaching  , or, for example, the common case of  -regular graphs on   vertices as  . The following sparse analogues of the discrepancy and eigenvalue bounding conditions are commonly considered:

  • Sparse discrepancy: for any subsets   of the vertex set  , the number of edges between   and   is within   of  .
  • Sparse eigenvalue bounding: If   are the eigenvalues of the adjacency matrix of  , then  .

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  -regular graph and a  -vertex complete graph has two eigenvalues of exactly   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  -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.

Consequences of eigenvalue boundingEdit

A  -regular graph   on   vertices is called an  -graph if, letting the eigenvalues of the adjacency matrix of   be  ,  . The Alon-Boppana bound gives that   (where the   term is as  ), and Joel Friedman proved that a random  -regular graph on   vertices is   for  .[6] In this sense, how much   exceeds   is a general measure of the non-randomness of a graph. There are graphs with  , 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   graph for small  , many standard graph-theoretic quantities can be bounded to near what one would expect from a random graph. In particular, the size of   has a direct effect on subset edge density discrepancies via the expander mixing lemma. Other examples are as follows, letting   be an   graph:

  • If  , the vertex-connectivity   of   satisfies  [7]
  • If  ,   is   edge-connected. If   is even,   contains a perfect matching.[2]:32
  • The maximum cut of   is at most  .[2]:33
  • The largest independent subset of a subset   in   is of size at least  [8]
  • The chromatic number of   is at most  [8]

Connections to the Green–Tao theoremEdit

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   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.[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.

ReferencesEdit

  1. ^ Thomason, Andrew (1987). "Pseudo-random graphs". Annals of Discrete Math. 33: 307–331.
  2. ^ a b c d e f g Krivelevich, Michael; Sudakov, Benny (2006). "Pseudo-random Graphs" (PDF). More Sets, Graphs and Numbers. Bolyai Society Mathematical Studies. 15: 199–262. doi:10.1007/978-3-540-32439-3_10. ISBN 978-3-540-32377-8.
  3. ^ a b c Chung, F. R. K.; Graham, R. L.; Wilson, R. M. (1989). "Quasi-Random Graphs" (PDF). Combinatorica. 9 (4): 345–362. doi:10.1007/BF02125347.
  4. ^ Simonovits, Miklós; Sós, Vera (1991). "Szemerédi's partition and quasirandomness". Random Structures and Algorithms. 2: 1–10. doi:10.1002/rsa.3240020102.
  5. ^ Conlon, David; Zhao, Yufei (2017). "Quasirandom Cayley graphs". Discrete Analysis. 6. arXiv:1603.03025v4. doi:10.19086/da.1294.
  6. ^ Friedman, Joel (2003). "Relative expanders or weakly relatively Ramanujan graphs". Duke Math. J. 118 (1): 19–35. doi:10.1215/S0012-7094-03-11812-8. MR 1978881.
  7. ^ Krivelevich, Michael; Sudakov, Benny; Vu, Van H.; Wormald, Nicholas C. (2001). "Random regular graphs of high degree". Random Structures and Algorithms. 18 (4): 346–363. doi:10.1002/rsa.1013.
  8. ^ a b Alon, Noga; Krivelevich, Michael; Sudakov, Benny (1999). "List coloring of random and pseudorandom graphs". Combinatorica. 19 (4): 453–472. doi:10.1007/s004939970001.
  9. ^ Conlon, David; Fox, Jacob; Zhao, Yufei (2014). "The Green–Tao theorem: an exposition". EMS Surveys in Mathematical Sciences. 1 (2): 249–282. arXiv:1403.2957. doi:10.4171/EMSS/6. MR 3285854.CS1 maint: ref=harv (link)