5 5. Eigenvalues and quasi-randomness

Definition 170 The spectral gap parameter $\bar\lambda $

Let $G$ be a graph with normalised Laplacian $\mathcal L = I - T^{-1/2}AT^{-1/2}$ ($T$ the diagonal degree matrix, $A$ the adjacency matrix) and eigenvalues $0 = \lambda _0 \le \lambda _1 \le \cdots \le \lambda _{n-1}$. We set

\[ \bar\lambda \; =\; \max _{i\neq 0} |1-\lambda _i|. \]

Thus $\bar\lambda $ measures how far the nontrivial Laplacian eigenvalues stay away from $1$; the eigenvalue quasi-random property asks that $\bar\lambda = o(1)$.

Definition 171 Quasi-random properties for edge density $1/2$ (Chung–Graham–Wilson)

For a graph $G$ on $n$ vertices with edge density $1/2$, consider the following properties (the $o(\cdot )$ estimates are meant as $n\to \infty $).

$\displaystyle \max _{i\neq 0}|1-\lambda _i| = o(1)$ and $G$ is almost regular, i.e. all but $o(n)$ vertices have degree $n/2 + o(n)$.
For each subset $S\subseteq V(G)$, the number $e(S)$ of edges of $G$ with both endpoints in $S$ satisfies $e(S) = \tfrac 14|S|^2 + o(n^2)$.
For each subset $S\subseteq V(G)$ with $|S| = \lfloor n/2\rfloor $, $\; e(S) = \bigl(\tfrac 1{16} + o(1)\bigr)n^2$.
For $u\in V(G)$ let $N(u) = \{ v : u\sim v\} $. Then $\displaystyle \sum _{u,v}\Bigl||N(u)\cap N(v)| - \tfrac n4\Bigr| = o(n^2)$.
For $s\ge 4$ and all graphs $M(s)$ on $s$ vertices, the number $N^{*}_G(M(s))$ of labelled induced subgraphs of $G$ isomorphic to $M(s)$ satisfies $N^{*}_G(M(s)) = (1+o(1))\, n^{s}\, 2^{-\binom s2}$.
For the $2t$-cycle $C_{2t}$, $t\ge 2$, the number $N_G(C_{2t})$ of occurrences of $C_{2t}$ as a labelled subgraph of $G$ is $N_G(C_{2t}) = (1+o(1))\bigl(\tfrac n2\bigr)^{2t}$, and $e(G) \ge (1+o(1))\tfrac {n^2}{4}$.

Theorem 172 Equivalence of the quasi-random properties [Chung–Graham–Wilson]

The properties $P_1,\dots ,P_6$ of Definition 171 are mutually equivalent: any graph (family) satisfying one of them satisfies them all, in the sense that $P(o(1)) \Rightarrow P'(o(1))$ for each pair.

Definition 173 Edges between vertex sets

Let $G$ have vertex set $V$ and edge set $E$. For $X,Y\subseteq V$ (not necessarily disjoint) put

\[ E(X,Y) = \{ (u,v) : u\in X,\ v\in Y,\ \{ u,v\} \in E\} , \qquad e(X,Y) = |E(X,Y)|. \]

Here $E(X,Y)$ consists of ordered pairs, so $e(S,S)$ counts every edge inside $S$ twice. We also write $e(S)$ for the number of (unordered) edges with both endpoints in $S$, so $e(S,S) = 2e(S)$.

Definition 174 Edge density

For a graph $G$ on $n$ vertices with $e$ edges, the edge density is

\[ \rho = \frac{2e}{n^2}. \]

Equivalently, with $A$ the adjacency matrix, $\mathbf1$ the all-ones vector and $J = \mathbf1\mathbf1^{*}$ the all-ones matrix,

\[ \rho = \frac{\langle \mathbf1, A\mathbf1\rangle }{\langle \mathbf1, J\mathbf1\rangle }, \]

since $\langle \mathbf1,A\mathbf1\rangle = 2e$ and $\langle \mathbf1,J\mathbf1\rangle = n^2$.

Definition 175 Discrepancy of a graph

Let $G$ have vertex set $V$, $|V| = n$, and edge density $\rho $. For $S\subseteq V$ the discrepancy of $S$ is

\[ \operatorname {disc}(G,S) = \bigl| e(S,S) - \rho |S|^2 \bigr|. \]

For $0 {\lt} \alpha \le 1$ the $\alpha $-discrepancy of $G$ is the maximum discrepancy over all $S$ with $|S| = \lfloor \alpha n\rfloor $,

\[ \operatorname {disc}(G;\alpha ) = \max _{|S| = \lfloor \alpha n\rfloor } \operatorname {disc}(G,S), \]

and the discrepancy of $G$ is

\[ \operatorname {disc} G = \max _{\alpha } \operatorname {disc}(G;\alpha ). \]

The $\alpha $-discrepancy is a quantitative version of the Ramsey property; determining it is NP-complete in general, which motivates the eigenvalue upper bounds below.

Definition 176 The discrepancy property DISC

Let $\{ G_n\} $ be a family of graphs with $|V(G_n)| = n\to \infty $ and edge densities $\rho = \rho (G_n)$. The family satisfies the discrepancy property $\mathrm{DISC}$ if

\[ \operatorname {disc} G_n = o(n^2), \]

equivalently, for all $X,Y\subseteq V(G_n)$,

\[ \bigl| e(X,Y) - \rho |X|\, |Y| \bigr| = o(n^2). \]

In the general (not necessarily almost-regular) normalisation this is expressed through the volume-weighted count as $\bigl| e(X,Y) - \tfrac {\mathrm{vol}\, X\, \mathrm{vol}\, Y}{\mathrm{vol}\, G}\bigr| = o(\mathrm{vol}\, G)$.

Definition 177 Characteristic vector of a vertex set

For $S\subseteq V$ the characteristic vector $\psi _S : V\to \{ 0,1\} $ is

\[ \psi _S(u) = \begin{cases} 1 & u\in S,\\ 0 & \text{otherwise.}\end{cases} \]

It satisfies $|S| = \langle \psi _S, \mathbf1\rangle $ and, with $T$ the diagonal degree matrix, $\mathrm{vol}\, S = \langle \psi _S, T\mathbf1\rangle = \langle \psi _S, T\psi _S\rangle $.

Lemma 178 Edge counts as a quadratic form

Let $A$ be the adjacency matrix of $G$. For all $X,Y\subseteq V$,

\[ e(X,Y) = \langle \psi _X, A\psi _Y\rangle = \sum _{u\in X}\sum _{v\in Y} A_{uv}, \]

and in particular $e(S,S) = \langle \psi _S, A\psi _S\rangle $.

Proof ▶

Expanding the bilinear form, $\langle \psi _X,A\psi _Y\rangle = \sum _{u,v} \psi _X(u) A_{uv} \psi _Y(v) = \sum _{u\in X,\, v\in Y} A_{uv}$. Since $A_{uv} = 1$ exactly when $\{ u,v\} \in E$ and $0$ otherwise, this counts the ordered pairs $(u,v)$ with $u\in X$, $v\in Y$, $\{ u,v\} \in E$, i.e. $e(X,Y)$. The case $X=Y=S$ is the special case.

Theorem 179 Theorem 5.1

Let $X,Y$ be two subsets of the vertex set $V$ of a graph $G$. Then

\[ \Bigl| e(X,Y) - \frac{\mathrm{vol}\, X\, \mathrm{vol}\, Y}{\mathrm{vol}\, G}\Bigr| \; \le \; \bar\lambda \, \sqrt{\mathrm{vol}\, X\, \mathrm{vol}\, Y}, \]

where $\bar\lambda = \max _{i\neq 0}|1-\lambda _i|$.

Proof ▶

Write $T$ for the diagonal degree matrix and recall the normalised Laplacian $\mathcal L = I - T^{-1/2}AT^{-1/2}$, so that $A = T^{1/2}(I-\mathcal L)T^{1/2}$. By Lemma 178,

\[ e(X,Y) = \psi _X\, A\, \psi _Y^{*} = \psi _X\, T^{1/2}(I-\mathcal L)T^{1/2}\, \psi _Y^{*}. \]

Let $\phi _0,\phi _1,\dots ,\phi _{n-1}$ be an orthonormal basis of eigenvectors of $\mathcal L$ with eigenvalues $0 = \lambda _0 \le \lambda _1 \le \cdots $, where $\phi _0 = T^{1/2}\mathbf1/\sqrt{\mathrm{vol}\, G}$. Expand

\[ T^{1/2}\psi _X = \sum _i a_i\phi _i, \qquad T^{1/2}\psi _Y = \sum _i b_i\phi _i. \]

Since $\phi _i \perp \phi _0$ for $i\ge 1$ and $J = \mathbf1\mathbf1^{*}$, we get $J T^{1/2}\phi _i = 0$ for all $i\ge 1$; equivalently $T^{1/2}JT^{1/2}/\mathrm{vol}\, G = \phi _0\phi _0^{*}$ is the orthogonal projection onto $\phi _0$. Consequently

\[ \frac{\mathrm{vol}\, X\, \mathrm{vol}\, Y}{\mathrm{vol}\, G} = \psi _X\, T^{1/2}\Bigl(\frac{T^{1/2}JT^{1/2}}{\mathrm{vol}\, G}\Bigr)T^{1/2}\, \psi _Y^{*} = a_0 b_0, \]

because $a_0 = \langle \phi _0, T^{1/2}\psi _X\rangle = \tfrac 1{\sqrt{\mathrm{vol}\, G}}\langle \mathbf1, T\psi _X\rangle = \mathrm{vol}\, X/\sqrt{\mathrm{vol}\, G}$ and likewise $b_0 = \mathrm{vol}\, Y/\sqrt{\mathrm{vol}\, G}$. Therefore

\begin{align*} \Bigl| e(X,Y) - \frac{\mathrm{vol}\, X\, \mathrm{vol}\, Y}{\mathrm{vol}\, G}\Bigr| & = \Bigl| \psi _X\, T^{1/2}\Bigl(I-\mathcal L - \frac{T^{1/2}JT^{1/2}}{\mathrm{vol}\, G}\Bigr) T^{1/2}\, \psi _Y^{*}\Bigr| \\ & = \Bigl| \sum _{i\ge 1} a_i b_i (1-\lambda _i)\Bigr| \; \le \; \bar\lambda \sum _{i\ge 1} |a_i|\, |b_i| \; \le \; \bar\lambda \sqrt{\sum _{i\ge 1} a_i^2}\, \sqrt{\sum _{i\ge 1} b_i^2}, \end{align*}

using $|1-\lambda _i|\le \bar\lambda $ and the Cauchy–Schwarz inequality (on $\phi _0$ the operator $I-\mathcal L - \phi _0\phi _0^{*}$ vanishes, so the $i=0$ term drops). Finally

\[ \sum _i a_i^2 = \langle \psi _X, T\psi _X\rangle = \mathrm{vol}\, X, \qquad a_0^2 = \frac{(\mathrm{vol}\, X)^2}{\mathrm{vol}\, G}, \]

so $\sum _{i\ge 1} a_i^2 = \mathrm{vol}\, X - (\mathrm{vol}\, X)^2/\mathrm{vol}\, G = \mathrm{vol}\, X\, \mathrm{vol}\, \overline X/\mathrm{vol}\, G \le \mathrm{vol}\, X$, and similarly $\sum _{i\ge 1} b_i^2 = \mathrm{vol}\, Y\, \mathrm{vol}\, \overline Y/\mathrm{vol}\, G \le \mathrm{vol}\, Y$. Substituting gives the stronger inequality

\[ \Bigl| e(X,Y) - \frac{\mathrm{vol}\, X\, \mathrm{vol}\, Y}{\mathrm{vol}\, G}\Bigr| \le \bar\lambda \, \frac{\sqrt{\mathrm{vol}\, X\, \mathrm{vol}\, \overline X\, \mathrm{vol}\, Y\, \mathrm{vol}\, \overline Y}}{\mathrm{vol}\, G} \le \bar\lambda \, \sqrt{\mathrm{vol}\, X\, \mathrm{vol}\, Y}, \]

the last step because $\mathrm{vol}\, \overline X,\ \mathrm{vol}\, \overline Y \le \mathrm{vol}\, G$.

Theorem 180 Theorem 5.2

Let $X,Y$ be two subsets of the vertex set $V$ of a graph $G$. Then

\begin{equation} \Bigl| e(X,Y) - \frac{\mathrm{vol}\, X\, \mathrm{vol}\, Y}{\mathrm{vol}\, G}\Bigr| \; \le \; \bar\lambda \, \frac{\sqrt{\mathrm{vol}\, X\, \mathrm{vol}\, Y\, \mathrm{vol}\, \overline X\, \mathrm{vol}\, \overline Y}}{\mathrm{vol}\, G}, \tag {5.1} \end{equation}

where $\bar\lambda = \max _{i\neq 0}|1-\lambda _i|$.

Proof ▶

This is exactly the intermediate bound established in the proof of Theorem 179: there we showed $\sum _{i\ge 1}a_i^2 = \mathrm{vol}\, X\, \mathrm{vol}\, \overline X/\mathrm{vol}\, G$ and $\sum _{i\ge 1}b_i^2 = \mathrm{vol}\, Y\, \mathrm{vol}\, \overline Y/\mathrm{vol}\, G$, and applied Cauchy–Schwarz to obtain the displayed right-hand side before weakening it to $\bar\lambda \sqrt{\mathrm{vol}\, X\, \mathrm{vol}\, Y}$.

Corollary 181 Corollary 5.3

Let $X$ be a subset of vertices in a graph $G$. Then

\[ \Bigl| e(X,X) - \frac{(\mathrm{vol}\, X)^2}{\mathrm{vol}\, G}\Bigr| \; \le \; \bar\lambda \, \frac{\mathrm{vol}\, X\, \mathrm{vol}\, \overline X}{\mathrm{vol}\, G} \; \le \; \bar\lambda \, \mathrm{vol}\, X. \]

Proof ▶

Apply Theorem 180 with $Y = X$: $\sqrt{\mathrm{vol}\, X\, \mathrm{vol}\, X\, \mathrm{vol}\, \overline X\, \mathrm{vol}\, \overline X}/\mathrm{vol}\, G = \mathrm{vol}\, X\, \mathrm{vol}\, \overline X/\mathrm{vol}\, G$, and $\mathrm{vol}\, \overline X \le \mathrm{vol}\, G$ gives the final bound $\bar\lambda \, \mathrm{vol}\, X$.

Corollary 182 Corollary 5.4

Let $X$ be a subset of vertices in a $k$-regular graph $G$ on $n$ vertices. Then

\[ \Bigl| e(X,X) - \frac{k|X|^2}{n}\Bigr| \; \le \; k\, \bar\lambda \, |X|. \]

Proof ▶

In a $k$-regular graph $\mathrm{vol}\, X = k|X|$, $\mathrm{vol}\, G = kn$ and $\mathrm{vol}\, \overline X = k(n-|X|)$. Substituting into Corollary 181, $(\mathrm{vol}\, X)^2/\mathrm{vol}\, G = k^2|X|^2/(kn) = k|X|^2/n$, and $\bar\lambda \, \mathrm{vol}\, X\, \mathrm{vol}\, \overline X/\mathrm{vol}\, G = \bar\lambda \, k|X|(n-|X|)/n \le k\, \bar\lambda \, |X|$.

Corollary 183 Corollary 5.5

Let $X$ be a subset of vertices in a graph $G$. Then the edge boundary $\partial X$ satisfies

\[ \frac{|\partial X|}{\mathrm{vol}\, X} \; \ge \; (1-\bar\lambda )\, \frac{\mathrm{vol}\, \overline X}{\mathrm{vol}\, G}. \]

Proof ▶

Every edge incident to $X$ is either internal to $X$ (contributing $2$ to $e(X,X)$ per edge, i.e. counted in $e(X,X)$) or leaves $X$, so $\mathrm{vol}\, X = e(X,X) + |\partial X|$. By Corollary 181, $e(X,X) \le (\mathrm{vol}\, X)^2/\mathrm{vol}\, G + \bar\lambda \, \mathrm{vol}\, X\, \mathrm{vol}\, \overline X/\mathrm{vol}\, G$, hence

\[ |\partial X| = \mathrm{vol}\, X - e(X,X) \ge \mathrm{vol}\, X\Bigl(1 - \frac{\mathrm{vol}\, X}{\mathrm{vol}\, G}\Bigr) - \bar\lambda \, \frac{\mathrm{vol}\, X\, \mathrm{vol}\, \overline X}{\mathrm{vol}\, G} = (1-\bar\lambda )\, \frac{\mathrm{vol}\, X\, \mathrm{vol}\, \overline X}{\mathrm{vol}\, G}, \]

using $1 - \mathrm{vol}\, X/\mathrm{vol}\, G = \mathrm{vol}\, \overline X/\mathrm{vol}\, G$. Dividing by $\mathrm{vol}\, X$ gives the claim.

Proposition 184 Partial answer to Question 1

Suppose $G$ satisfies, for some fixed $\alpha $ with $0\le \alpha {\lt}1$,

\[ \Bigl| e(X,Y) - \frac{\mathrm{vol}\, X\, \mathrm{vol}\, Y}{\mathrm{vol}\, G}\Bigr| \le \alpha \, \frac{\sqrt{\mathrm{vol}\, X\, \mathrm{vol}\, Y\, \mathrm{vol}\, \overline X\, \mathrm{vol}\, \overline Y}}{\mathrm{vol}\, G} \qquad \text{for all } X,Y\subseteq V(G). \]

Then the Cheeger constant satisfies $h_G \ge \tfrac {1-\alpha }{2}$, and consequently

\[ 1 - \lambda _1 \; \le \; 1 - \frac{(1-\alpha )^2}{8}. \]

Proof ▶

Apply the hypothesis with $Y = X$: $e(X,X) \le (\mathrm{vol}\, X)^2/\mathrm{vol}\, G + \alpha \, \mathrm{vol}\, X\, \mathrm{vol}\, \overline X/\mathrm{vol}\, G$. Since $\mathrm{vol}\, X = e(X,X) + |\partial X|$, the same computation as in Corollary 183 (with $\alpha $ in place of $\bar\lambda $) gives

\[ \frac{|\partial X|}{\mathrm{vol}\, X} \ge (1-\alpha )\, \frac{\mathrm{vol}\, \overline X}{\mathrm{vol}\, G}. \]

For any $X$ with $\mathrm{vol}\, X \le \tfrac 12\mathrm{vol}\, G$ we have $\mathrm{vol}\, \overline X \ge \tfrac 12\mathrm{vol}\, G$, so $|\partial X|/\mathrm{vol}\, X \ge (1-\alpha )/2$; taking the minimum over such $X$ yields $h_G \ge (1-\alpha )/2$. Cheeger’s inequality from Chapter 2, $\lambda _1 \ge h_G^2/2$, then gives $\lambda _1 \ge (1-\alpha )^2/8$, i.e. $1-\lambda _1 \le 1 - (1-\alpha )^2/8$.

Construction 185 Question 2 counterexample: a non-almost-regular graph with small (5.2)-error but large discrepancy

Question 2 asks whether the hypothesis

\begin{equation} \Bigl| e(X,Y) - \frac{\mathrm{vol}\, X\, \mathrm{vol}\, Y}{\mathrm{vol}\, G}\Bigr| \le \alpha \, \frac{\sqrt{\mathrm{vol}\, X\, \mathrm{vol}\, Y\, \mathrm{vol}\, \overline X\, \mathrm{vol}\, \overline Y}}{\mathrm{vol}\, G} \qquad (X,Y\subseteq V(G)) \tag {5.2} \end{equation}

forces $\operatorname {disc} G \le 100\alpha $. The answer is negative. Let $H$ have vertex set $A\cup B$ with $|A| = |B| = n/2$ and $A\cap B = \emptyset $, where: the induced subgraph on $A$ is a random graph of edge density $1/2$; the induced subgraph on $B$ is a random graph of edge density $1/4$; and the bipartite subgraph between $A$ and $B$ has edge density $1/3$. Then $H$ satisfies (5.2), yet $\operatorname {disc} H$ is large (about $cn^2$ with $c \ge 0.01$), and $H$ is not even almost regular. Thus "almost regular” is a necessary condition for quasi-randomness.

Theorem 186 Erdős–Spencer discrepancy lower bound

For any graph $G$ of edge density $1/2$,

\[ \operatorname {disc} G \; \ge \; c\, n^{3/2} \]

for an absolute constant $c {\gt} 0$. Hence for graphs with $\bar\lambda \sim 1/\sqrt k$ the eigenvalue upper bound $\operatorname {disc}(G;\alpha ) \le c'\sqrt k\, \alpha n$ is within a constant factor of best possible.

Proposition 187 Discrepancy of a random graph

Let $G$ be a random graph on $n$ vertices with fixed edge density $\rho $. Then, for fixed $\alpha $,

\[ \operatorname {disc}(G;\alpha ) \; \sim \; c\, n^{3/2}, \]

where $c$ depends only on $\rho $ and $\alpha $; one may take $c = \alpha \sqrt{\rho \, H(\alpha )}$ with $H$ the binary entropy function.

Proof ▶

(Sketch.) Assign to each pair the value $f(u,v) = 1-\rho $ if $\{ u,v\} \in E$ and $f(u,v) = -\rho $ otherwise, so that $\bigl|\sum _{u,v\in S} f(u,v)\bigr| = \operatorname {disc}(G,S)$. For $|S| = \alpha n$ the Chernoff bound gives

\[ \Pr [\operatorname {disc}(G,S) {\gt} \beta ] \le \exp \! \bigl(-\beta ^2/(2\rho \alpha ^2 n^2)\bigr), \]

and a union bound over the $\binom {n}{\alpha n}$ sets of size $\alpha n$ yields

\[ \Pr [\operatorname {disc}(G;\alpha ) {\gt} \beta ] \le \binom {n}{\alpha n}\exp \! \bigl(-\beta ^2/(2\rho \alpha ^2 n^2)\bigr). \]

When this quantity is ${\lt}1$ some graph has $\operatorname {disc}(G;\alpha )\le \beta $; choosing $\beta = c\, n^{3/2}$ with $c = \alpha \sqrt{\rho \, H(\alpha )}$ makes it so, giving the upper bound, and a matching lower bound follows by the same second-moment/Chernoff estimate.

Theorem 188 Ramsey’s theorem

✓

There is a number $R(k,\ell )$ such that any graph on $n \ge R(k,\ell )$ vertices contains either a complete graph of size $k$ or an independent set of size $\ell $.

Theorem 189 Erdős’ probabilistic Ramsey lower bound

The diagonal Ramsey number satisfies

\begin{equation} R(k,k) \; {\gt}\; (1+o(1))\, \frac{1}{e\sqrt2}\, k\, 2^{k/2}. \tag {5.3} \end{equation}

In particular there exist graphs on $n$ vertices with no clique and no independent set of size $2\log _2 n$ when $n$ is sufficiently large.

Proof ▶

Colour each of the $\binom n2$ edges of a fixed vertex set of size $n$ present or absent independently with probability $1/2$ (equivalently, choose a graph uniformly among the $2^{\binom n2}$ labelled graphs). For a fixed $k$-subset $W$, the probability that $W$ is a clique or an independent set is $2\cdot 2^{-\binom k2} = 2^{1-\binom k2}$. By the union bound over the $\binom nk$ choices of $W$,

\[ \Pr [\text{some $k$-set is monochromatic}] \le \binom nk\, 2^{1-\binom k2}. \]

If $\binom nk\, 2^{1-\binom k2} {\lt} 1$ then, with positive probability, no $k$-set is a clique or an independent set, so there exists a graph on $n$ vertices avoiding both, whence $R(k,k) {\gt} n$. Estimating $\binom nk \le n^k/k!$ and using Stirling’s formula $k! \sim \sqrt{2\pi k}\, (k/e)^k$, the inequality $\binom nk\, 2^{1-\binom k2} {\lt} 1$ holds for $n \le (1+o(1))\tfrac {1}{e\sqrt2}\, k\, 2^{k/2}$, which gives (5.3). Choosing $n$ at this threshold, the resulting graph has no clique or independent set of size $k = 2\log _2 n$.

Construction 190 Example 5.6: Frankl–Wilson Ramsey graph

Let $q$ be a prime power. Define a graph $G$ with vertex set

\[ V = \bigl\{ F \subseteq \{ 1,\dots ,m\} : |F| = q^2 - 1 \bigr\} \]

and edge set

\[ E = \bigl\{ (F,F') : |F\cap F'| \not\equiv -1 \pmod q \bigr\} . \]

A result of Frankl–Wilson implies that $G$ contains no clique and no independent set of size $\binom {m}{q-1}$. Taking $m = q^3$ produces a graph on $n = \binom {m}{q^2-1}$ vertices containing no clique and no independent set of size

\[ e^{\, c\, (\log n\, \log \log n)^{1/2}}, \]

markedly deviating from the Ramsey bounds of random graphs.

Definition 191 Weighted indicator function

For a graph $G$ with edge density $\rho $, the weighted indicator function $\chi \colon V\times V\to \mathbb {R}$ is

\[ \chi (x,y)=\begin{cases} \, 1-\rho & \text{if } x\sim y,\\[2pt] -\rho & \text{otherwise.}\end{cases} \]

Equivalently $\chi (x,y)=a_{xy}-\rho $, where $a_{xy}$ is the adjacency indicator of the pair $\{ x,y\} $. Note $\chi $ is symmetric. For a $4$-cycle $C$ we set

\[ \chi (C)=\prod _{\{ x,y\} \in C}\chi (x,y). \]

Definition 192 Deviation of a graph [5.3]

The deviation of a graph $G$ with edge density $\rho $ is

\[ \operatorname {dev} G \; =\; \frac{1}{\rho ^4 n^4}\sum _{C}\chi (C) \; =\; \frac{1}{\rho ^4 n^4}\sum _{x,y,z,w}\chi (x,y)\, \chi (y,z)\, \chi (z,w)\, \chi (w,x), \]

where $x,y,z,w$ range independently over all vertices of $G$. In the special case $\rho =\tfrac 12$, the deviation equals $\tfrac {1}{16 n^4}$ times the number of “even” $4$-cycles minus the number of “odd” $4$-cycles, where a $4$-cycle $\{ x,y,z,w\} $ is called even if $\chi (x,y)\chi (y,z)\chi (z,w)\chi (w,x)$ is positive.

Definition 193 Irregularity

The irregularity of a graph $G$ is

\[ \operatorname {irr} G \; :=\; \frac{\rho }{n}\sum _{v\in V(G)}\Big(\frac{1}{\rho _v}-\frac{1}{\rho }\Big), \]

where $|V(G)|=n$, $\rho _v = d_v/n$ and $\rho = \sum _v d_v/n^2$. The smaller $\operatorname {irr} G$ is, the more closely $G$ approximates a regular graph; $\operatorname {irr} G = 0$ if and only if $G$ is regular.

Definition 194 Variance of degrees

The variance of a graph $G$ is

\[ \operatorname {var} G \; =\; \frac{1}{\rho ^2 n}\sum _{v\in V(G)}(\rho _v-\rho )^2 . \]

Lemma 195 [Lemma 5.7]

For any $A\subseteq V(G)$,

\[ \sum _{v\in V(G)}\Big(\frac{1}{\rho _v}-\frac{1}{\rho }\Big)\; \ge \; \frac{(\operatorname {vol} A - |A|\rho n)^2}{\rho ^2 n\, \operatorname {vol} A}. \]

Proof ▶

Using $\sum _v \rho _v = n\rho $ one checks the identity $\frac{1}{\rho _v}\big(1-\frac{\rho _v}{\rho }\big)^2 = \frac{1}{\rho _v}-\frac{2}{\rho }+\frac{\rho _v}{\rho ^2}$, whose sum over all $v$ equals $\sum _v(\frac{1}{\rho _v}-\frac{1}{\rho })$. Hence, restricting the (nonnegative) summands to $A$,

\[ \sum _{v\in V(G)}\Big(\frac{1}{\rho _v}-\frac1\rho \Big) =\sum _{v}\frac{1}{\rho _v}\Big(1-\frac{\rho _v}{\rho }\Big)^2 \ge \sum _{v\in A}\Big(\frac{1}{\rho _v}-\frac2\rho +\frac{\rho _v}{\rho ^2}\Big) =\frac{\operatorname {vol} A-|A|\rho n}{\rho ^2 n}+\sum _{v\in A}\Big(\frac1{\rho _v}-\frac1\rho \Big), \]

where we used $\sum _{v\in A}\rho _v = \operatorname {vol} A/n$. Let $\rho _A=\sum _{v\in A}\rho _v/|A|$ be the average density on $A$; by the arithmetic–harmonic mean inequality $\sum _{v\in A}(\frac{1}{\rho _v}-\frac{1}{\rho _A})\ge 0$. Since $1/\rho _A = |A|n/\operatorname {vol} A$,

\[ \sum _{v\in A}\Big(\frac1{\rho _v}-\frac1\rho \Big) =\sum _{v\in A}\Big(\frac1{\rho _v}-\frac1{\rho _A}+\frac1{\rho _A}-\frac1\rho \Big) \ge |A|\Big(\frac{|A|n}{\operatorname {vol} A}-\frac1\rho \Big) =\frac{(|A|\rho n-\operatorname {vol} A)}{\rho \, \operatorname {vol} A}\, |A|. \]

Writing $D=\operatorname {vol} A-|A|\rho n$ and adding the two contributions,

\[ \sum _{v\in V(G)}\Big(\frac1{\rho _v}-\frac1\rho \Big)\ge \frac{D}{\rho ^2 n}-\frac{D|A|}{\rho \, \operatorname {vol} A} =\frac{D}{\rho }\cdot \frac{\operatorname {vol} A-|A|\rho n}{\rho n\, \operatorname {vol} A} =\frac{D^2}{\rho ^2 n\, \operatorname {vol} A}=\frac{(\operatorname {vol} A-|A|\rho n)^2}{\rho ^2 n\, \operatorname {vol} A}. \qedhere \]

Corollary 196 [Corollary 5.8]

For all $A\subseteq V(G)$,

\[ \big|\, \operatorname {vol} A - |A|\rho n\, \big|\; \le \; \sqrt{\operatorname {irr} G}\, \operatorname {vol} G. \]

Proof ▶

By definition $\sum _v(\frac{1}{\rho _v}-\frac{1}{\rho })=\frac{n}{\rho }\operatorname {irr} G$, so Lemma 195 gives $(\operatorname {vol} A-|A|\rho n)^2\le \frac{n}{\rho }\operatorname {irr} G\cdot \rho ^2 n\, \operatorname {vol} A = \rho n^2\, \operatorname {irr} G\, \operatorname {vol} A$. Since $\rho n^2 = \operatorname {vol} G$ and $\operatorname {vol} A\le \operatorname {vol} G$, the right-hand side is at most $\operatorname {irr} G\, (\operatorname {vol} G)^2$; taking square roots proves the claim.

Lemma 197 [Lemma 5.9]

\[ \sup _{A\subseteq V(G)}\Big|\sum _{v\in A}\Big(\frac{1}{\rho _v}-\frac{1}{\rho }\Big)\Big|\; \le \; \frac{n}{\rho }\big(\operatorname {irr} G+\sqrt{\operatorname {irr} G}\big). \]

Proof ▶

From the identity established in the proof of Lemma 195,

\[ \sum _{v\in A}\Big(\frac1{\rho _v}-\frac1\rho \Big) =\sum _{v\in V(G)}\Big(\frac1{\rho _v}-\frac1\rho \Big)+\frac{|A|\rho n-\operatorname {vol} A}{\rho ^2 n} \le \frac{n}{\rho }\operatorname {irr} G+\frac{|A|\rho n-\operatorname {vol} A}{\rho ^2 n}. \]

By the inequality $(\operatorname {vol} A-|A|\rho n)^2\le \rho n^2\, \operatorname {irr} G\, \operatorname {vol} A$ from the proof of Corollary 196 and $\operatorname {vol} A\le \rho n^2$,

\[ \frac{|A|\rho n-\operatorname {vol} A}{\rho ^2 n}\le \frac{\sqrt{\rho n^2\operatorname {vol} A\, \operatorname {irr} G}}{\rho ^2 n}\le \frac{n}{\rho }\sqrt{\operatorname {irr} G}. \]

Adding the bounds and using the same estimate for $-A$ gives the stated supremum bound.

Theorem 198 [Theorem 5.10]

\[ \operatorname {dev} G \; =\; \frac{1}{\rho ^4 n^4}\sum _{x,y}\big(\, |N_x\cap N_y|-\rho ^2 n\, \big)^2, \]

where $N_x=N(x)=\{ y:y\sim x\} $ and $d_x=|N_x|$.

Proof ▶

Relabelling the $4$-cycle so that $z,w$ are the two vertices adjacent to both $x$ and $y$,

\[ \rho ^4 n^4\operatorname {dev} G=\sum _{x,y,z,w}\chi (x,z)\chi (y,z)\chi (x,w)\chi (y,w) =\sum _{x,y}\Big(\sum _z\chi (x,z)\chi (y,z)\Big)^2 . \]

For fixed $x,y$, splitting the sum over $z$ according to the four cases $z\in N_x\cap N_y$, $N_x\cap \bar N_y$, $\bar N_x\cap N_y$, $\bar N_x\cap \bar N_y$ gives

\[ \sum _z\chi (x,z)\chi (y,z)=\big(|N_x\cap N_y|-\rho ^2 n\big)-\rho \, (d_x-\rho n)-\rho \, (d_y-\rho n). \]

For a regular graph $d_x=d_y=\rho n$, so the degree–deviation terms vanish and $\sum _z\chi (x,z)\chi (y,z)=|N_x\cap N_y|-\rho ^2 n$. Hence

\[ \rho ^4 n^4\operatorname {dev} G=\sum _{x,y}\big(|N_x\cap N_y|-\rho ^2 n\big)^2 . \qedhere \]

Lemma 199 Trace of a matrix power equals the power sum of its eigenvalues

✓

If $M$ is a real symmetric $n\times n$ matrix with eigenvalues $\mu _1,\dots ,\mu _n$, then for every $k\ge 1$,

\[ \operatorname {tr}(M^k)=\sum _{i=1}^n \mu _i^{\, k}. \]

Theorem 200 [Theorem 5.11]

For a regular graph $G$ with Laplacian eigenvalues $\lambda _0=0\le \lambda _1\le \dots \le \lambda _{n-1}$,

\[ \operatorname {dev} G=\sum _{i\neq 0}(1-\lambda _i)^4 . \]

Proof ▶

Let $T$ be the diagonal degree matrix, $J$ the all-ones matrix, and $\mathcal{L}=I-T^{-1/2}AT^{-1/2}$ the normalized Laplacian. Consider

\[ M:=I-\mathcal{L}-\frac{1}{\operatorname {vol} G}\, T^{1/2}J\, (T^{1/2})^{*}. \]

For a regular graph $T=\rho n\, I$ and $\operatorname {vol} G=\rho n^2$, so the last term is $\frac1n J$; the matrix $I-\mathcal{L}$ has eigenvalues $1-\lambda _i$, and subtracting $\frac1n J$ turns the eigenvalue $1-\lambda _0=1$ (on the all-ones eigenvector) into $0$ while leaving the others unchanged. Thus $M$ has eigenvalues $0$ and $1-\lambda _i$ for $i=1,\dots ,n-1$, and by Lemma 199

\[ \sum _{i\neq 0}(1-\lambda _i)^4=\operatorname {tr}(M^4).\tag {5.4} \]

A direct computation of the entries gives $M(x,y)=\dfrac {\chi (x,y)}{\rho n}$ (both for $x\neq y$ and for $x=y$, since $G$ has no loops). Therefore

\[ \operatorname {tr}(M^4)=\sum _{x,y,z,w}\frac{\chi (x,z)\chi (y,z)\chi (x,w)\chi (y,w)}{\rho ^4 n^4}=\operatorname {dev} G, \]

which together with $(5.4)$ proves the theorem.

Theorem 201 [Theorem 5.12]

For any graph $G$,

\[ \operatorname {dev} G\; \le \; \sum _{i\neq 0}(1-\lambda _i)^4+20\sqrt{\operatorname {irr} G}. \]

Proof ▶

Corollary 202 Two-sided deviation–eigenvalue approximation

For any graph $G$,

\[ \Big|\, \operatorname {dev} G-\sum _{i\neq 0}(1-\lambda _i)^4\, \Big|\; \le \; 20\sqrt{\operatorname {irr} G}. \]

Proof ▶

Definition 203 Almost regular property $P_r$

A family of graphs $G$ (with $|V(G)|=n\to \infty $) is almost regular if it satisfies

\[ (P_r)\qquad \operatorname {irr} G=\frac{\rho }{n}\sum _{v\in V(G)}\Big(\frac{1}{\rho _v}-\frac1\rho \Big)=o(1), \]

where $\rho _v=d_v/n$ and $\rho =\sum _v d_v/n^2$. Equivalently, all but $o(n)$ vertices have degree within a $(1+o(1))$ factor of the average degree.

Definition 204 Eigenvalue quasi-random property EIG [5.4]

A family of graphs $G$ has the eigenvalue property (EIG) if

\[ (P_e)\qquad \bar\lambda :=\max _{i\neq 0}|1-\lambda _i|=o(1), \]

where $\lambda _0=0\le \lambda _1\le \dots \le \lambda _{n-1}$ are the eigenvalues of the (normalized) Laplacian of $G$.

Definition 205 Deviation quasi-random property DEV

A family of graphs $G$ has the deviation property if

\[ (P_{\mathrm{dev}})\qquad \operatorname {dev} G=o(1). \]

Lemma 206 Edge-count eigenvalue bound [Theorem 5.2, from §5.2]

For any $X\subseteq V(G)$,

\[ \Big|\, e(X,X)-\frac{(\operatorname {vol} X)^2}{\operatorname {vol} G}\, \Big|\; \le \; \bar\lambda \, \operatorname {vol} X, \qquad \bar\lambda =\max _{i\neq 0}|1-\lambda _i|. \]

Proof ▶

Lemma 207 [Lemma 5.14] and $\operatorname {var} G\le \operatorname {irr} G$

For positive reals $a_1,\dots ,a_n$ with average $a=\frac1n\sum _i a_i$,

\[ \frac{1}{a^2 n^2}\sum _{i=1}^n (a_i-a)^2\; \le \; \frac{a}{n}\sum _{i=1}^n\Big(\frac1{a_i}-\frac1a\Big). \]

Consequently $\operatorname {var} G\le \operatorname {irr} G$.

Proof ▶

Using $\sum _i a_i=na$ one has $\sum _i(\frac1{a_i}-\frac1a)=\sum _i\frac1{a_i}(1-\frac{a_i}{a})^2=\frac1{a^2}\sum _i\frac{(a_i-a)^2}{a_i}$, so the right-hand side equals $\frac1{na}\sum _i\frac{(a_i-a)^2}{a_i}$. By Cauchy–Schwarz,

\[ \sum _i(a_i-a)^2\le \Big(\sum _i|a_i-a|\Big)^2=\Big(\sum _i\frac{|a_i-a|}{\sqrt{a_i}}\sqrt{a_i}\Big)^2\le \Big(\sum _i\frac{(a_i-a)^2}{a_i}\Big)\Big(\sum _i a_i\Big)=an\sum _i\frac{(a_i-a)^2}{a_i}. \]

Dividing by $a^2 n^2$ gives the stated inequality. Taking $a_i=\rho _v$ and $a=\rho $ recovers $\operatorname {var} G\le \operatorname {irr} G$.

Lemma 208 Variance lower bound [(5.5)]

For any nonempty $X\subseteq V(G)$,

\[ \operatorname {var} G\; \ge \; \frac{1}{\rho ^2 n^3|X|}\, \big(\operatorname {vol} X-\rho n|X|\big)^2 . \]

Proof ▶

Restricting the nonnegative summands to $X$ and applying Cauchy–Schwarz,

\[ \operatorname {var} G=\frac1{\rho ^2 n}\sum _{v\in V}(\rho _v-\rho )^2\ge \frac1{\rho ^2 n}\sum _{v\in X}(\rho _v-\rho )^2\ge \frac1{\rho ^2 n|X|}\Big(\sum _{v\in X}(\rho _v-\rho )\Big)^2 . \]

Since $\sum _{v\in X}(\rho _v-\rho )=\frac{\operatorname {vol} X}{n}-\rho |X|=\frac{\operatorname {vol} X-\rho n|X|}{n}$, the last quantity equals $\dfrac {(\operatorname {vol} X-\rho n|X|)^2}{\rho ^2 n^3|X|}$.

Theorem 209 [Theorem 5.13]

For a graph $G$,

\[ \operatorname {disc} G\; \le \; \big(\bar\lambda +2\sqrt{\operatorname {irr} G}\big)\operatorname {vol} G, \qquad \bar\lambda =\max _{i\neq 0}|1-\lambda _i|. \]

(The irregularity $\operatorname {irr} G$ may be replaced by $\operatorname {var} G$, using 

??disc G=_X⊆V(G)|e(X,X)-ρ|X|^2| (the two-set version $\sup _{X,Y}|e(X,Y)-\rho |X||Y||$ differs by at most a constant factor, since $e(X\cup Y,X\cup Y)=e(X,X)+e(Y,Y)+2e(X,Y)$). By Lemma 206 and $\operatorname {vol} G=\rho n^2$,

\[ \operatorname {disc} G\le \sup _{X}\Big|e(X,X)-\frac{(\operatorname {vol} X)^2}{\operatorname {vol} G}\Big|+\Big|\frac{(\operatorname {vol} X)^2}{\operatorname {vol} G}-\rho |X|^2\Big| \le \bar\lambda \, \operatorname {vol} X+\Big|\frac{(\operatorname {vol} X)^2}{\rho n^2}-\rho |X|^2\Big|. \]

Factoring the difference of squares and using $\operatorname {vol} X+\rho n|X|\le 2\rho n^2$,

\[ \frac{(\operatorname {vol} X)^2}{\rho n^2}-\rho |X|^2=\frac{(\operatorname {vol} X-\rho n|X|)(\operatorname {vol} X+\rho n|X|)}{\rho n^2}\le 2(\operatorname {vol} X-\rho n|X|). \]

By Lemma 208 (with $|X|\le n$), $\operatorname {vol} X-\rho n|X|\le \rho n^2\sqrt{\operatorname {var} G}$, and by Lemma 207 $\sqrt{\operatorname {var} G}\le \sqrt{\operatorname {irr} G}$. Hence the correction term is at most $2\rho n^2\sqrt{\operatorname {irr} G}=2\sqrt{\operatorname {irr} G}\, \operatorname {vol} G$, and with $\operatorname {vol} X\le \operatorname {vol} G$,

\[ \operatorname {disc} G\le \bar\lambda \, \operatorname {vol} G+2\sqrt{\operatorname {irr} G}\, \operatorname {vol} G=\big(\bar\lambda +2\sqrt{\operatorname {irr} G}\big)\operatorname {vol} G. \qedhere \]

Proof ▶

Theorem 210 [Theorem 5.15]

For a graph $G$,

\[ \operatorname {disc} G\; \le \; \rho n^2\, (\operatorname {dev} G)^{1/4}, \qquad \operatorname {dev} G\; \le \; \frac{4}{\rho ^4 n^2}\operatorname {disc} G+2\operatorname {var} G\; \le \; \frac{4}{\rho ^4 n^2}\operatorname {disc} G+2\operatorname {irr} G . \]

Proof ▶

First inequality. For any $X,Y\subseteq V$, grouping the deviation sum and applying Cauchy–Schwarz repeatedly,

\[ \begin{aligned} \rho ^4 n^4\operatorname {dev} G& =\sum _{x,y,z,w}\chi (x,y)\chi (y,z)\chi (z,w)\chi (w,x) =\sum _{x,z}\Big(\sum _y\chi (x,y)\chi (y,z)\Big)^2\\ & \ge \sum _{x,z\in X}\Big(\sum _y\chi (x,y)\chi (y,z)\Big)^2 \ge \frac{1}{|X|^2}\Big(\sum _{x,z\in X}\sum _y\chi (x,y)\chi (y,z)\Big)^2\\ & =\frac{1}{|X|^2}\Big(\sum _y\big(\textstyle \sum _{x\in X}\chi (x,y)\big)^2\Big)^2 \ge \frac{1}{|X|^2}\Big(\sum _{y\in Y}\big(\textstyle \sum _{x\in X}\chi (x,y)\big)^2\Big)^2\\ & \ge \frac{1}{|X|^2|Y|^2}\Big(\sum _{y\in Y}\sum _{x\in X}\chi (x,y)\Big)^4 =\frac{1}{|X|^2|Y|^2}\big(e(X,Y)-\rho |X||Y|\big)^4 , \end{aligned} \]

using $\sum _{x\in X,y\in Y}\chi (x,y)=e(X,Y)-\rho |X||Y|$. With $|X|,|Y|\le n$, taking fourth roots gives $|e(X,Y)-\rho |X||Y||\le \sqrt{|X||Y|}\, \rho n\, (\operatorname {dev} G)^{1/4}\le \rho n^2(\operatorname {dev} G)^{1/4}$, whence $\operatorname {disc} G\le \rho n^2(\operatorname {dev} G)^{1/4}$.

Second inequality. By Theorem 198, $\rho ^4 n^4\operatorname {dev} G=\sum _{x,y}(|N_x\cap N_y|-\rho ^2 n)^2$. Fix $x$ and set $W_x=\sum _y(|N_x\cap N_y|-\rho ^2 n)^2$; write $d'_y=|N_x\cap N_y|=e(\{ y\} ,N_x)$, the number of edges from $y$ to $N_x$. Let $X=\{ y:d'_y\le \rho d_x\} $. Since $\sum _{y\in X}d'_y=e(N_x,X)$,

\[ \sum _{y\in X}|d'_y-\rho d_x|=\big|e(N_x,X)-\rho d_x|X|\big|\le \operatorname {disc} G, \qquad \sum _{y\notin X}|d'_y-\rho d_x|=\big|e(N_x,\bar X)-\rho d_x|\bar X|\big|\le \operatorname {disc} G , \]

so $\sum _y|d'_y-\rho d_x|\le 2\operatorname {disc} G$, and since $|d'_y-\rho d_x|\le n$,

\[ \sum _y(d'_y-\rho d_x)^2\le n\sum _y|d'_y-\rho d_x|\le 2n\operatorname {disc} G . \]

Writing $d'_y-\rho ^2 n=(d'_y-\rho d_x)+\rho (d_x-\rho n)$ and using $(a+b)^2\le 2a^2+2b^2$,

\[ W_x\le 2\sum _y(d'_y-\rho d_x)^2+2n\, (\rho d_x-\rho ^2 n)^2\le 4n\operatorname {disc} G+2\rho ^2 n^3(\rho _x-\rho )^2 , \]

where $d_x-\rho n=n(\rho _x-\rho )$. Summing over the $n$ choices of $x$ and using $\sum _x(\rho _x-\rho )^2=\rho ^2 n\operatorname {var} G$,

\[ \rho ^4 n^4\operatorname {dev} G=\sum _x W_x\le 4n^2\operatorname {disc} G+2\rho ^4 n^4\operatorname {var} G . \]

Dividing by $\rho ^4 n^4$ gives $\operatorname {dev} G\le \frac{4}{\rho ^4 n^2}\operatorname {disc} G+2\operatorname {var} G$, and $\operatorname {var} G\le \operatorname {irr} G$ (Lemma 207) yields the last bound.

Theorem 211 Equivalence of quasi-random properties [5.4]

Let $G$ range over a family of graphs satisfying the almost-regular property $P_r$ (i.e. $\operatorname {irr} G=o(1)$), and with edge density $\rho $ bounded away from $0$. Then the following three quasi-random properties are equivalent:

\[ (P_e)\ \ \bar\lambda =o(1),\qquad (P_{\mathrm{disc}})\ \ \operatorname {disc} G=o(\operatorname {vol} G),\qquad (P_{\mathrm{dev}})\ \ \operatorname {dev} G=o(1). \]

Equivalently, $P_e+P_r$, $P_{\mathrm{disc}}+P_r$ and $P_{\mathrm{dev}}+P_r$ all coincide.

Proof ▶

We close the cycle $P_e+P_r\Rightarrow P_{\mathrm{disc}}\Rightarrow P_{\mathrm{dev}}\Rightarrow P_e$.

$P_e+P_r\Rightarrow P_{\mathrm{disc}}$. By Theorem 209, $\operatorname {disc} G\le (\bar\lambda +2\sqrt{\operatorname {irr} G})\operatorname {vol} G$; under $P_e$ and $P_r$ the factor $\bar\lambda +2\sqrt{\operatorname {irr} G}=o(1)$, so $\operatorname {disc} G=o(\operatorname {vol} G)$.

$P_{\mathrm{disc}}+P_r\Rightarrow P_{\mathrm{dev}}$. By the second inequality of Theorem 210, $\operatorname {dev} G\le \frac{4}{\rho ^4 n^2}\operatorname {disc} G+2\operatorname {irr} G$. With $\operatorname {disc} G=o(\operatorname {vol} G)=o(\rho n^2)$ and $\rho =\Theta (1)$ the first term is $o(1)$, and $2\operatorname {irr} G=o(1)$ by $P_r$; hence $\operatorname {dev} G=o(1)$. (Independently, the first inequality $\operatorname {disc} G\le \rho n^2(\operatorname {dev} G)^{1/4}$ gives the reverse $P_{\mathrm{dev}}\Rightarrow P_{\mathrm{disc}}$.)

$P_{\mathrm{dev}}+P_r\Rightarrow P_e$. By Corollary 202, $\sum _{i\neq 0}(1-\lambda _i)^4\le \operatorname {dev} G+20\sqrt{\operatorname {irr} G}=o(1)$ under $P_{\mathrm{dev}}$ and $P_r$. Since $\bar\lambda ^4=\max _{i\neq 0}(1-\lambda _i)^4\le \sum _{i\neq 0}(1-\lambda _i)^4$, we get $\bar\lambda =o(1)$, i.e. $P_e$.

The three implications form a cycle, so $P_e+P_r$, $P_{\mathrm{disc}}+P_r$ and $P_{\mathrm{dev}}+P_r$ are pairwise equivalent.

Proposition 212 Subgraph-counting quasi-random property $P_5(s)$

Let $G$ have edge density $\tfrac 12$ and, for $s\ge 4$, let $M(s)$ be any graph on $s$ vertices; write $N^{*}_G(M(s))$ for the number of labelled induced subgraphs of $G$ isomorphic to $M(s)$. Then the quasi-random properties are equivalent to

\[ (P_5(s))\qquad N^{*}_G(M(s))=(1+o(1))\, n^s\, 2^{-\binom {s}{2}}, \]

and quantitatively

\[ \big|\, N^{*}_G(M(s))-n^s 2^{-\binom {s}{2}}\, \big|\; \le \; n^s\, (\operatorname {dev} G)^{1/4}. \]

In particular, if a quasi-random $G$ of edge density $\tfrac 12$ contains $(1+o(1))\tfrac {n^4}{16}$ labelled copies of $C_4$, then $G$ contains the expected number of copies of every fixed graph.

Proof ▶