Pseudorandom graph

Definition
A pseudorandom graph is a deterministic graph that exhibits structural properties characteristic of graphs generated by a random process, particularly those of the Erdős–Rényi random graph model $G(n,p)$. Such graphs are constructed explicitly, yet they mimic the edge distribution, spectral characteristics, and combinatorial regularities of truly random graphs.

Overview
Pseudorandom graphs were introduced to bridge the gap between probabilistic existence proofs and explicit constructions in combinatorics and theoretical computer science. They are employed in areas such as network design, cryptography, error‑correcting codes, and complexity theory, where the benefits of randomness are desired without reliance on probabilistic methods. The study of pseudorandomness in graphs often parallels the broader field of pseudorandomness in number theory and algorithms.

Etymology/Origin
The term combines “pseudo‑,” meaning false or imitation, with “random graph,” reflecting the intent to imitate the statistical behavior of random graphs while being deterministically defined. The concept emerged in the late 1970s and early 1980s, notably through work by Thomason (1987) on “pseudo‑random graphs” and by Alon, Krivelevich, and Sudakov, among others, who formalized quantitative measures of pseudorandomness.

Characteristics
Typical criteria used to classify a graph as pseudorandom include:

1. Edge density – The number of edges $e(G)$ is close to the expected value $p\binom{n}{2}$ for a given density $p$.
2. Uniform edge distribution – For all vertex subsets $X,Y\subseteq V(G)$ with $|X|,|Y|$ sufficiently large, the number of edges between $X$ and $Y$ satisfies
   $$ \big|e_G(X,Y)-p|X||Y|\big| = o\big(p|X||Y|\big). $$
3. Spectral gap – The adjacency matrix $A$ has its largest eigenvalue $\lambda_1$ close to $pn$ and all other eigenvalues $\lambda_i$ satisfy $|\lambda_i| \leq C\sqrt{pn}$ for a constant $C$. This spectral condition is a strong indicator of uniform edge distribution.
4. Small subgraph counts – The number of copies of any fixed small graph $H$ in $G$ approximates the expectation in $G(n,p)$. For example, the count of triangles is close to $p^3\binom{n}{3}$.
5. Expansion properties – Pseudorandom graphs often have high vertex or edge expansion, meaning every small set of vertices has a large neighbourhood, akin to expander graphs.

Various families satisfy these properties, such as:

• Paley graphs – Constructed from quadratic residues in finite fields.
• Ramanujan graphs – Optimal spectral expanders that meet the Alon–Boppana bound.
• Random regular graphs – Though generated probabilistically, they possess deterministic constructions that emulate their properties.

Related Topics

• Random graph – The probabilistic model $G(n,p)$ serving as the benchmark for pseudorandomness.
• Expander graph – Highly connected sparse graphs; many expanders are also pseudorandom.
• Quasirandomness – A broader notion applied to sequences, permutations, and hypergraphs, sharing similar equivalence theorems.
• Spectral graph theory – The study of eigenvalues of graph matrices, central to quantifying pseudorandomness.
• Explicit constructions – Algorithms that produce pseudorandom graphs deterministically, often using number‑theoretic or algebraic methods.

Pseudorandom graphs continue to be a focal point of research, particularly in constructing networks and algorithms that require the robustness of random structures while maintaining provable guarantees.