Pseudorandom graph

Last updated February 17, 2024

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.

for every subset $U$ of the vertex set $V$ , where $e(U)$ is the number of edges among $U$ (equivalently, the number of edges in the subgraph induced by the vertex set $U$ ). It can be shown that the Erdős–Rényi random graph $G(n,p)$ is almost surely $(p,O({\sqrt {np}}))$ -jumbled.^[2]^: 6 However, graphs with less uniformly distributed edges, for example a graph on $2n$ vertices consisting of an $n$ -vertex complete graph and $n$ completely independent vertices, are not $(p,\alpha )$ -jumbled for any small $\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 $\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 $\operatorname {codeg} (u,v)\leq np^{2}+\ell$ for every $u$ and $v$ , then $G$ is $\left(p,{\sqrt {(p+\ell )n}}\,\right)$ -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 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:^[3] a graph $G$ on $n$ vertices with edge density $p$ and some $\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 $\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 $\varepsilon n^{2}$ of $p{\binom {|X|}{2}}$ .
Subgraph counting: for every graph $H$ , the number of labeled copies of $H$ among the subgraphs of $G$ is within $\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 $\varepsilon n^{4}$ of $p^{4}n^{4}$ .
Codegree: letting $\operatorname {codeg} (u,v)$ be the number of common neighbors of two vertices $u$ and $v$ ,

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

Eigenvalue bounding: If $\lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n}$ are the eigenvalues of the adjacency matrix of $G$ , then $\lambda _{1}$ is within $\varepsilon n$ of $pn$ and $\max \left(\left|\lambda _{2}\right|,\left|\lambda _{n}\right|\right)\leq \varepsilon n$ .

These conditions may all be stated in terms of a sequence of graphs $\{G_{n}\}$ where $G_{n}$ is on $n$ vertices with $(p+o(1)){\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 $\left(p^{e(H)}+o(1)\right)e^{v(H)}$ as $n\to \infty$ , and the discrepancy condition becomes that $\left|e(X,Y)-p|X||Y|\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 $\varepsilon$ ^[3]. 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. 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:

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

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

\sum _{u,v}\operatorname {codeg} (u,v)^{2}={\text{Number of labeled copies of }}C_{4}+o(n^{4})\leq \left(p^{4}+o(1)\right)n^{4}.

Therefore, the Cauchy–Schwarz inequality gives

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

which can be expanded out using our bounds on the first and second moments of $\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, $\operatorname {tr} \left(A_{G}^{4}\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.^[3]

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

\left|d(X,Y)-d(A,B)\right|\leq \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.^[4]

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 $0$ , or, for example, the common case of $d$ -regular graphs on $n$ vertices as $n\to \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 $\varepsilon dn$ of ${\frac {d}{n}}|X||Y|$ .
Sparse eigenvalue bounding: If $\lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n}$ are the eigenvalues of the adjacency matrix of $G$ , then $\max \left(\left|\lambda _{2}\right|,\left|\lambda _{n}\right|\right)\leq \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 $\varepsilon$ .^[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 bounding

A $d$ -regular graph $G$ on $n$ vertices is called an $(n,d,\lambda )$ -graph if, letting the eigenvalues of the adjacency matrix of $G$ be $d=\lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n}$ , $\max \left(\left|\lambda _{2}\right|,\left|\lambda _{n}\right|\right)\leq \lambda$ . The Alon-Boppana bound gives that $\max \left(\left|\lambda _{2}\right|,\left|\lambda _{n}\right|\right)\geq 2{\sqrt {d-1}}-o(1)$ (where the $o(1)$ term is as $n\to \infty$ ), and Joel Friedman proved that a random $d$ -regular graph on $n$ vertices is $(n,d,\lambda )$ for $\lambda =2{\sqrt {d-1}}+o(1)$ .^[6] In this sense, how much $\lambda$ exceeds $2{\sqrt {d-1}}$ is a general measure of the non-randomness of a graph. There are graphs with $\lambda \leq 2{\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,\lambda )$ graph for small $\lambda$ , many standard graph-theoretic quantities can be bounded to near what one would expect from a random graph. In particular, the size of $\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,\lambda )$ graph:

If $d\leq {\frac {n}{2}}$ , the vertex-connectivity $\kappa (G)$ of $G$ satisfies $\kappa (G)\geq d-{\frac {36\lambda ^{2}}{d}}.$ ^[7]
If $\lambda \leq d-2$ , $G$ is $d$ edge-connected. If $n$ is even, $G$ contains a perfect matching.^[2]^: 32
The maximum cut of $G$ is at most ${\frac {n(d+\lambda )}{4}}$ .^[2]^: 33
The largest independent subset of a subset $U\subset V(G)$ in $G$ is of size at least ${\frac {n}{2(d-\lambda )}}\ln \left({\frac {|U|(d-\lambda )}{n(\lambda +1)}}+1\right).$ ^[8]
The chromatic number of $G$ is at most ${\frac {6(d-\lambda )}{\ln \left({\frac {d+1}{\lambda +1}}\right)}}.$ ^[8]

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

Related Research Articles

In graph theory, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion. Expander constructions have spawned research in pure and applied mathematics, with several applications to complexity theory, design of robust computer networks, and the theory of error-correcting codes.

In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.

In mathematics, the spectral radius of a square matrix is the maximum of the absolute values of its eigenvalues. More generally, the spectral radius of a bounded linear operator is the supremum of the absolute values of the elements of its spectrum. The spectral radius is often denoted by $ρ(\cdot)$ .

In mathematics, a low-discrepancy sequence is a sequence with the property that for all values of N, its subsequence x₁, ..., x_N has a low discrepancy.

In the mathematical field of spectral graph theory, a Ramanujan graph is a regular graph whose spectral gap is almost as large as possible. Such graphs are excellent spectral expanders. As Murty's survey paper notes, Ramanujan graphs "fuse diverse branches of pure mathematics, namely, number theory, representation theory, and algebraic geometry". These graphs are indirectly named after Srinivasa Ramanujan; their name comes from the Ramanujan–Petersson conjecture, which was used in a construction of some of these graphs.

In extremal graph theory, Szemerédi’s regularity lemma states that a graph can be partitioned into a bounded number of parts so that the edges between parts are regular. The lemma shows that properties of random graphs can be applied to general graphs like counting the copies of a given subgraph within graphs. Endre Szemerédi proved the lemma over bipartite graphs for his theorem on arithmetic progressions in 1975 and for general graphs in 1978. Variants of the lemma use different notions of regularity and apply to other mathematical objects like hypergraphs.

The expander mixing lemma intuitively states that the edges of certain $-regular graphs are evenly distributed throughout the graph. In particular, the number of edges between two vertex subsets and is always close to the expected number of edges between them in a random -regular graph, namely .$

In the mathematical discipline of graph theory, the expander walk sampling theorem intuitively states that sampling vertices in an expander graph by doing relatively short random walk can simulate sampling the vertices independently from a uniform distribution. The earliest version of this theorem is due to Ajtai, Komlós & Szemerédi (1987), and the more general version is typically attributed to Gillman (1998).

In mathematical analysis, Ekeland's variational principle, discovered by Ivar Ekeland, is a theorem that asserts that there exist nearly optimal solutions to some optimization problems.

In extremal graph theory, the forbidden subgraph problem is the following problem: given a graph $, find the maximal number of edges an -vertex graph can have such that it does not have a subgraph isomorphic to . In this context, is called a forbidden subgraph .$

In graph theory and statistics, a graphon is a symmetric measurable function $, that is important in the study of dense graphs. Graphons arise both as a natural notion for the limit of a sequence of dense graphs, and as the fundamental defining objects of exchangeable random graph models. Graphons are tied to dense graphs by the following pair of observations: the random graph models defined by graphons give rise to dense graphs almost surely, and, by the regularity lemma, graphons capture the structure of arbitrary large dense graphs.$

In coding theory, expander codes form a class of error-correcting codes that are constructed from bipartite expander graphs. Along with Justesen codes, expander codes are of particular interest since they have a constant positive rate, a constant positive relative distance, and a constant alphabet size. In fact, the alphabet contains only two elements, so expander codes belong to the class of binary codes. Furthermore, expander codes can be both encoded and decoded in time proportional to the block length of the code.

In probability theory, concentration inequalities provide mathematical bounds on the probability of a random variable deviating from some value.

In mathematics, singular integral operators of convolution type are the singular integral operators that arise on Rⁿ and Tⁿ through convolution by distributions; equivalently they are the singular integral operators that commute with translations. The classical examples in harmonic analysis are the harmonic conjugation operator on the circle, the Hilbert transform on the circle and the real line, the Beurling transform in the complex plane and the Riesz transforms in Euclidean space. The continuity of these operators on L² is evident because the Fourier transform converts them into multiplication operators. Continuity on L^p spaces was first established by Marcel Riesz. The classical techniques include the use of Poisson integrals, interpolation theory and the Hardy–Littlewood maximal function. For more general operators, fundamental new techniques, introduced by Alberto Calderón and Antoni Zygmund in 1952, were developed by a number of authors to give general criteria for continuity on L^p spaces. This article explains the theory for the classical operators and sketches the subsequent general theory.

In graph theory, the hypergraph removal lemma states that when a hypergraph contains few copies of a given sub-hypergraph, then all of the copies can be eliminated by removing a small number of hyperedges. It is a generalization of the graph removal lemma. The special case in which the graph is a tetrahedron is known as the tetrahedron removal lemma. It was first proved by Nagle, Rödl, Schacht and Skokan and, independently, by Gowers.

In the mathematical field of extremal graph theory, homomorphism density with respect to a graph $is a parameter that is associated to each graph in the following manner:$

The counting lemmas this article discusses are statements in combinatorics and graph theory. The first one extracts information from $-regular pairs of subsets of vertices in a graph, in order to guarantee patterns in the entire graph; more explicitly, these patterns correspond to the count of copies of a certain graph in . The second counting lemma provides a similar yet more general notion on the space of graphons, in which a scalar of the cut distance between two graphs is correlated to the homomorphism density between them and .$

Sidorenko's conjecture is a conjecture in the field of graph theory, posed by Alexander Sidorenko in 1986. Roughly speaking, the conjecture states that for any bipartite graph $and graph on vertices with average degree , there are at least labeled copies of in , up to a small error term. Formally, it provides an intuitive inequality about graph homomorphism densities in graphons. The conjectured inequality can be interpreted as a statement that the density of copies of in a graph is asymptotically minimized by a random graph, as one would expect a fraction of possible subgraphs to be a copy of if each edge exists with probability .$

In spectral graph theory, the Alon–Boppana bound provides a lower bound on the second-largest eigenvalue of the adjacency matrix of a $-regular graph, meaning a graph in which every vertex has degree . The reason for the interest in the second-largest eigenvalue is that the largest eigenvalue is guaranteed to be due to -regularity, with the all-ones vector being the associated eigenvector. The graphs that come close to meeting this bound are Ramanujan graphs, which are examples of the best possible expander graphs.$

The blow-up lemma, proved by János Komlós, Gábor N. Sárközy, and Endre Szemerédi in 1997, is an important result in extremal graph theory, particularly within the context of the regularity method. It states that the regular pairs in the statement of Szemerédi's regularity lemma behave like complete bipartite graphs in the context of embedding spanning graphs of bounded degree.

References

↑ Thomason, Andrew (1987). "Pseudo-random graphs". Annals of Discrete Math. 33: 307–331.
1 2 3 4 5 6 7 Krivelevich, Michael; Sudakov, Benny (2006). "Pseudo-random Graphs" (PDF). More Sets, Graphs and Numbers. Bolyai Society Mathematical Studies. Vol. 15. pp. 199–262. doi:10.1007/978-3-540-32439-3_10. ISBN 978-3-540-32377-8. S2CID 1952661.
1 2 3 Chung, F. R. K.; Graham, R. L.; Wilson, R. M. (1989). "Quasi-Random Graphs" (PDF). Combinatorica. 9 (4): 345–362. doi:10.1007/BF02125347. S2CID 17166765.
↑ 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.
↑ Conlon, David; Zhao, Yufei (2017). "Quasirandom Cayley graphs". Discrete Analysis. 6. arXiv: 1603.03025 . doi:10.19086/da.1294. S2CID 56362932.
↑ 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.
↑ 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. S2CID 16641598.
1 2 Alon, Noga; Krivelevich, Michael; Sudakov, Benny (1999). "List coloring of random and pseudorandom graphs". Combinatorica. 19 (4): 453–472. doi:10.1007/s004939970001. S2CID 5724231.
↑ 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. S2CID 119301206.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[th-1] Thomason, Andrew (1987). "Pseudo-random graphs". Annals of Discrete Math. 33: 307–331.

[ks-2] 1 2 3 4 5 6 7 Krivelevich, Michael; Sudakov, Benny (2006). "Pseudo-random Graphs" (PDF). More Sets, Graphs and Numbers. Bolyai Society Mathematical Studies. Vol. 15. pp. 199–262. doi:10.1007/978-3-540-32439-3_10. ISBN 978-3-540-32377-8. S2CID 1952661.

[cgw-3] 1 2 3 Chung, F. R. K.; Graham, R. L.; Wilson, R. M. (1989). "Quasi-Random Graphs" (PDF). Combinatorica. 9 (4): 345–362. doi:10.1007/BF02125347. S2CID 17166765.

[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.03025 . doi:10.19086/da.1294. S2CID 56362932.

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

[aks-8] 1 2 Alon, Noga; Krivelevich, Michael; Sudakov, Benny (1999). "List coloring of random and pseudorandom graphs". Combinatorica. 19 (4): 453–472. doi:10.1007/s004939970001. S2CID 5724231.

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]