pseudorandom graph

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 $\backslash operatorname\{codeg\}(u,v)$ be the number of common neighbors of two vertices $u$ and $v$, Thomason showed that, given a graph $G$ on $n$ vertices with minimum degree $np$, if $\backslash operatorname\{codeg\}(u,v)\backslash leq\; np^2+\backslash ell$ for every $u$ and $v$, then $G$ is $\backslash left(\; p,\backslash sqrt\{(p+\backslash ell)n\}\backslash ,\backslash right)$-jumbled.{{r|ks|p=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.{{r|ks|p=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:{{cite journal |last1=Chung |first1=F. R. K. |last2=Graham |first2=R. L. |last3=Wilson |first3=R. M. |title=Quasi-Random Graphs |journal=Combinatorica |date=1989 |volume=9 |issue=4 |pages=345–362 |url=http://www.math.ucsd.edu/~fan/wp/quasirandom1.pdf|doi=10.1007/BF02125347 |s2cid=17166765 }} a graph $G$ on $n$ vertices with edge density $p$ and some $\backslash varepsilon>0$ can satisfy each of these conditions if

• Discrepancy: for any subsets $X,Y$ of the vertex set $V=V(G)$, the number of edges between $X$ and $Y$ is within $\backslash varepsilon\; n^2$ of $p|X||Y|$.
• Discrepancy on individual sets: for any subset $X$ of $V$, the number of edges among $X$ is within $\backslash varepsilon\; n^2$ of $p\backslash binom$

  X

  {2}.
• Subgraph counting: for every graph $H$, the number of labeled copies of $H$ among the subgraphs of $G$ is within $\backslash varepsilon\; n^\{v(H)\}$ of $p^\{e(H)\}n^\{v(H)\}$.
• 4-cycle counting: the number of labeled $4$-cycles among the subgraphs of $G$ is within $\backslash varepsilon\; n^4$ of $p^4n^4$.
• Codegree: letting $\backslash operatorname\{codeg\}(u,v)$ be the number of common neighbors of two vertices $u$ and $v$,

:$\backslash sum\_\{u,v\backslash in\; V\}\backslash big|\backslash operatorname\{codeg\}(u,v)-p^2\; n\backslash big|\backslash leq\; \backslash varepsilon\; n^3.$

• Eigenvalue bounding: If $\backslash lambda\_1\backslash geq\; \backslash lambda\_2\backslash geq\; \backslash cdots\; \backslash geq\; \backslash lambda\_n$ are the eigenvalues of the adjacency matrix of $G$, then $\backslash lambda\_1$ is within $\backslash varepsilon\; n$ of $pn$ and $\backslash max\backslash left(\backslash left|\backslash lambda\_2\backslash right|,\backslash left|\backslash lambda\_n\backslash right|\backslash right)\backslash leq\; \backslash varepsilon\; n$.

These conditions may all be stated in terms of a sequence of graphs $\backslash \{G\_n\backslash \}$ where $G\_n$ is on $n$ vertices with $(p+o(1))\backslash binom\{n\}\{2\}$ edges. For example, the 4-cycle counting condition becomes that the number of copies of any graph $H$ in $G\_n$ is $\backslash left(p^\{e(H)\}+o(1)\backslash right)e^\{v(H)\}$ as $n\backslash to\backslash infty$, and the discrepancy condition becomes that $\backslash left|e(X,Y)-p|X||Y|\backslash 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 $\backslash varepsilon${{r|cgw}}. A sequence of graphs which satisfies those conditions is called quasi-random. It is considered particularly surprising{{r|ks|p=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 $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:

:$\backslash sum\_\{u,v\backslash in\; G\}\; \backslash operatorname\{codeg\}(u,v)=\backslash sum\_\{x\backslash in\; G\}\; \backslash deg(x)^2\backslash ge\; n\backslash left(\backslash frac\{2e(G)\}\{n\}\backslash right)^2=\backslash left(p^2+o(1)\backslash right)n^3.$

Given 4-cycles, the sum of squares of codegrees is bounded:

: $\backslash sum\_\{u,v\}\; \backslash operatorname\{codeg\}(u,v)^2=\backslash text\{Number\; of\; labeled\; copies\; of\; \}C\_4\; +\; o(n^4)\backslash le\; \backslash left(p^4+o(1)\backslash right)n^4.$

Therefore, the Cauchy–Schwarz inequality gives

:$\backslash sum\_\{u,v\backslash in\; G\}|\backslash operatorname\{codeg\}(u,v)-p^2n|\backslash le\; n\backslash left(\backslash sum\_\{u,v\backslash in\; G\}\; \backslash left(\backslash operatorname\{codeg\}(u,v)-p^2n\backslash right)^2\backslash right)^\{1/2\},$

which can be expanded out using our bounds on the first and second moments of $\backslash 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 $G$ is, up to $o(1)$ stemming from degenerate 4-cycles, $\backslash operatorname\{tr\}\backslash left(A\_G^4\backslash right)$, where $A\_G$ is the adjacency matrix of $G$. The two conditions can then be shown to be equivalent by invocation of the Courant–Fischer theorem.{{r|cgw}}

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 $\backslash varepsilon>0$, a pair of vertex sets $X,Y$ is called $\backslash varepsilon$-regular, if for all subsets $A\backslash subset\; X,B\backslash subset\; Y$ satisfying $|A|\backslash geq\backslash varepsilon|X|,|B|\backslash geq\backslash varepsilon|Y|$, it holds that

:$\backslash left|\; d(X,Y)\; -\; d(A,B)\; \backslash right|\; \backslash le\; \backslash varepsilon,$

where $d(X,Y)$ denotes the edge density between $X$ and $Y$: the number of edges between $X$ and $Y$ divided by $|X||Y|$. This condition implies a bipartite analogue of the discrepancy condition, and essentially states that the edges between $A$ and $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.{{cite journal |last1=Simonovits |first1=Miklós |last2=Sós |first2=Vera |title=Szemerédi's partition and quasirandomness |journal=Random Structures and Algorithms |date=1991 |volume=2 |pages=1–10|doi=10.1002/rsa.3240020102 }}

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

• Sparse discrepancy: for any subsets $X,Y$ of the vertex set $V=V(G)$, the number of edges between $X$ and $Y$ is within $\backslash varepsilon\; dn$ of $\backslash frac\{d\}\{n\}|X||Y|$.
• Sparse eigenvalue bounding: If $\backslash lambda\_1\backslash geq\; \backslash lambda\_2\backslash geq\; \backslash cdots\; \backslash geq\; \backslash lambda\_n$ are the eigenvalues of the adjacency matrix of $G$, then $\backslash max\backslash left(\backslash left|\backslash lambda\_2\backslash right|,\backslash left|\backslash lambda\_n\backslash right|\backslash right)\backslash leq\; \backslash varepsilon\; d$.

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 $d$-regular graph and a $d+1$-vertex complete graph has two eigenvalues of exactly $d$ 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 $d$-regular Cayley graphs are equivalent up to linear scaling in $\backslash varepsilon$.{{cite journal |last1=Conlon |first1=David |last2=Zhao |first2=Yufei |title=Quasirandom Cayley graphs |journal=Discrete Analysis |date=2017 |volume=6 |arxiv=1603.03025 |doi=10.19086/da.1294 |s2cid=56362932 }} 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.

A $d$-regular graph $G$ on $n$ vertices is called an $(n,d,\backslash lambda)$-graph if, letting the eigenvalues of the adjacency matrix of $G$ be $d=\backslash lambda\_1\backslash geq\; \backslash lambda\_2\backslash geq\; \backslash cdots\; \backslash geq\; \backslash lambda\_n$, $\backslash max\backslash left(\backslash left|\backslash lambda\_2\backslash right|,\backslash left|\backslash lambda\_n\backslash right|\backslash right)\backslash leq\; \backslash lambda$. The Alon-Boppana bound gives that $\backslash max\backslash left(\backslash left|\backslash lambda\_2\backslash right|,\backslash left|\backslash lambda\_n\backslash right|\backslash right)\backslash geq\; 2\backslash sqrt\{d-1\}-o(1)$ (where the $o(1)$ term is as $n\backslash to\backslash infty$), and Joel Friedman proved that a random $d$-regular graph on $n$ vertices is $(n,d,\backslash lambda)$ for $\backslash lambda=2\backslash sqrt\{d-1\}+o(1)$.{{Cite journal|last=Friedman|first=Joel|date=2003|title=Relative expanders or weakly relatively Ramanujan graphs|journal=Duke Math. J.|volume=118|issue=1|pages=19–35|mr=1978881|doi=10.1215/S0012-7094-03-11812-8}} In this sense, how much $\backslash lambda$ exceeds $2\backslash sqrt\{d-1\}$ is a general measure of the non-randomness of a graph. There are graphs with $\backslash lambda\backslash leq\; 2\backslash sqrt\{d-1\}$, 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 $(n,d,\backslash lambda)$ graph for small $\backslash lambda$, many standard graph-theoretic quantities can be bounded to near what one would expect from a random graph. In particular, the size of $\backslash lambda$ has a direct effect on subset edge density discrepancies via the expander mixing lemma. Other examples are as follows, letting $G$ be an $(n,d,\backslash lambda)$ graph:

• If $d\backslash leq\; \backslash frac\{n\}\{2\}$, the vertex-connectivity $\backslash kappa(G)$ of $G$ satisfies $\backslash kappa(G)\backslash geq\; d-\backslash frac\{36\backslash lambda^2\}\{d\}.${{cite journal |last1=Krivelevich |first1=Michael |last2=Sudakov |first2=Benny |last3=Vu |first3=Van H. |last4=Wormald |first4=Nicholas C. |title=Random regular graphs of high degree |journal=Random Structures and Algorithms |date=2001 |volume=18 |issue=4 |pages=346–363 |doi=10.1002/rsa.1013 |s2cid=16641598 }}
• If $\backslash lambda\backslash leq\; d-2$, $G$ is $d$ edge-connected. If $n$ is even, $G$ contains a perfect matching.{{r|ks|p=32}}
• The maximum cut of $G$ is at most $\backslash frac\{n(d+\backslash lambda)\}\{4\}$.{{r|ks|p=33}}
• The largest independent subset of a subset $U\backslash subset\; V(G)$ in $G$ is of size at least $\backslash frac\{n\}\{2(d-\backslash lambda)\}\backslash ln\backslash left(\backslash frac\{|U|(d-\backslash lambda)\}\{n(\backslash lambda+1)\}+1\backslash right).${{cite journal |last1=Alon |first1=Noga |last2=Krivelevich |first2=Michael |last3=Sudakov |first3=Benny |title=List coloring of random and pseudorandom graphs |journal=Combinatorica |date=1999 |volume=19 |issue=4 |pages=453–472|doi=10.1007/s004939970001 |s2cid=5724231 }}
• The chromatic number of $G$ is at most $\backslash frac\{6(d-\backslash lambda)\}\{\backslash ln\backslash left(\backslash frac\{d+1\}\{\backslash lambda+1\}\backslash right)\}.${{r|aks}}

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 $0$ 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.{{cite journal | arxiv=1403.2957 | title=The Green–Tao theorem: an exposition | first1=David | last1=Conlon | author1link=David Conlon | first2=Jacob | last2=Fox | author2link=Jacob Fox | first3=Yufei | last3=Zhao | mr=3285854 | journal=EMS Surveys in Mathematical Sciences | year=2014 | doi=10.4171/EMSS/6 | volume=1 | issue=2 | pages=249–282 | s2cid=119301206 }} 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.

{{Reflist}}

Category:Graph theory