From our point of view the most important parameter of random graph
$G(n,p)$
is its edge distribution. This characteristics can be easily handled due to the fact that
$G(n,p)$
is a product probability space with independent appearances of different edges. Below we cite known results on the edge distribution in
$G(n,p)$
.
Theorem 2.1
Let
$p=p\left(n\right)\le 0.99$
. Then almost surely
$G\in G(n,p)$
is such that if
$U$
is any set of
$u$
vertices, then
$$\lefte\left(U\right)p\left(\genfrac{}{}{0ex}{}{u}{2}\right)\right=O\left({u}^{3/2}{p}^{1/2}{log}^{1/2}(2n/u)\right).$$
Theorem 2.2
Let
$p=p\left(n\right)\le 0.99$
. Then almost surely
$G\in G(n,p)$
is such that if
$U,W$
are disjoint sets of vertices satisfying
$u=\leftU\right\le w=\leftW\right$
, then
$$\lefte(U,W)puw\right=O\left({u}^{1/2}w{p}^{1/2}{log}^{1/2}(2n/w)\right).$$
The proof of the above two statements is rather straightforward. Notice that both quantities
$e\left(U\right)$
and
$e(U,W)$
are binomially distributed random variables with parameters
$\left(\genfrac{}{}{0ex}{}{u}{2}\right)$
and
$p$
, and
$uw$
and
$p$
, respectively. Applying standard Chernofftype estimates on the tails of the binomial distribution (see, e.g., Appendix A of [
18]
) and then the union bound, one gets the desired inequalities. It is very instructive to notice that we get less and less control over the edge distribution as the set size becomes smaller. For example, in the probability space
$G(n,1/2)$
every subset is expected to contain half of its potential edges. While this is what happens almost surely for large enough sets due to Theorem 2.1 , there will be almost surely sets of size about
$2{log}_{2}n$
containing all possible edges (i.e. cliques), and there will be almost surely sets of about the same size, containing no edges at all (i.e. independent sets).
For future comparison we formulate the above two theorems in the following unified form:
Corollary 2.3
Let
$p=p\left(n\right)\le 0.99$
. Then almost surely in
$G(n,p)$
for every two (not necessarily) disjoint subsets of vertices
$U,W\subset V$
of cardinalities
$\leftU\right=u,\leftW\right=w$
, the number
$e(U,W)$
of edges of
$G$
with one endpoint in
$U$
and the other one in
$W$
satisfies:
$$\begin{array}{ccc}\lefte\right(U,W)puw=O\left(\sqrt{uwnp}\right).& & \end{array}$$ 
(1)

(A notational agreement here and later in the paper: if an edge
$e$
belongs to the intersection
$U\cap W$
, then
$e$
is counted twice in
$e(U,W)$
.) Similar bounds for edge distribution hold also in the space
${G}_{n,d}$
of
$d$
regular graphs, although they are significantly harder to derive there.
Inequality (
1 ) provides us with a quantitative benchmark, according to which we will later measure the uniformity of edge distribution in pseudorandom graphs on
$n$
vertices with edge density
$p=\leftE\right(G\left)\right\left(\genfrac{}{}{0ex}{}{n}{2}\right)$
It is interesting to draw comparisons between research in random graphs and in pseudorandom graphs. In general, many properties of random graphs are much easier to study than the corresponding properties of pseudorandom graphs, mainly due to the fact that along with the almost uniform edge distribution described in Corollary 2.3 , random graphs possess as well many other nice features, first and foremost of them being that they are in fact very simply defined product probability spaces.
Certain graph properties can be easily shown to hold almost surely in
$G(n,p)$
while they are not necessarily valid in pseudorandom graphs of the same edge density. We will see quite a few such examples in the next section. A general line of research appears to be not to use pseudorandom methods to get new results for random graphs, but rather to try to adapt techniques developed for random graphs to the case of pseudorandom graphs, or alternatively to develop original techniques and methods.
2.2 Thomason's jumbled graphs
In two fundamental papers [
79]
, [
80]
published in 1987 Andrew Thomason introduced the first formal quantitative definition of pseudorandom graphs. It appears quite safe to attribute the launch of the systematic study of pseudorandomness to Thomason's papers.
Thomason used the term ”jumbled” graphs in his papers. A graph
$G=(V,E)$
is said to be
$(p,\alpha )$
jumbled if
$p,\alpha $
are real numbers satisfying
$0<p<1\le \alpha $
if every subset of vertices
$U\subset V$
satisfies:
$$\begin{array}{ccc}\lefte\left(U\right)p\left(\genfrac{}{}{0ex}{}{\leftU\right}{2}\right)\right\le \alpha \leftU\right.& & \end{array}$$ 
(2)

The parameter
$p$
can be thought of as the density of
$G$
, while
$\alpha $
controls the deviation from the ideal distribution. According to Thomason, the word ”jumbled” is intended to convey the fact that the edges are evenly spread throughout the graph.
The motivation for the above definition can be clearly traced to the attempt to compare the edge distribution in a graph
$G$
to that of a truly random graph
$G(n,p)$
. Applying it indeed to
$G(n,p)$
and recalling ( 1 ) we conclude that the random graph
$G(n,p)$
is almost surely
$O\left(\sqrt{np}\right)$
jumbled.
Thomason's definition has several trivial yet very nice features. Observe for example that if
$G$
is
$(p,\alpha )$
jumbled then the complement
$\overline{G}$
is
$(1p,\alpha )$
jumbled. Also, the definition is hereditary – if
$G$
is
$(p,\alpha )$
jumbled, then so is every induced subgraph
$H$
of
$G$
.
Note that being
$(p,\Theta (np\left)\right)$
jumbled for a graph
$G$
on
$n$
vertices and
$\left(\genfrac{}{}{0ex}{}{n}{2}\right)p$
edges does not say too much about the edge distribution of
$G$
as the number of edges in linear sized sets can deviate by a percentage from their expected value. However as we shall see very soon if
$G$
is known to be
$(p,o(np\left)\right)$
jumbled, quite a lot can be said about its properties. Of course, the smaller is the value of
$\alpha $
, the more uniform or jumbled is the edge distribution of
$G$
. A natural question is then how small can be the parameter
$\alpha =\alpha (n,p)$
for a graph
$G=(V,E)$
on
$\leftV\right=n$
vertices with edge density
$p=\leftE\right\left(\genfrac{}{}{0ex}{}{n}{2}\right)$
? Erdős and Spencer proved in [
35]
that
$\alpha $
satisfies
$\alpha =\Omega \left(\sqrt{n}\right)$
for a constant
$p$
; their method can be extended to show
$\alpha =\Omega \left(\sqrt{np}\right)$
for all values of
$p=p\left(n\right)$
. We thus may think about
$(p,O(\sqrt{np}\left)\right)$
jumbled graphs on
$n$
vertices as in a sense best possible pseudorandom graphs.
Although the fact that
$G$
is
$(p,\alpha )$
jumbled carries in it a lot of diverse information on the graph, it says almost nothing (directly at least) about small subgraphs, i.e. those spanned by subsets
$U$
of size
$\leftU\right=o(\alpha /p)$
. Therefore in principle a
$(p,\alpha )$
jumbled graph can have subsets of size
$\leftU\right=O(\alpha /p)$
spanning by a constant factor less or more edges then predicted by the uniform distribution. In many cases however quite a meaningful local information (such as the presence of subgraphs of fixed size) can still be salvaged from global considerations as we will see later.
Condition (
2 ) has obviously a global nature as it applies to all subsets of
$G$
, and there are exponentially many of them. Therefore the following result of Thomason, providing a sufficient condition for pseudorandomness based on degrees and codegrees only, carries a certain element of surprise in it.
Theorem 2.4
[
79]
Let
$G$
be a graph on
$n$
vertices with minimum degree
$np$
. If no pair of vertices of
$G$
has more than
$n{p}^{2}+l$
common neighbors, then
$G$
is
$(p,\sqrt{(p+l)n})$
jumbled.
The above theorem shows how the pseudorandomness condition of ( 2 ) can be ensured/checked by testing only a polynomial number of easily accessible conditions. It is very useful for showing that specific constructions are jumbled. Also, it can find algorithmic applications, for example, a very similar approach has been used by Alon, Duke, Lefmann, Rödl and Yuster in their Algorithmic Regularity Lemma [
9]
. As observed by Thomason, the minimum degree condition of Theorem 2.4 can be dropped if we require that every pair of vertices has
$(1+o(1\left)\right)n{p}^{2}$
common neighbors. One cannot however weaken the conditions of the theorem so as to only require that every edge is in at most
$n{p}^{2}+l$
triangles.
Another sufficient condition for pseudorandomness, this time of global nature, has also been provided in [
79]
, [
80]
:
Theorem 2.5
[
79]
Let
$G$
be a graph of order
$n$
, let
$\eta n$
be an integer between 2 and
$n2$
, and let
$\omega >1$
be a real number. Suppose that each induced subgraph
$H$
of order
$\eta n$
satisfies
$\lefte\right(H)p\left(\genfrac{}{}{0ex}{}{\eta n}{2}\right)\le \eta n\alpha $
. Then
$G$
is
$(p,7\sqrt{n\alpha /\eta}/(1\eta \left)\right)$
jumbled. Moreover
$G$
contains a subset
$U\subseteq V\left(G\right)$
of size
$\leftU\right\ge \left(1\frac{380}{n(1\eta {)}^{2}w}\right)n$
such that the induced subgraph
$G\left[U\right]$
is
$(p,\omega \alpha )$
jumbled.
Thomason also describes in [
79]
, [
80]
several properties of jumbled graphs. We will not discuss these results in details here as we will mostly adopt a different approach to pseudorandomness.
Occasionally however we will compare some of later results to those obtained by Thomason.
2.3 Equivalent definitions of weak pseudorandomness
Let us go back to the jumbledness condition ( 2 ) of Thomason. As we have already noted it becomes nontrivial only when the error term in ( 2 ) is
$o\left({n}^{2}p\right)$
. Thus the latter condition can be considered as the weakest possible condition for pseudorandomness.
Guided by the above observation we now define the notion of weak pseudorandomness as follows. Let
$\left({G}_{n}\right)$
be a sequence of graphs, where
${G}_{n}$
has
$n$
vertices. Let also
$p=p\left(n\right)$
is a parameter (
$p\left(n\right)$
is a typical density of graphs in the sequence). We say that the sequence
$\left({G}_{n}\right)$
is weakly pseudorandom if the following condition holds:
$$\begin{array}{ccc}\text{For all subsets}U\subseteq V\left({G}_{n}\right)\text{,}\lefte\left(U\right)p\left(\genfrac{}{}{0ex}{}{\leftU\right}{2}\right)\right=o\left({n}^{2}p\right).& & \end{array}$$ 
(3)

For notational convenience we will frequently write
$G={G}_{n}$
, tacitly assuming that
$\left(G\right)$
is in fact a sequence of graphs.
Notice that the error term in the above condition of weak pseudorandomness does not depend on the size of the subset
$U$
. Therefore it applies essentially only to subsets
$U$
of linear size, ignoring subsets
$U$
of size
$o\left(n\right)$
. Hence ( 3 ) is potentially much weaker than Thomason's jumbledness condition ( 2 ).
Corollary
2.3 supplies us with the first example of weakly pseudorandom graphs – a random graph
$G(n,p)$
is weakly pseudorandom as long as
$p\left(n\right)$
satisfies
$np\to \infty $
. We can thus say that if a graph
$G$
on
$n$
vertices is weakly pseudorandom for a parameter
$p$
, then the edge distribution of
$G$
is close to that of
$G(n,p)$
.
In the previous subsection we have already seen examples of conditions implying pseudorandomness.
In general one can expect that conditions of various kinds that hold almost surely in
$G(n,p)$
may imply or be equivalent to weak pseudorandomness of graphs with edge density
$p$
.
Let us first consider the case of the constant edge density
$p$
. This case has been treated extensively in the celebrated paper of Chung, Graham and Wilson from 1989 [
26]
, where they formulated several equivalent conditions for weak pseudorandomness. In order to state their important result we need to introduce some notation.
Let
$G=(V,E)$
be a graph on
$n$
vertices. For a graph
$L$
we denote by
${N}_{G}^{*}\left(L\right)$
the number of labeled induced copies of
$L$
in
$G$
, and by
${N}_{G}\left(L\right)$
the number of labeled not necessarily induced copies of
$L$
in
$G$
. For a pair of vertices
$x,y\in V\left(G\right)$
, we set
$s(x,y)$
to be the number of vertices of
$G$
joined to
$x$
and
$y$
the same way: either to both or to none. Also,
$codeg(x,y)$
is the number of common neighbors of
$x$
and
$y$
in
$G$
. Finally, we order the eigenvalues
${\lambda}_{i}$
of the adjacency matrix
$A\left(G\right)$
so that
$\left{\lambda}_{1}\right\ge \left{\lambda}_{2}\right\ge \dots \ge \left{\lambda}_{n}\right$
.
Theorem 2.6
[
26]
Let
$p\in (0,1)$
be fixed. For any graph sequence
$\left({G}_{n}\right)$
the following properties are equivalent:

${P}_{1}\left(l\right)$
:
For a fixed
$l\ge 4$
for all graphs
$L$
on
$l$
vertices,
$${N}_{G}^{*}\left(L\right)=(1+o(1\left)\right){n}^{l}{p}^{\leftE\right(L\left)\right}(1p{)}^{\left(\genfrac{}{}{0ex}{}{l}{2}\right)\leftE\right(L\left)\right}.$$

${P}_{2}\left(t\right)$
:
Let
${C}_{t}$
denote the cycle of length
$t$
. Let
$t\ge 4$
be even,
$$e\left({G}_{n}\right)=\frac{{n}^{2}p}{2}+o\left({n}^{2}\right)\text{and}{N}_{G}\left({C}_{t}\right)\le (np{)}^{t}+o({n}^{t}).$$

${P}_{3}$
:
$e\left({G}_{n}\right)\ge \frac{{n}^{2}p}{2}+o\left({n}^{2}\right)\text{and}{\lambda}_{1}=(1+o(1\left)\right)np,{\lambda}_{2}=o\left(n\right).$

${P}_{4}$
:
For each subset
$U\subset V\left(G\right)$
,
$e\left(U\right)=\frac{p}{2}U{}^{2}+o({n}^{2})$
.

${P}_{5}$
:
For each subset
$U\subset V\left(G\right)$
with
$\leftU\right=\lfloor \frac{n}{2}\rfloor $
, we have
$e\left(U\right)=\left(\frac{p}{8}+o\left(1\right)\right){n}^{2}.$

${P}_{6}$
:
${\sum}_{x,y\in V}\lefts\right(x,y)({p}^{2}+(1p{)}^{2})n=o({n}^{3})$
.

${P}_{7}$
:
${\sum}_{x,y\in V}\leftcodeg\right(x,y){p}^{2}n=o\left({n}^{3}\right)$
.
Note that condition
${P}_{4}$
of this remarkable theorem is in fact identical to our condition ( 3 ) of weak pseudorandomness. Thus according to the theorem all conditions
${P}_{1}$
–
${P}_{3}$
,
${P}_{5}{P}_{7}$
are in fact equivalent to weak pseudorandomness!
As noted by Chung et al. probably the most surprising fact (although possibly less surprising for the reader in view of Theorem
2.4 ) is that apparently the weak condition
${P}_{2}\left(4\right)$
is strong enough to imply weak pseudorandomness.
It is quite easy to add another condition to the equivalence list of the above theorem: for all
$U,W\subset V$
,
$e(U,W)=p\leftU\right\leftW\right+o\left({n}^{2}\right)$
.
A condition of a very different type, related to the celebrated Szemerédi Regularity Lemma has been added to the above list by Simonovits and Sós in [
73]
. They showed that if a graph
$G$
possesses a Szemerédi partition in which almost all pairs have density
$p$
, then
$G$
is weakly pseudorandom, and conversely if
$G$
is weakly pseudorandom then in every Szemerédi partition all pairs are regular with density
$p$
. An extensive background on the Szemerédi Regularity Lemma, containing in particular the definitions of the above used notions, can be found in a survey paper of Komlós and Simonovits [
55]
.
The reader may have gotten the feeling that basically every property of random graphs
$G(n,p)$
ensures weak pseudorandomness. This feeling is quite misleading, and one should be careful while formulating properties equivalent to pseudorandomness. Here is an example provided by Chung et al. Let
$G$
be a graph with vertex set
$\{1,\dots ,4n\}$
defined as follows: the subgraph of
$G$
spanned by the first
$2n$
vertices is a complete bipartite graph
${K}_{n,n}$
, the subgraph spanned by the last
$2n$
vertices is the complement of
${K}_{n,n}$
, and for every pair
$(i,j),1\le i\le 2n,2n+1\le j\le 4n$
, the edge
$(i,j)$
is present in
$G$
independently with probability
$0.5$
. Then
$G$
is almost surely a graph on
$4n$
vertices with edge density
$0.5$
. One can verify that
$G$
has properties
${P}_{1}\left(3\right)$
and
${P}_{2}(2t+1)$
for every
$t\ge 1$
, but is obviously very far from being pseudorandom (contains a clique and an independentset of one quarter of its size). Hence
${P}_{1}\left(3\right)$
and
${P}_{2}(2t+1)$
are not pseudorandom properties. This example shows also the real difference between even and odd cycles in this context – recall that Property
${P}_{2}\left(2t\right)$
does imply pseudorandomness.
A possible explanation to the above described somewhat disturbing phenomenon has been suggested by Simonovits and Sós in [
74]
. They noticed that the above discussed properties are not hereditary in the sense that the fact that the whole graph
$G$
possesses one of these properties does not imply that large induced subgraphs of
$G$
also have it. A property is called hereditary in this context if it is assumed to hold for all sufficiently large subgraphs
$F$
of our graph
$G$
with the same error term as for
$G$
. Simonovits and Sós proved that adding this hereditary condition gives significant extra strength to many properties making them pseudorandom.
Theorem 2.7
[
74]
Let
$L$
be a fixed graph on
$l$
vertices, and let
$p\in (0,1)$
be fixed. Let
$\left({G}_{n}\right)$
be a sequence of graphs. If for every induced subgraph
$H\subseteq G$
on
$h$
vertices,
$${N}_{H}\left(L\right)={p}^{\leftE\right(L\left)\right}{h}^{l}+o\left({n}^{l}\right),$$
then
$\left({G}_{n}\right)$
is weakly pseudorandom, i.e. property
${P}_{4}$
holds.
Two main distinctive features of the last result compared to Theorem 2.6 are: (a)
${P}_{1}\left(3\right)$
assumed hereditarily implies pseudorandomness; and (b) requiring the right number of copies of a single graph
$L$
on
$l$
vertices is enough, compared to Condition
${P}_{1}\left(l\right)$
required to hold for all graphs on
$l$
vertices simultaneously.
Let us switch now to the case of vanishing edge density
$p\left(n\right)=o\left(1\right)$
. This case has been treated in two very recent papers of Chung and Graham [
25]
and of Kohayakawa, Rödl and Sissokho [
50]
.
Here the picture becomes significantly more complicated compared to the dense case. In particular, there exist graphs with very balanced edge distribution not containing a single copy of some fixed subgraphs (see the ErdősRényi graph and the Alon graph in the next section (Examples 6, 9, resp.)).
In an attempt to find properties equivalent to weak pseudorandomness in the sparse case, Chung and Graham define the following properties in [
25]
:
CIRCUIT(
$t$
): The number of closed walks
${w}_{0},{w}_{1},\dots ,{w}_{t}={w}_{0}$
of length
$t$
in
$G$
is
$(1+o(1\left)\right)(np{)}^{t}$
; CYCLE(
$t$
): The number of labeled
$t$
cycles in
$G$
is
$(1+o(1\left)\right)(np{)}^{t}$
; EIG: The eigenvalues
${\lambda}_{i}$
,
$\left{\lambda}_{1}\right\ge \left{\lambda}_{2}\right\ge \dots \left{\lambda}_{n}\right$
, of the adjacency matrix of
$G$
satisfy:
$$\begin{array}{ccc}{\lambda}_{1}& =& (1+o(1\left)\right)np,\end{array}$$  
$$\begin{array}{ccc}\left{\lambda}_{i}\right& =& o\left(np\right),i>1.\end{array}$$  
DISC: For all
$X,Y\subset V\left(G\right)$
,
$$\lefte\right(X,Y)pX\left\rightY\left\right=o\left(p{n}^{2}\right).$$
(DISC here is in fact DICS(1) in [
25]
).
Theorem 2.8
[
25]
Let
$(G={G}_{n}:n\to \infty )$
be a sequence of graphs with
$e\left({G}_{n}\right)=(1+o(1\left)\right)p\left(\genfrac{}{}{0ex}{}{n}{2}\right)$
.
Then the following implications hold for all
$t\ge 1$
:
$$CIRCUIT\left(2t\right)\Rightarrow EIG\Rightarrow DISC.$$
Proof. To prove the first implication, let
$A$
be the adjacency matrix of
$G$
, and consider the trace
$Tr\left({A}^{2t}\right)$
. The
$(i,i)$
entry of
${A}^{2t}$
is equal to the number of closed walks of length
$2t$
starting and ending at
$i$
, and hence
$Tr\left({A}^{2t}\right)=(1+o(1\left)\right)(np{)}^{2t}$
. On the other hand, since
$A$
is symmetric it is similar to the diagonal matrix
$D=diag({\lambda}_{1},{\lambda}_{2},\dots ,{\lambda}_{n})$
, and therefore
$Tr\left({A}^{2t}\right)={\sum}_{i=1}^{2t}{\lambda}_{i}^{2t}$
. We obtain:
$${\sum}_{i=1}^{n}{\lambda}_{i}^{2t}=(1+o(1\left)\right)(np{)}^{2t}.$$
Since the first eigenvalue of
$G$
is easily shown to be as large as its average degree, it follows that
${\lambda}_{1}\ge 2\leftE\right(G\left)\right/\leftV\right(G\left)\right=(1+o(1\left)\right)np$
. Combining these two facts we derive that
${\lambda}_{1}=(1+o(1\left)\right)np$
and
$\left{\lambda}_{i}\right=o\left(np\right)$
as required.
The second implication will be proven in the next subsection.
$\square $
Both reverse implications are false in general. To see why
$DISC\Rightarrow \u0338EIG$
take a graph
${G}_{0}$
on
$n1$
vertices with all degrees equal to
$(1+o(1\left)\right){n}^{0.1}$
and having property
$DISC$
(see next section for examples of such graphs). Now add to
${G}_{0}$
a vertex
${v}^{*}$
and connect it to any set of size
${n}^{0.8}$
in
${G}_{0}$
, let
$G$
be the obtained graph. Since
$G$
is obtained from
${G}_{0}$
by adding
$o\left(\rightE\left({G}_{0}\right)$
edges,
$G$
stillsatisfies
$DISC$
. On the other hand,
$G$
contains a star
$S$
of size
${n}^{0.8}$
with a center at
${v}^{*}$
, and hence
${\lambda}_{1}\left(G\right)\ge {\lambda}_{1}\left(S\right)=\sqrt{{n}^{0.8}1}\gg \leftE\right(G\left)\right/n$
(see, e.g. Chapter 11 of [
64]
for the relevant proofs). This solves an open question from [
25]
.
The ErdősRényi graph from the next section is easily seen to satisfy
$EIG$
, but fails to satisfy
$CIRCUIT\left(4\right)$
. Chung and Graham provide an alternative example in [
25]
(Example 1).
The above discussion indicates that one probably needs to impose some additional condition on the graph
$G$
to glue all these pieces together and to make the above stated properties equivalent.
One such condition has been suggested by Chung and Graham who defined:
U(
$t$
): For some absolute constant
$c$
, all degrees in
$G$
satisfy:
$d\left(v\right)<cnp$
, and for every pair of vertices
$x,y\in G$
the number
${e}_{t1}(x,y)$
of walks of length
$t1$
from
$x$
to
$y$
satisfies:
${e}_{t1}(x,y)\le c{n}^{t2}{p}^{t1}$
.
Notice that
$U\left(t\right)$
can only hold for
$p>{c}^{\prime}{n}^{1+1/(t1)}$
, where
${c}^{\prime}$
depends on
$c$
. Also, every dense graph (
$p=\Theta \left(1\right)$
) satisfies
$U\left(t\right)$
.
As it turns out adding property
$U\left(t\right)$
makes all the above defined properties equivalent and thus equivalent to the notion of weak pseudorandomness (that can be identified with property
$DISC$
):
Theorem 2.9
[
25]
Suppose for some constant
$c>0$
,
$p\left(n\right)>c{n}^{1+1/(t1)}$
, where
$t\ge 2$
. For any family of graphs
${G}_{n}$
,
$\leftE\right({G}_{n}\left)\right=(1+o(1\left)\right)p\left(\genfrac{}{}{0ex}{}{n}{2}\right)$
, satisfying
$U\left(t\right)$
, the following properties are all equivalent:
$CIRCUIT\left(2t\right),CYCLE\left(2t\right),EIG$
and
$DISC$
.
Theorem 2.9 can be viewed as a sparse analog of Theorem 2.6 as it also provides a list of conditions equivalent to weak pseudorandomness.
Further properties implying or equivalent to pseudorandomness, including local statistics conditions, are given in [
50]
.
2.4 Eigenvalues and pseudorandom graphs
In this subsection we describe an approach to pseudorandomness based on graph eigenvalues – the approach most frequently used in this survey. Although the eigenvaluebased condition is not as general as the jumbledness condition of Thomason or some other properties described in the previous subsection, its power and convenience are so appealing that they certainly constitute a good enough reason to prefer this approach. Below we first provide a necessary background on graph spectra and then derive quantitative estimates connecting the eigenvalue gap and edge distribution.
Recall that the
adjacency matrix of a graph
$G=(V,E)$
with vertex set
$V=\{1,\dots ,n\}$
is an
$n$
by
$n$
matrix whose entry
${a}_{ij}$
is 1 if
$(i,j)\in E\left(G\right)$
, and is 0 otherwise. Thus
$A$
is a
$0,1$
symmetric matrix with zeroes along the main diagonal, and we can apply the standard machinery of eigenvalues and eigenvectors of real symmetric matrices. It follows that all eigenvalues of
$A$
(usually also called the eigenvalues of the graph
$G$
itself ) are real, and we denote them by
${\lambda}_{1}\ge {\lambda}_{2}\ge \dots \ge {\lambda}_{n}$
. Also, there is an orthonormal basis
$B=\{{x}_{1},\dots ,{x}_{n}\}$
of the euclidean space
${R}^{n}$
composed of eigenvectors of
$A$
:
$A{x}_{i}={\lambda}_{i}{x}_{i}$
,
${x}_{i}^{t}{x}_{i}=1$
,
$i=1,\dots ,n$
. The matrix
$A$
can be decomposed then as:
$A={\sum}_{i=1}^{n}{\lambda}_{i}{x}_{i}{x}_{i}^{t}$
– the so called spectral decomposition of
$A$
. (Notice that the product
$x{x}^{t}$
,
$x\in {R}^{n}$
, is an
$n$
by
$n$
matrix of rank 1; if
$x,y,z\in {R}^{n}$
then
${y}^{t}\left(x{x}^{t}\right)z=\left({y}^{t}x\right)\left({x}^{t}z\right)$
). Every vector
$y\in {R}^{n}$
can be easily represented in basis
$B$
:
$y={\sum}_{i=1}^{n}\left({y}^{t}{x}_{i}\right){x}_{i}$
. Therefore, for
$y,z\in {R}^{n}$
,
${y}^{t}z={\sum}_{i=1}^{n}\left({y}^{t}{x}_{i}\right)\left({z}^{t}{x}_{i}\right)$
and
$\parallel y{\parallel}^{2}={y}^{t}y={\sum}_{i=1}^{n}({y}^{t}{x}_{i}{)}^{2}$
.
All the above applies in fact to all real symmetric matrices. Since the adjacency matrix
$A$
of a graph
$G$
is a matrix with nonnegative entries, one can derive some important extra features of
$A$
, most notably the PerronFrobenius Theorem, that reads in the graph context as follows: if
$G$
is connected then the multiplicity of
${\lambda}_{1}$
is one, all coordinates of the first eigenvector
${x}_{1}$
can be assumed to be strictly positive, and
$\left{\lambda}_{i}\right\le {\lambda}_{1}$
for all
$i\ge 2$
. Thus, graph spectrum lies entirely in the interval
$[{\lambda}_{1},{\lambda}_{1}]$
.
For the most important special case of regular graphs PerronFrobenius implies the following corollary:
Proposition 2.10
Let
$G$
be a
$d$
regular graph on
$n$
vertices. Let
${\lambda}_{1}\ge {\lambda}_{2}\ge \dots \ge {\lambda}_{n}$
be the eigenvalues of
$G$
. Then
${\lambda}_{1}=d$
and
$d\le {\lambda}_{i}\le d$
for all
$1\le i\le n$
. Moreover, if
$G$
is connected then the first eigenvector
${x}_{1}$
is proportional to the all one vector
$(1,\dots ,1{)}^{t}\in {R}^{n}$
, and
${\lambda}_{i}<d$
for all
$i\ge 2$
.
To derive the above claim from the PerronFrobenius Theorem observe that
$e=(1,\dots ,1)$
is immediately seen to be an eigenvector of
$A\left(G\right)$
corresponding to the eigenvalue
$d$
:
$Ae=de$
. The positivity of the coordinates of
$e$
implies then that
$e$
is not orthogonal to the first eigenvector, and hence is in fact proportional to
${x}_{1}$
of
$A\left(G\right)$
. Proposition 2.10 can be also proved directly without relying on the PerronFrobenius Theorem. We remark that
${\lambda}_{n}=d$
is possible, in fact it holds if and only if the graph
$G$
is bipartite.
All this background information, presented above in a somewhat condensed form, can be found in many textbooks in Linear Algebra. Readers more inclined to consult combinatorial books can
find it for example in a recent monograph of Godsil and Royle on Algebraic Graph Theory [
46]
.
We now prove a well known theorem (see its variant, e.g., in Chapter 9, [
18]
) bridging between graph spectra and edge distribution.
Theorem 2.11
Let
$G$
be a
$d$
regular graph on
$n$
vertices. Let
$d={\lambda}_{1}\ge {\lambda}_{2}\ge \dots {\lambda}_{n}$
be the eigenvalues of
$G$
. Denote
$$\lambda =ma{x}_{2\le i\le n}\left{\lambda}_{i}\right.$$
Then for every two subsets
$U,W\subset V$
,
$$\begin{array}{c}\lefte(U,W)\frac{d\leftU\right\leftW\right}{n}\right\le \lambda \sqrt{\leftU\right\leftW\right\left(1\frac{\leftU\right}{n}\right)\left(1\frac{\leftW\right}{n}\right)}.\end{array}$$ 
(4)

Proof. Let
$B=\{{x}_{1},\dots ,{x}_{n}\}$
be an orthonormal basis of
${R}^{n}$
composed from eigenvectors of
$A$
:
$A{x}_{i}={\lambda}_{i}{x}_{i}$
,
$1\le i\le n$
. We represent
$A={\sum}_{i=1}^{n}{\lambda}_{i}{x}_{i}{x}_{i}^{t}$
. Denote
$$\begin{array}{ccc}{A}_{1}& =& {\lambda}_{1}{x}_{1}{x}_{1}^{t},\end{array}$$  
$$\begin{array}{ccc}\mathcal{\mathcal{E}}& =& {\sum}_{i=2}^{n}{\lambda}_{i}{x}_{i}{x}_{i}^{t},\end{array}$$  
then
$A={A}_{1}+\mathcal{\mathcal{E}}$
.
Let
$u=\leftU\right$
,
$w=\leftW\right$
be the cardinalities of
$U,W$
, respectively. We denote the characteristic vector of
$U$
by
${\chi}_{U}\in {R}^{n}$
, i.e.
${\chi}_{U}\left(i\right)=1$
if
$i\in U$
, and
${\chi}_{U}\left(i\right)=0$
otherwise. Similarly, let
${\chi}_{W}\in {R}^{n}$
be the characteristic vector of
$W$
. We represent
${\chi}_{U}$
,
${\chi}_{W}$
according to
$B$
:
$$\begin{array}{ccc}{\chi}_{U}& =& {\sum}_{i=1}^{n}{\alpha}_{i}{x}_{i},{\alpha}_{i}={\chi}_{U}^{t}{x}_{i},{\sum}_{i=1}^{n}{\alpha}_{i}^{2}=\parallel {\chi}_{U}{\parallel}^{2}=u,\end{array}$$  
$$\begin{array}{ccc}{\chi}_{W}& =& {\sum}_{i=1}^{n}{\beta}_{i}{x}_{i},{\beta}_{i}={\chi}_{W}^{t}{x}_{i},{\sum}_{i=1}^{n}{\beta}_{i}^{2}=\parallel {\chi}_{W}{\parallel}^{2}=w.\end{array}$$  
It follows easily from the definitions of
$A$
,
${\chi}_{U}$
and
${\chi}_{W}$
that the product
${\chi}_{U}^{t}A{\chi}_{W}$
counts exactly the number of edges of
$G$
with one endpoint in
$U$
and the other one in
$W$
, i.e.
$$e(U,W)={\chi}_{U}^{t}A{\chi}_{W}={\chi}_{U}^{t}{A}_{1}{\chi}_{W}+{\chi}_{U}^{t}\mathcal{\mathcal{E}}{\chi}_{W}.$$
Now we estimate the last two summands separately, the first of them will be the main term for
$e(U,W)$
, the second one will be the error term. Substituting the expressions for
${\chi}_{U}$
,
${\chi}_{W}$
and recalling the orthonormality of
$B$
, we get:
$$\begin{array}{c}{\chi}_{U}^{t}{A}_{1}{\chi}_{W}={\left({\sum}_{i=1}^{n}{\alpha}_{i}{x}_{i}\right)}^{t}\left({\lambda}_{1}{x}_{1}{x}_{1}^{t}\right)\left({\sum}_{j=1}^{n}{\beta}_{j}{x}_{j}\right)={\sum}_{i=1}^{n}{\sum}_{j=1}^{n}{\alpha}_{i}{\lambda}_{1}{\beta}_{j}\left({x}_{i}^{t}{x}_{1}\right)\left({x}_{1}^{t}{x}_{j}\right)={\alpha}_{1}{\beta}_{1}{\lambda}_{1}.\end{array}$$ 
(5)

Similarly,
$$\begin{array}{c}{\chi}_{U}^{t}\mathcal{\mathcal{E}}{\chi}_{W}={\left({\sum}_{i=1}^{n}{\alpha}_{i}{x}_{i}\right)}^{t}\left({\sum}_{j=2}^{n}{\lambda}_{j}{x}_{j}{x}_{j}^{t}\right)\left({\sum}_{k=1}^{n}{\beta}_{k}{x}_{k}\right)={\sum}_{i=2}^{n}{\alpha}_{i}{\beta}_{i}{\lambda}_{i}.\end{array}$$ 
(6)

Recall now that
$G$
is
$d$
regular. Then according to Proposition 2.10 ,
${\lambda}_{1}=d$
and
${x}_{1}=\frac{1}{\sqrt{n}}(1,\dots ,1{)}^{t}$
. We thus get:
${\alpha}_{1}={\chi}_{U}^{t}{x}_{1}=u/\sqrt{n}$
and
${\beta}_{1}={\chi}_{W}^{t}{x}_{1}=w/\sqrt{n}$
. Hence it follows from ( 5 ) that
${\chi}_{U}^{t}{A}_{1}{\chi}_{W}=duw/n$
.
Now we estimate the absolute value of the error term
${\chi}_{U}^{t}\mathcal{\mathcal{E}}{\chi}_{W}$
. Recalling ( 6 ), the definition of
$\lambda $
and the obtained values of
${\alpha}_{1}$
,
${\beta}_{1}$
, we derive, applying CauchySchwartz:
$$\begin{array}{ccc}{\chi}_{U}^{t}\mathcal{\mathcal{E}}{\chi}_{W}& =& \left{\sum}_{i=2}^{n}{\alpha}_{i}{\beta}_{i}{\lambda}_{i}\right\le \lambda \left{\sum}_{i=2}^{n}{\alpha}_{i}{\beta}_{i}\right\le \lambda \sqrt{{\sum}_{i=2}^{n}{\alpha}_{i}^{2}{\sum}_{i=2}^{n}{\beta}_{i}^{2}}\end{array}$$  
$$\begin{array}{ccc}& =& \lambda \sqrt{(\parallel {\chi}_{U}{\parallel}^{2}{\alpha}_{1}^{2})(\parallel {\chi}_{W}{\parallel}^{2}{\beta}_{1}^{2})}=\lambda \sqrt{\left(u\frac{{u}^{2}}{n}\right)\left(w\frac{{w}^{2}}{n}\right)}.\end{array}$$  
The theorem follows.
$\square $
The above proof can be extended to the irregular (general) case. Since the obtained quantitative bounds on edge distribution turn out to be somewhat cumbersome, we will just indicate how they can be obtained. Let
$G=(V,E)$
be a graph on
$n$
vertices with average degree
$d$
. Assume that the eigenvalues of
$G$
satisfy
$\lambda <d$
, with
$\lambda $
as defined in the theorem. Denote
$$K={\sum}_{v\in V}\left(d\right(v)d{)}^{2}.$$
The parameter
$K$
is a measure of irregularity of
$G$
. Clearly
$K=0$
if and only if
$G$
is
$d$
regular.
Let
$e=\frac{1}{\sqrt{n}}(1,\dots ,1{)}^{t}$
. We represent
$e$
in the basis
$B=\{{x}_{1},\dots ,{x}_{n}\}$
of the eigenvectors of
$A\left(G\right)$
:
$$e={\sum}_{i=1}^{n}{\gamma}_{i}{x}_{i},{\gamma}_{i}={e}^{t}{x}_{i},{\sum}_{i=1}^{n}{\gamma}_{i}^{2}=\parallel e{\parallel}^{2}=1.$$
Denote
$z=\frac{1}{\sqrt{n}}\left(d\right({v}_{1})d,\dots ,d({v}_{n})d{)}^{t}$
, then
$\parallel z{\parallel}^{2}=K/n$
. Notice that
$Ae=\frac{1}{\sqrt{n}}\left(d\right({v}_{1}),\dots ,d({v}_{n}){)}^{t}$
$=de+z$
, and therefore
$z=Aede={\sum}_{i=1}^{n}{\gamma}_{i}({\lambda}_{i}d){x}_{i}$
. This implies:
$$\begin{array}{ccc}\frac{K}{n}& =& \parallel z{\parallel}^{2}={\sum}_{i=1}^{n}{\gamma}_{i}^{2}({\lambda}_{i}d{)}^{2}\ge {\sum}_{i=2}^{n}{\gamma}_{i}^{2}({\lambda}_{i}d{)}^{2}\end{array}$$  
$$\begin{array}{ccc}& \ge & (d\lambda {)}^{2}{\sum}_{i=2}^{n}{\gamma}_{i}^{2}.\end{array}$$  
Hence
${\sum}_{i=2}^{n}{\gamma}_{i}^{2}\le \frac{K}{n(d\lambda {)}^{2}}$
. It follows that
${\gamma}_{1}^{2}=1{\sum}_{i=2}^{n}{\gamma}_{i}^{2}\ge 1\frac{K}{n(d\lambda {)}^{2}}$
and
$${\gamma}_{1}\ge {\gamma}_{1}^{2}\ge 1\frac{K}{n(d\lambda {)}^{2}}.$$
Now we estimate the distance between the vectors
$e$
and
${x}_{1}$
and show that they are close given that the parameter
$K$
is small.
$$\begin{array}{ccc}\parallel e{x}_{1}{\parallel}^{2}& =& (e{x}_{1}{)}^{t}(e{x}_{1})={e}^{t}e+{x}_{1}^{t}{x}_{1}2{e}^{t}{x}_{1}=1+12{\gamma}_{1}=22{\gamma}_{1}\end{array}$$  
$$\begin{array}{ccc}& \le & \frac{2K}{n(d\lambda {)}^{2}}.\end{array}$$  
We now return to expressions ( 5 ) and ( 6 ) from the proof of Theorem 2.11 . In order to estimate the main term
${\chi}_{U}^{t}{A}_{1}{\chi}_{W}$
, we bound the coefficients
${\alpha}_{1}$
,
${\beta}_{1}$
and
${\lambda}_{1}$
as follows:
$${\alpha}_{1}={\chi}_{U}^{t}{x}_{1}={\chi}_{U}^{t}e+{\chi}_{U}^{t}({x}_{1}e)=\frac{u}{\sqrt{n}}+{\chi}_{U}^{t}({x}_{1}e),$$
and therefore
$$\begin{array}{c}\left{\alpha}_{1}\frac{u}{\sqrt{n}}\right=\left{\chi}_{U}^{t}\right({x}_{1}e\left)\right\le \parallel {\chi}_{U}\left\right\cdot \parallel {x}_{1}e\parallel \le \frac{\sqrt{\frac{2Ku}{n}}}{d\lambda}.\end{array}$$ 
(7)

In a similar way one gets:
$$\begin{array}{c}\left{\beta}_{1}\frac{w}{\sqrt{n}}\right\le \frac{\sqrt{\frac{2Kw}{n}}}{d\lambda}.\end{array}$$ 
(8)

Finally, to estimate from above the absolute value of the difference between
${\lambda}_{1}$
and
$d$
we argue as follows:
$$\frac{K}{n}=\parallel z{\parallel}^{2}={\sum}_{i=1}^{n}{\gamma}_{i}^{2}({\lambda}_{i}d{)}^{2}\ge {\gamma}_{1}^{2}({\lambda}_{1}d{)}^{2},$$
and therefore
$$\begin{array}{c}{\lambda}_{1}d\le \frac{1}{{\gamma}_{1}}\sqrt{\frac{K}{n}}\le \frac{n(d\lambda {)}^{2}}{n(d\lambda {)}^{2}K}\sqrt{\frac{K}{n}}.\end{array}$$ 
(9)

Summarizing, we see from ( 7 ), ( 8 ) and ( 9 ) that the main term in the product
${\chi}_{U}^{t}{A}_{1}{\chi}_{W}$
is equal to
$\frac{duw}{n}$
, just as in the regular case, and the error term is governed by the parameter
$K$
.
In order to estimate the error term
${\chi}_{U}^{t}\mathcal{\mathcal{E}}{\chi}_{W}$
we use ( 6 ) to get:
$$\begin{array}{ccc}{\chi}_{U}^{t}\mathcal{\mathcal{E}}{\chi}_{W}& =& \left{\sum}_{i=2}^{n}{\alpha}_{i}{\beta}_{i}{\lambda}_{i}\right\le \lambda \left{\sum}_{i=2}^{n}{\alpha}_{i}{\beta}_{i}\right\le \lambda \sqrt{{\sum}_{i=2}^{n}{\alpha}_{i}^{2}{\sum}_{i=2}^{n}{\beta}_{i}^{2}}\end{array}$$  
$$\begin{array}{ccc}& \le & \lambda \sqrt{{\sum}_{i=1}^{n}{\alpha}_{i}^{2}{\sum}_{i=1}^{n}{\beta}_{i}^{2}}=\lambda \parallel {\chi}_{U}\parallel \parallel {\chi}_{W}\parallel =\lambda \sqrt{uw}.\square \end{array}$$  
Applying the above developed techniques we can prove now the second implication of Theorem 2.8 . Let us prove first that
$EIG$
implies
$K=o\left(n{d}^{2}\right)$
, where
$d=(1+o(1\left)\right)np$
is as before the average degree of
$G$
. Indeed, for every vector
$v\in {R}^{n}$
we have
$\parallel Av\parallel \le {\lambda}_{1}\parallel v\parallel $
, and therefore
$${\lambda}_{1}^{2}n={\lambda}_{1}^{2}{e}^{t}e\ge \left(Ae{)}^{t}\right(Ae)={\sum}_{v\in V}{d}^{2}(v).$$
Hence from
$EIG$
we get:
${\sum}_{v\in V}{d}^{2}\left(v\right)\le (1+o(1\left)\right)n{d}^{2}$
. As
${\sum}_{v}d\left(v\right)=nd$
, it follows that:
$$K={\sum}_{v\in V}\left(d\right(v)d{)}^{2}={\sum}_{v\in V}{d}^{2}(v)2d{\sum}_{v\in V}d(v)+n{d}^{2}=(1+o\left(1\right))n{d}^{2}2n{d}^{2}+n{d}^{2}=o(n{d}^{2}),$$
as promised. Substituting this into estimates ( 7 ), ( 8 ), ( 9 ) and using
$\lambda =o\left(d\right)$
of
$EIG$
we get:
$$\begin{array}{ccc}{\alpha}_{1}& =& \frac{u}{\sqrt{n}}+o\left(\sqrt{u}\right),\end{array}$$  
$$\begin{array}{ccc}{\beta}_{1}& =& \frac{w}{\sqrt{n}}+o\left(\sqrt{w}\right),\end{array}$$  
$$\begin{array}{ccc}{\lambda}_{1}& =& (1+o(1\left)\right)d,\end{array}$$  
and therefore
$${\chi}_{U}^{t}{A}_{1}{\chi}_{W}=\frac{duw}{n}+o\left(dn\right).$$
Also, according to
$EIG$
,
$\lambda =o\left(d\right)$
, which implies:
$${\chi}_{U}^{t}\mathcal{\mathcal{E}}{\chi}_{w}=o\left(d\sqrt{uw}\right)=o\left(dn\right),$$
and the claim follows.
$\square $
Theorem 2.11 is a truly remarkable result. Not only it connects between two seemingly unrelated graph characteristics – edge distribution and spectrum, it also provides a very good quantitative handle for the uniformity of edge distribution, based on easily computable, both theoretically and practically, graph parameters – graph eigenvalues. According to the bound ( 4 ), a polynomial number of parameters can control quite well the number of edges in exponentially many subsets of vertices.
The parameter
$\lambda $
in the formulation of Theorem 2.11 is usually called the second eigenvalue of the
$d$
regular graph
$G$
(the first and the trivial one being
${\lambda}_{1}=d$
). There is certain inaccuracy though in this term, as in fact
$\lambda =max\{{\lambda}_{2},{\lambda}_{n}\}$
. Later we will call, following Alon, a
$d$
regular graph
$G$
on
$n$
vertices in which all eigenvalues, but the first one, are at most
$\lambda $
in their absolute values, an
$(n,d,\lambda )$
graph.
Comparing (
4 ) with the definition of jumbled graphs by Thomason we see that an
$(n,d,\lambda )$
graph
$G$
is
$(d/n,\lambda )$
jumbled. Hence the parameter
$\lambda $
(or in other words, the so called spectral gap – the difference between
$d$
and
$\lambda $
) is responsible for pseudorandom properties of such a graph. The smaller the value of
$\lambda $
compared to
$d$
, the more close is the edge distribution of
$G$
to the ideal uniform distribution. A natural question is then: how small can be
$\lambda $
? It is easy to see that as long as
$d\le (1\epsilon )n$
,
$\lambda =\Omega \left(\sqrt{d}\right)$
. Indeed, the trace of
${A}^{2}$
satisfies:
$$nd=2\leftE\right(G\left)\right=Tr\left({A}^{2}\right)={\sum}_{i=1}^{n}{\lambda}_{i}^{2}\le {d}^{2}+(n1){\lambda}_{2}\le (1\epsilon )nd+(n1){\lambda}^{2},$$
and
$\lambda =\Omega \left(\sqrt{d}\right)$
as claimed. More accurate bounds are known for smaller values of
$d$
(see, e.g. [
69]
).
Based on these estimates we can say that an
$(n,d,\lambda )$
graph
$G$
, for which
$\lambda =\Theta \left(\sqrt{d}\right)$
, is a very good pseudorandom graph. We will see several examples of such graphs in the next section.
2.5 Strongly regular graphs
A strongly regular graph
$srg(n,d,\eta ,\mu )$
is a
$d$
regular graph on
$n$
vertices in which every pair of adjacent vertices has exactly
$\eta $
common neighbors and every pair of nonadjacent vertices has exactly
$\mu $
common neighbors. (We changed the very standard notation in the above definition so as to avoid interference with other notational conventions throughout this paper and to make it more coherent, usually the parameters are denoted
$(v,k,\lambda ,\mu )$
). Two simple examples of strongly regular graph are the pentagon
${C}_{5}$
that has parameters
$(5,2,0,1)$
, and the Petersen graph whose parameters are
$(10,3,0,1)$
. Strongly regular graphs were introduced by Bose in 1963 [
21]
who also pointed out their tight connections with finite geometries. As follows from the definition, strongly regular graphs are highly regular structures, and one can safely predict that algebraic methods are extremely useful in their study. We do not intend to provide any systematic coverage of this fascinating concept here, addressing the reader to the vast literature on the subject instead (see, e.g., [
24]
). Our aim here is to calculate the eigenvalues of strongly regular graphs and then to connect them with pseudorandomness, relying on results from the previous subsection.
Proposition 2.12
Let
$G$
be a connected strongly regular graph with parameters
$(n,d,\eta ,\mu )$
.
Then the eigenvalues of
$G$
are:
${\lambda}_{1}=d$
with multiplicity
${s}_{1}=1$
,
$${\lambda}_{2}=\frac{1}{2}\left(\eta \mu +\sqrt{(\eta \mu {)}^{2}+4(d\mu )}\right)$$
and
$${\lambda}_{3}=\frac{1}{2}\left(\eta \mu \sqrt{(\eta \mu {)}^{2}+4(d\mu )}\right),$$
with multiplicities
$${s}_{2}=\frac{1}{2}\left(n1+\frac{(n1)(\mu \eta )2d}{\sqrt{(\mu \eta {)}^{2}+4(d\mu )}}\right)$$
and
$${s}_{3}=\frac{1}{2}\left(n1\frac{(n1)(\mu \eta )2d}{\sqrt{(\mu \eta {)}^{2}+4(d\mu )}}\right),$$
respectively.
Proof. Let
$A$
be the adjacency matrix of
$A$
. By the definition of
$A$
and the fact that
$A$
is symmetric with zeroes on the main diagonal, the
$(i,j)$
entry of the square
${A}^{2}$
counts the numberof common neighbors of
${v}_{i}$
and
${v}_{j}$
in
$G$
if
$i\ne j$
, and is equal to the degree
$d\left({v}_{i}\right)$
in case
$i=j$
. The statement that
$G$
is
$srg(n,d,\eta ,\mu )$
is equivalent then to:
$$\begin{array}{c}AJ=dJ,{A}^{2}=(d\mu )I+\mu J+(\eta \mu )A,\end{array}$$ 
(10)

where
$J$
is the
$n$
by
$n$
allone matrix and
$I$
is the
$n$
by
$n$
identity matrix.
Since
$G$
is
$d$
regular and connected, we obtain from the PerronFrobenius Theorem that
${\lambda}_{1}=d$
is an eigenvalue of
$G$
with multiplicity 1 and with
$e=(1,\dots ,1{)}^{t}$
as the corresponding eigenvector.
Let
$\lambda \ne d$
be another eigenvalue of
$G$
, and let
$x\in {R}^{n}$
be a corresponding eigenvector. Then
$x$
is orthogonal to
$e$
, and therefore
$Jx=0$
. Applying both sides of the second identity in ( 10 ) to
$x$
we get the equation:
${\lambda}^{2}x=(d\mu )x+(\eta \mu )\lambda x$
, which results in the following quadratic equation for
$\lambda $
:
$${\lambda}^{2}+(\mu \eta )\lambda +(\mu d)=0.$$
This equation has two solutions
${\lambda}_{2}$
and
${\lambda}_{3}$
as defined in the proposition formulation. If we denote by
${s}_{2}$
and
${s}_{3}$
the respective multiplicities of
${\lambda}_{2}$
and
${\lambda}_{3}$
as eigenvalues of
$A$
, we get:
$$1+{s}_{2}+{s}_{3}=n,Tr\left(A\right)=d+{s}_{2}{\lambda}_{2}+{s}_{3}{\lambda}_{3}=0.$$
Solving the above system of linear equations for
${s}_{2}$
and
${s}_{3}$
we obtain the assertion of the proposition.
$\square $
Using the bound ( 4 ) we can derive from the above proposition that if the parameters of a strongly regular graph
$G$
satisfy
$\eta \approx \mu $
then
$G$
has a large eigenvalue gap and is therefore a good pseudorandom graph. We will exhibit several examples of such graphs in the next section.
3 Examples
Here we present some examples of pseudorandom graphs. Many of them are well known and already appeared, e.g., in [
79]
and [
80]
, but there also some which have been discovered only recently.
Since in the rest of the paper we will mostly discuss properties of
$(n,d,\lambda )$
graphs, in our examples we emphasize the spectral properties of the constructed graphs. We will also use most of these constructions later to illustrate particular points and to test the strength of the theorems.
Random graphs

1.
Let
$G=G(n,p)$
be a random graph with edge probability
$p$
. If
$p$
satisfies
$pn/logn\to \infty $
and
$(1p)nlogn\to \infty $
, then almost surely all the degrees of
$G$
are equal to
$(1+o(1\left)\right)np$
.
Moreover it was proved by Füredi and Komlós [
44]
that the largest eigenvalue of
$G$
is a.s.
$(1+o(1\left)\right)np$
and that
$\lambda \left(G\right)\le (2+o(1\left)\right)\sqrt{p(1p)n}$
. They stated this result only for constant
$p$
but their proof shows that
$\lambda \left(G\right)\le O\left(\sqrt{np}\right)$
also when
$p\ge polylogn/n$
.

2.
For a positive integervalued function
$d=d\left(n\right)$
we define the model
${G}_{n,d}$
of random regular graphs consisting of all regular graphs on
$n$
vertices of degree
$d$
with the uniform probability distribution. This definition of a random regular graph is conceptually simple, but it is not easy to use. Fortunately, for small
$d$
there is an efficient way to generate
${G}_{n,d}$
which is useful for theoretical studies. This is the so called configuration model. For more details about this model, and random regular graphs in general we refer the interested reader to two excellent monographs [20] and [49] , or to a survey [83] . As it turns out, sparse random regular graphs have quite different properties from those of the binomial random graph
$G(n,p),p=d/n$
. For example, they are almost surely connected. The spectrum of
${G}_{n,d}$
for a fixed
$d$
was studied in [38] by Friedman, Kahn and Szemerédi. Friedman [39] proved that for constant
$d$
the second largest eigenvalue of a random
$d$
regular graph is
$\lambda =(1+o(1\left)\right)2\sqrt{d1}$
. The approach of Kahn and Szemerédi gives only
$O\left(\sqrt{d}\right)$
bound on
$\lambda $
but continues to work also when
$d$
is small power of
$n$
. The case
$d\gg {n}^{1/2}$
was recently studied by Krivelevich, Sudakov, Vu and Wormald [61] .
They proved that in this case for any two vertices
$u,v\in {G}_{n,d}$
almost surely
$$\leftcodeg\right(u,v){d}^{2}/n<C{d}^{3}/{n}^{2}+6d\sqrt{logn}/\sqrt{n},$$
where
$C$
is some constant and
$codeg(u,v)$
is the number of common neighbors of
$u,v$
.
Moreover if
$d\ge n/logn$
, then
$C$
can be defined to be zero. Using this it is easy to show that for
$d\gg {n}^{1/2}$
, the second largest eigenvalue of a random
$d$
regular graph is
$o\left(d\right)$
. The true bound for the second largest eigenvalue of
${G}_{n,d}$
should be probably
$(1+o(1\left)\right)2\sqrt{d1}$
for all values of
$d$
, but we are still far from proving it.
Strongly regular graphs

3.
Let
$q={p}^{\alpha}$
be a prime power which is congruent to
$1$
modulo
$4$
so that
$1$
is a square in the finite field
$GF\left(q\right)$
. Let
${P}_{q}$
be the graph whose vertices are all elements of
$GF\left(q\right)$
and two vertices are adjacent if and only if their difference is a quadratic residue in
$GF\left(q\right)$
. This graph is usually called the Paley graph. It is easy to see that
${P}_{q}$
is
$(q1)/2$
regular. In addition one can easily compute the number of common neighbors of two vertices in
${P}_{q}$
. Let
$\chi $
be the quadratic residue character on
$GF\left(q\right)$
, i.e.,
$\chi \left(0\right)=0$
,
$\chi \left(x\right)=1$
if
$x\ne 0$
and is a square in
$GF\left(q\right)$
and
$\chi \left(x\right)=1$
otherwise. By definition,
${\sum}_{x}\chi \left(x\right)=0$
and the number of common neighbors of two vertices
$a$
and
$b$
equals
$${\sum}_{x\ne a,b}\left(\frac{1+\chi (ax)}{2}\right)\left(\frac{1+\chi (bx)}{2}\right)=\frac{q2}{4}\frac{\chi (ab)}{2}+\frac{1}{4}{\sum}_{x\ne a,b}\chi (ax)\chi (bx).$$
Using that for
$x\ne b$
,
$\chi (bx)=\chi \left((bx{)}^{1}\right)$
, the last term can be rewritten as
$${\sum}_{x\ne a,b}\chi (ax)\chi \left((bx{)}^{1}\right)={\sum}_{x\ne a,b}\chi \left(\frac{ax}{bx}\right)={\sum}_{x\ne a,b}\chi \left(1+\frac{ab}{bx}\right)={\sum}_{x\ne 0,1}\chi \left(x\right)=1.$$
Thus the number of common neighbors of
$a$
and
$b$
is
$(q3)/4\chi (ab)/2$
. This equals
$(q5)/4$
if
$a$
and
$b$
are adjacent and
$(q1)/4$
otherwise. This implies that the Paley graph is a strongly regular graph with parameters
$\left(q,(q1)/2,(q5)/4,(q1)/4\right)$
and therefore its second largest eigenvalue equals
$(\sqrt{q}+1)/2$
.

4.
For any odd integer
$k$
let
${H}_{k}$
denote the graph whose
${n}_{k}={2}^{k1}1$
vertices are all binary vectors of length
$k$
with an odd number of ones except the all one vector, in which two distinct vertices are adjacent iff the inner product of the corresponding vectors is
$1$
modulo
$2$
.
Using elementary linear algebra it is easy to check that this graph is
$({2}^{k2}2)$
regular. Also every two nonadjacent vertices vertices in it have
${2}^{k3}1$
common neighbors and every two adjacent vertices vertices have
${2}^{k3}3$
common neighbors. Thus
${H}_{k}$
is a strongly regular graph with parameters
$\left({2}^{k1}1,{2}^{k2}2,{2}^{k3}3,{2}^{k3}1\right)$
and with the second largest eigenvalue
$\lambda \left({H}_{k}\right)=1+{2}^{\frac{k3}{2}}$
.

5.
Let
$q$
be a prime power an let
$V\left(G\right)$
be the elements of the two dimensional vector space over
$GF\left(q\right)$
, so
$G$
has
${q}^{2}$
vertices. Partition the
$q+1$
lines through the origin of the space into two sets
$P$
and
$N$
, where
$\leftP\right=k$
. Two vertices
$x$
and
$y$
of the graph
$G$
are adjacent if
$xy$
is parallel to a line in
$P$
. This example is due to Delsarte and Goethals and to Turyn (see [72] ). It is easy to check that
$G$
is strongly regular with parameters
$\left(k(q1),(k1)(k2)+q2,k(k1)\right)$
. Therefore its eigenvalues, besides the trivial one are
$k$
and
$qk$
.
Thus if
$k$
is sufficiently large we obtain that
$G$
is
$d=k(q1)$
regular graph whose second largest eigenvalue is much smaller than
$d$
.
Graphs arising from finite geometries

6.
For any integer
$t\ge 2$
and for any power
$q={p}^{\alpha}$
of prime
$p$
let
$PG(q,t)$
denote the projective geometry of dimension
$t$
over the finite field
$GF\left(q\right)$
. The interesting case for our purposes here is that of large
$q$
and fixed
$t$
. The vertices of
$PG(q,t)$
correspond to the equivalence classes of the set of all nonzero vectors
$\mathbf{x}=({x}_{0},\dots ,{x}_{t})$
of length
$t+1$
over
$GF\left(q\right)$
, where two vectors are equivalent if one is a multiple of the other by an element of the field. Let
$G$
denote the graph whose vertices are the points of
$PG(q,t)$
and two (not necessarily distinct) vertices
$\mathbf{x}$
and
$\mathbf{y}$
are adjacent if and only if
${x}_{0}{y}_{0}+\dots +{x}_{t}{y}_{t}=0$
. This construction is well known. In particular, in case
$t=2$
this graph is often called the ErdősRényi graph and it contains no cycles of length
$4$
. It is easy to see that the number of vertices of
$G$
is
${n}_{q,t}=\left({q}^{t+1}1\right)/\left(q1\right)=\left(1+o\left(1\right)\right){q}^{t}$
and that it is
${d}_{q,t}$
regular for
${d}_{q,t}=\left({q}^{t}1\right)/\left(q1\right)=\left(1+o\left(1\right)\right){q}^{t1}$
, where
$o\left(1\right)$
tends to zero as
$q$
tends to infinity. It is easy to see that the number of vertices of
$G$
with loops is bounded by
$2\left({q}^{t}1\right)/\left(q1\right)=\left(2+o\left(1\right)\right){q}^{t1}$
, since for every possible value of
${x}_{0},\dots ,{x}_{t1}$
we have at most two possible choices of
${x}_{t}$
. Actually using more complicated computation, which we omit, one can determine the exact number of vertices with loops. The eigenvalues of
$G$
are easy to compute (see [11] ). Indeed, let
$A$
be the adjacency matrix of
$G$
. Then, by the properties of
$PG(q,t)$
,
${A}^{2}=A{A}^{T}=\mu J+({d}_{q,t}\mu )I$
, where
$\mu =\left({q}^{t1}1\right)/\left(q1\right)$
,
$J$
is the all one matrix and
$I$
is the identity matrix, both of size
${n}_{q,t}\times {n}_{q,t}$
. Therefore the largest eigenvalue of
$A$
is
${d}_{q,t}$
and the absolute value of all other eigenvalues is
$\sqrt{{d}_{q,t}\mu}={q}^{(t1)/2}$
.

7.
The generalized polygons are incidence structures consisting of points
$\mathcal{P}$
and lines
$\mathcal{\mathcal{L}}$
. For our purposes we restrict our attention to those in which every point is incident to
$q+1$
lines and every line is incident to
$q+1$
points. A generalized
$m$
gon defines a bipartite graph
$G$
with bipartition
$(\mathcal{P},\mathcal{\mathcal{L}})$
that satisfies the following conditions. The diameter of
$G$
is
$m$
and for every vertex
$v\in G$
there is a vertex
$u\in G$
such that the shortest path from
$u$
to
$v$
has length
$m$
. Also for every
$r<m$
and for every two vertices
$u,v$
at distance
$r$
there exists a unique path of length
$r$
connecting them. This immediately implies that every cycle in
$G$
has length at least
$2m$
. For
$q\ge 2$
, it was proved by Feit and Higman [36] that
$(q+1)$
regular generalized
$m$
gons exist only for
$m=3,4,6$
. A polarity of
$G$
is a bijection
$\pi :\mathcal{P}\cup \mathcal{\mathcal{L}}\to \mathcal{P}\cup \mathcal{\mathcal{L}}$
such that
$\pi (\mathcal{P})=\mathcal{\mathcal{L}}$
,
$\pi (\mathcal{\mathcal{L}})=\mathcal{P}$
and
${\pi}^{2}$
is the identity map. Also for every
$p\in \mathcal{P},l\in \mathcal{\mathcal{L}}$
,
$\pi \left(p\right)$
is adjacent to
$\pi \left(l\right)$
if and only if
$p$
and
$l$
are adjacent. Given
$\pi $
we define a polarity graph
${G}^{\pi}$
to be the graph whose vertices are point in
$\mathcal{P}$
and two (not necessarily distinct) points
${p}_{1},{p}_{2}$
are adjacent iff
${p}_{1}$
was adjacent to
$\pi \left({p}_{2}\right)$
in
$G$
. Some properties of
${G}^{\pi}$
can be easily deduced from the corresponding properties of
$G$
. In particular,
${G}^{\pi}$
is
$(q+1)$
regular and also contains no even cycles of length less than
$2m$
.
For every
$q$
which is an odd power of
$2$
, the incidence graph of the generalized
$4$
gon has a polarity. The corresponding polarity graph is a
$(q+1)$
regular graph with
${q}^{3}+{q}^{2}+q+1$
vertices. See [
23]
, [
62]
for more details. This graph contains no cycle of length
$6$
and it is not difficult to compute its eigenvalues (they can be derived, for example, from the eigenvalues of the corresponding bipartite incidence graph, given in [
78]
). Indeed, all the eigenvalues, besides the trivial one (which is
$q+1$
) are either
$0$
or
$\sqrt{2q}$
or
$\sqrt{2q}$
. Similarly, for every
$q$
which is an odd power of
$3$
, the incidence graph of the generalized
$6$
gon has a polarity. The corresponding polarity graph is a
$(q+1)$
regular graph with
${q}^{5}+{q}^{4}+\cdots +q+1$
vertices ( see again [
23]
, [
62]
).
This graph contains no cycle of length
$10$
and its eigenvalues can be derived using the same technique as in case of the
$4$
gon. All these eigenvalues, besides the trivial one are either
$\sqrt{3q}$
or
$\sqrt{3q}$
or
$\sqrt{q}$
or
$\sqrt{q}$
.
Cayley graphs

8.
Let
$G$
be a finite group and let
$S$
be a set of nonidentity elements of
$G$
such that
$S={S}^{1}$
, i.e., for every
$s\in S$
,
${s}^{1}$
also belongs to
$S$
. The Cayley graph
$\Gamma (G,S)$
of this group with respect to the generating set
$S$
is the graph whose set of vertices is
$G$
and where two vertices
$g$
and
${g}^{\prime}$
are adjacent if and only if
${g}^{\prime}{g}^{1}\in S$
. Clearly,
$\Gamma (G,S)$
is
$\leftS\right$
regular and it is connected iff
$S$
is a set of generators of the group. If
$G$
is abelian then the eigenvalues of the Cayley graph can be computed in terms of the characters of
$G$
. Indeed, let
$\chi :G\to C$
be a character of
$G$
and let
$A$
be the adjacency matrix of
$\Gamma (G,S)$
whose rows and columns are indexed by the elements of
$G$
. Consider the vector
$\mathbf{v}$
defined by
$\mathbf{v}\left(g\right)=\chi \left(g\right)$
. Then it is easy to check that
$A\mathbf{v}=\alpha \mathbf{v}$
with
$\alpha ={\sum}_{s\in S}\chi \left(s\right)$
. In addition all eigenvalues can be obtained in this way, since every abelian group has exactly
$\leftG\right$
different character which are orthogonal to each other. Using this fact, one can often give estimates on the eigenvalues of
$\Gamma (G,S)$
for abelian groups.
One example of a Cayley graph that has already been described earlier is
${P}_{q}$
. In that case the group is the additive group of the finite field
$GF\left(q\right)$
and
$S$
is the set of all quadratic residues modulo
$q$
. Next we present a slightly more general construction. Let
$q=2kr+1$
be a prime power and let
$\Gamma $
be a Cayley graph whose group is the additive group of
$GF\left(q\right)$
and whose generating set is
$S=\left\{x={y}^{k}\text{for some}y\in GF(q)\right\}$
. By definition,
$\Gamma $
is
$(q1)/k$
regular. On the other hand, this graph is not strongly regular unless
$k=2$
, when it is the Paley graph. Let
$\chi $
be a nontrivial additive character of
$GF\left(q\right)$
and consider the Gauss sum
${\sum}_{y\in GF\left(q\right)}\chi \left({y}^{k}\right)$
. Using the classical bound
$\left{\sum}_{y\in GF\left(q\right)}\chi \right({y}^{k}\left)\right\le (k1){q}^{1/2}$
(see e.g. [
63]
) and the above connection between characters and eigenvalues we can conclude that the second largest eigenvalue of our graph
$\Gamma $
is bounded by
$O\left({q}^{1/2}\right)$
.

9.
Next we present a surprising construction obtained by Alon [3] of a very dense pseudorandom graph that on the other hand is trianglefree. For a positive integer
$k$
, consider the finite field
$GF\left({2}^{k}\right)$
, whose elements are represented by binary vectors of length
$k$
. If
$a,b,c$
are three such vectors, denote by
$(a,b,c)$
the binary vector of length
$3k$
whose coordinates are those of
$a$
, followed by coordinates of
$b$
and then
$c$
. Suppose that
$k$
is not divisible by
$3$
. Let
${W}_{0}$
be the set of all nonzero elements
$\alpha \in GF\left({2}^{k}\right)$
so that the leftmost bit in the binary representation of
${\alpha}^{7}$
is
$0$
, and let
${W}_{1}$
be the set of all nonzero elements
$\alpha \in GF\left({2}^{k}\right)$
for which the leftmost bit of
${\alpha}^{7}$
is
$1$
. Since
$3$
does not divide
$k$
,
$7$
does not divide
${2}^{k}1$
and hence
$\left{W}_{0}\right={2}^{k1}1$
and
$\left{W}_{1}\right={2}^{k1}$
, as when
$\alpha $
ranges over all nonzero elements of the field so does
${\alpha}^{7}$
. Let
${G}_{n}$
be the graph whose vertices are all
$n={2}^{3k}$
binary vectors of length
$3k$
, where two vectors
$\mathbf{v}$
and
${\mathbf{v}}^{\prime}$
are adjacent if and only if there exist
${w}_{0}\in {W}_{0}$
and
${w}_{1}\in {W}_{1}$
so that
$\mathbf{v}{\mathbf{v}}^{\prime}=({w}_{0},{w}_{0}^{3},{w}_{0}^{5})+({w}_{1},{w}_{1}^{3},{w}_{1}^{5})$
, where here powers are computed in the field
$GF\left({2}^{k}\right)$
and the addition is addition modulo
$2$
. Note that
${G}_{n}$
is the Cayley graph of the additive group
${\mathbf{Z}}_{2}^{3k}$
with respect to the generating set
$S={U}_{0}+{U}_{1}$
, where
${U}_{0}=\left\{({w}_{0},{w}_{0}^{3},{w}_{0}^{5}){w}_{0}\in {W}_{0}\right\}$
and
${U}_{1}$
is defined similarly. A well known fact from Coding Theory (see e.g., [66] ), which can be proved using the Vandermonde determinant, is that every set of six distinct vectors in
${U}_{0}\cup {U}_{1}$
is linearly independent over
$GF\left(2\right)$
. In particular all the vectors in
${U}_{0}+{U}_{1}$
are distinct,
$S=\left{U}_{0}\right\left{U}_{1}\right$
and hence
${G}_{n}$
is
$\leftS\right={2}^{k1}({2}^{k1}1)$
regular. The statement that
${G}_{n}$
is triangle free is clearly equivalent to the fact that the sum modulo
$2$
of any set of
$3$
nonzero elements of
$S$
is not a zerovector. Let
${u}_{0}+{u}_{1},{u}_{0}^{\prime}+{u}_{1}^{\prime}$
and
${u}_{0}^{\prime \prime}+{u}_{1}^{\prime \prime}$
be three distinct element of
$S$
, where
${u}_{0},{u}_{0}^{\prime},{u}_{0}^{\prime \prime}\in {U}_{0}$
and
${u}_{1},{u}_{1}^{\prime},{u}_{1}^{\prime \prime}\in {U}_{1}$
. By the above discussion, if the sum of these six vectors is zero, then every vector must appear an even number of times in the sequence
$({u}_{0},{u}_{0}^{\prime},{u}_{0}^{\prime \prime},{u}_{1},{u}_{1}^{\prime},{u}_{1}^{\prime \prime})$
. However, since
${U}_{0}$
and
${U}_{1}$
are disjoint, this is clearly impossible. Finally, as we already mentioned, the eigenvalues of
${G}_{n}$
can be computed in terms of characters of
${\mathbf{Z}}_{2}^{3k}$
. Using this fact together with the CarlitzUchiyama bound on the characters of
${\mathbf{Z}}_{2}^{3k}$
it was proved in [3] that the second eigenvalue of
${G}_{n}$
is bounded by
$\lambda \le 9\cdot {2}^{k}+3\cdot {2}^{k/2}+1/4$
.

10.
The construction above can be extended in the obvious way as mentioned in [10] . Let
$h\ge 1$
and suppose that
$k$
is an integer such that
${2}^{k}1$
is not divisible by
$4h+3$
. Let
${W}_{0}$
be the set of all nonzero elements
$\alpha \in GF\left({2}^{k}\right)$
so that the leftmost bit in the binary representation of
${\alpha}^{4h+3}$
is
$0$
, and let
${W}_{1}$
be the set of all nonzero elements
$\alpha \in GF\left({2}^{k}\right)$
for which the leftmost bit of
${\alpha}^{4h+3}$
is
$1$
. Since
$4h+3$
does not divide
${2}^{k}1$
we have that
$\left{W}_{0}\right={2}^{k1}1$
and
$\left{W}_{1}\right={2}^{k1}$
, as when
$\alpha $
ranges over all nonzero elements of the field so does
${\alpha}^{4h+3}$
. Define
$G$
to be the Cayley graph of the additive group
${\mathbf{Z}}_{2}^{(2h+1)k}$
with respect to the generating set
$S={U}_{0}+{U}_{1}$
, where
${U}_{0}=\left\{({w}_{0},{w}_{0}^{3},\dots ,{w}_{0}^{4h+1}){w}_{0}\in {W}_{0}\right\}$
and
${U}_{1}$
is defined similarly.
Clearly,
$G$
is a
${2}^{k1}({2}^{k1}1)$
regular graph on
${2}^{(2h+1)k}$
vertices. Using methods from [
3]
, one can show that
$G$
contains no odd cycle of length
$\le 2h+1$
and that the second eigenvalue of
$G$
is bounded by
$O\left({2}^{k}\right)$
.

11.
Now we describe the celebrated expander graphs constructed by Lubotzky, Phillips and Sarnak [65] and independently by Margulis [68] . Let
$p$
and
$q$
be unequal primes, both congruent to
$1$
modulo
$4$
and such that
$p$
is a quadratic residue modulo
$q$
. As usual denote by
$PSL(2,q)$
the factor group of the group of two by two matrices over
$GF\left(q\right)$
with determinant
$1$
modulo its normal subgroup consisting of the two scalar matrices
$\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)$
and
$\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)$
.
The graphs we describe are Cayley graphs of
$PSL(2,q)$
. A well known theorem of Jacobi asserts that the number of ways to represent a positive integer
$n$
as a sum of
$4$
squares is
$8{\sum}_{4\u0338d,dn}d$
. This easily implies that there are precisely
$p+1$
vectors
$\mathbf{a}=({a}_{0},{a}_{1},{a}_{2},{a}_{3})$
, where
${a}_{0}$
is an odd positive integer,
${a}_{1},{a}_{2},{a}_{3}$
are even integers and
${a}_{0}^{2}+{a}_{1}^{2}+{a}_{2}^{2}+{a}_{3}^{2}=p$
. From each such vector construct the matrix
${M}_{a}$
in
$PSL(2,q)$
where
${M}_{a}=\frac{1}{\sqrt{p}}\left(\begin{array}{cc}{a}_{0}+i{a}_{1}& {a}_{2}+i{a}_{3}\\ {a}_{2}+i{a}_{3}& {a}_{0}i{a}_{1}\end{array}\right)$
and
$i$
is an integer satisfying
${i}^{2}=1(\text{mod}q)$
. Note that, indeed, the determinant of
${M}_{a}$
is
$1$
and that the square root of
$p$
modulo
$q$
does exist. Let
${G}^{p,q}$
denote the Cayley graph of
$PSL(2,q)$
with respect to these
$p+1$
matrices. In [
65]
it was proved that if
$q>2\sqrt{p}$
then
${G}^{p,q}$
is a connected
$(p+1)$
regular graph on
$n=q({q}^{2}1)/2$
vertices. Its girth is at least
$2{log}_{p}q$
and all the eigenvalues of its adjacency matrix, besides the trivial one
${\lambda}_{1}=p+1$
, are at most
$2\sqrt{p}$
in absolute value. The bound on the eigenvalues was obtained by applying deep results of Eichler and Igusa concerning the Ramanujan conjecture. The graphs
${G}^{p,q}$
have very good expansion properties and have numerous applications in Combinatorics and Theoretical Computer Science.

12.
The projective norm graphs
$N{G}_{p,t}$
have been constructed in [17] , modifying an earlier construction given in [52] . These graphs are not Cayley graphs, but as one will immediately see, their construction has a similar flavor. The construction is the following. Let
$t>2$
be an integer, let
$p$
be a prime, let
$GF(p{)}^{*}$
be the multiplicative group of the field with
$p$
elements and let
$GF\left({p}^{t1}\right)$
be the field with
${p}^{t1}$
elements. The set of vertices of the graph
$N{G}_{p,t}$
is the set
$V=GF\left({p}^{t1}\right)\times GF(p{)}^{*}$
. Two distinct vertices
$(X,a)$
and
$(Y,b)\in V$
are adjacent if and only if
$N(X+Y)=ab$
, where the norm
$N$
is understood over
$GF\left(p\right)$
, that is,
$N\left(X\right)={X}^{1+p+\cdots +{p}^{t2}}.$
Note that
$\leftV\right={p}^{t}{p}^{t1}$
. If
$(X,a)$
and
$(Y,b)$
are adjacent, then
$(X,a)$
and
$Y\ne X$
determine
$b$
. Thus
$N{G}_{p,t}$
is a regular graph of degree
${p}^{t1}1$
. In addition, it was proved in [17] , that
$N{G}_{p,t}$
contains no complete bipartite graphs
${K}_{t,(t1)!+1}$
.
These graphs can be also defined in the same manner starting with a prime power instead of the prime
$p$
. It is also not difficult to compute the eigenvalues of this graph. Indeed, put
$q={p}^{t1}$
and let
$A$
be the adjacency matrix of
$N{G}_{p,t}$
. The rows and columns of this matrix are indexed by the ordered pairs of the set
$GF\left(q\right)\times GF(p{)}^{*}$
. Let
$\psi $
be a character of the additive group of
$GF\left(q\right)$
, and let
$\chi $
be a character of the multiplicative group of
$GF\left(p\right)$
. Consider the vector
$\mathbf{v}:GF\left(q\right)\times GF(p{)}^{*}\mapsto C$
defined by
$\mathbf{v}(X,a)=\psi \left(X\right)\chi \left(a\right)$
. Now one can check (see [
14]
, [
76]
for more details) that the vector
$\mathbf{v}$
is an eigenvector of
${A}^{2}$
with eigenvalue
$\left{\sum}_{Z\in GF\left(q\right),Z\ne 0}\psi \right(Z\left)\chi \right(N\left(Z\right)){}^{2}$
and that all eigenvalues of
${A}^{2}$
have this form. Set
${\chi}^{\prime}\left(Z\right)=\chi \left(N\right(Z\left)\right)$
for all nonzero
$Z$
in
$GF\left(q\right)$
. Note that as the norm is multiplicative,
${\chi}^{\prime}$
is a multiplicative character of the large field. Hence the above expression is a square of the absolute value of the Gauss sum and it is well known (see e.g. [
31]
, [
20]
) that the value of each such square, besides the trivial one (that is, when either
$\psi $
or
${\chi}^{\prime}$
are trivial), is
$q$
. This implies that the second largest eigenvalue of
$N{G}_{p,t}$
is
$\sqrt{q}={p}^{(t1)/2}$
.
4 Properties of pseudorandom graphs
We now examine closely properties of pseudorandom graphs, with a special emphasis on
$(n,d,\lambda )$
graphs. The majority of them are obtained using the estimate ( 4 ) of Theorem 2.11 , showing again the extreme importance and applicability of the latter result. It is instructive to compare the properties of pseudorandom graphs, considered below, with the analogous properties of random graphs, usually shown to hold by completely different methods. The set of properties we chose to treat here is not meant to be comprehensive or systematic, but quite a few rather diverse graph parameters will be covered.
4.1 Connectivity and perfect matchings
The vertexconnectivity of a graph
$G$
is the minimum number of vertices that we need to delete to make
$G$
disconnected. We denote this parameter by
$\kappa \left(G\right)$
. For random graphs it is well known (see, e.g., [
20]
) that the vertexconnectivity is almost surely the same as the minimum degree.
Recently it was also proved (see [
61]
and [
30]
) that random
$d$
regular graphs are
$d$
vertexconnected.
For
$(n,d,\lambda )$
graphs it is easy to show the following.
Theorem 4.1
Let
$G$
be an
$(n,d,\lambda )$
graph with
$d\le n/2$
. Then the vertexconnectivity of
$G$
satisfies:
$$\kappa \left(G\right)\ge d36{\lambda}^{2}/d.$$
Proof. We can assume that
$\lambda \le d/6$
, since otherwise there is nothing to prove. Suppose that there is a subset
$S\subset V$
of size less than
$d36{\lambda}^{2}/d$
such that the induced graph
$G[VS]$
is disconnected. Denote by
$U$
the set of vertices of the smallest connected component of
$G[VS]$
and set
$W=V(S\cup U)$
. Then
$\leftW\right\ge (nd)/2\ge n/4$
and there is no edge between
$U$
and
$W$
. Also
$\leftU\right+\leftS\right>d$
, since all the neighbors of a vertex from
$U$
are contained in
$S\cup U$
.
Therefore
$\leftU\right\ge 36{\lambda}^{2}/d$
. Since there are no edges between
$U$
and
$W$
, by Theorem 2.11 , we have that
$d\leftU\right\leftW\right/n<\lambda \sqrt{\leftU\right\leftW\right}$
. This implies that
$$\leftU\right<\frac{{\lambda}^{2}{n}^{2}}{{d}^{2}\leftW\right}=\frac{\lambda}{d}\frac{n}{\leftW\right}\frac{\lambda n}{d}\le \frac{1}{6}\cdot 4\cdot \frac{\lambda n}{d}<\frac{\lambda n}{d}.$$
Next note that, by Theorem 2.11 , the number of edges spanned by
$U$
is at most
$$e\left(U\right)\le \frac{dU{}^{2}}{2n}+\frac{\lambda \leftU\right}{2}<\frac{\lambda n}{d}\frac{d\leftU\right}{2n}+\frac{\lambda \leftU\right}{2}=\frac{\lambda \leftU\right}{2}+\frac{\lambda \leftU\right}{2}=\lambda \leftU\right.$$
As the degree of every vertex in
$U$
is
$d$
, it follows that
$$e(U,S)\ge d\leftU\right2e\left(U\right)>(d2\lambda )\leftU\right\ge 2d\leftU\right/3.$$
On the other hand using again Theorem 2.11 together with the facts that
$\leftU\right\ge 36{\lambda}^{2}/d$
,
$\leftS\right<d$
and
$d\le n/2$
we conclude that
$$\begin{array}{ccc}e(U,S)& \le & \frac{d\leftU\right\leftS\right}{n}+\lambda \sqrt{\leftU\right\leftS\right}<\frac{d}{n}d\leftU\right+\lambda \sqrt{d\leftU\right}\le \frac{d\leftU\right}{2}+\frac{\lambda \sqrt{d}\leftU\right}{\sqrt{\leftU\right}}\end{array}$$  
$$\begin{array}{ccc}& \le & \frac{d\leftU\right}{2}+\frac{\lambda \sqrt{d}\leftU\right}{6\lambda /\sqrt{d}}=\frac{d\leftU\right}{2}+\frac{d\leftU\right}{6}=\frac{2d\leftU\right}{3}.\end{array}$$  
This contradiction completes the proof.
$\square $
The constants in this theorem can be easily improved and we make no attempt to optimize them.
Note that, in particular, for an
$(n,d,\lambda )$
graph
$G$
with
$\lambda =O\left(\sqrt{d}\right)$
we have that
$\kappa \left(G\right)=d\Theta \left(1\right)$
.
Next we present an example which shows that the assertion of Theorem
4.1 is tight up to a constant factor. Let
$G$
be any
$(n,d,\lambda )$
graph with
$\lambda =\Theta \left(\sqrt{d}\right)$
. We already constructed several such graphs in the previous section. For an integer
$k$
, consider a new graph
${G}_{k}$
, which is obtained by replacing each vertex of
$G$
by the complete graph of order
$k$
and by connecting two vertices of
${G}_{k}$
by an edge if and only if the corresponding vertices of
$G$
are connected by an edge. Then it follows immediately from the definition that
${G}_{k}$
has
${n}^{\prime}=nk$
vertices and is
${d}^{\prime}$
regular graph with
${d}^{\prime}=dk+k1$
. Let
${\lambda}^{\prime}$
be the second eigenvalue of
${G}_{k}$
. To estimate
${\lambda}^{\prime}$
note that the adjacency matrix of
${G}_{k}$
equals to
${A}_{G}\otimes {J}_{k}+{I}_{n}\otimes {A}_{{K}_{k}}$
. Here
${A}_{G}$
is the adjacency matrix of
$G$
,
${J}_{k}$
is the all one matrix of size
$k\times k$
,
${I}_{n}$
is the identity matrix of size
$n\times n$
and
${A}_{{K}_{k}}$
is the adjacency matrix of the complete graph of order
$k$
. Also the tensor product of the
$m\times n$
dimensional matrix
$A=\left({a}_{ij}\right)$
and the
$s\times t$
dimensional matrix
$B=\left({b}_{kl}\right)$
is the
$ms\times nt$
dimensional matrix
$A\otimes B$
, whose entry labeled
$\left(\right(i,k\left)\right(j,l\left)\right)$
is
${a}_{ij}{b}_{kl}$
. In case
$A$
and
$B$
are symmetric matrices with spectrums
$\{{\lambda}_{1},\dots ,{\lambda}_{n}\}$
,
$\{{\mu}_{1},\dots ,{\mu}_{t}\}$
respectively, it is a simple consequence of the definition that the spectrum of
$A\otimes B$
is
$\{{\lambda}_{i}{\mu}_{k}:i=1,\dots ,n,k=1,\dots ,t\}$
(see, e.g. [
64]
). Therefore the second eigenvalue of
${A}_{G}\otimes {J}_{k}$
is
$k\lambda $
.
On the other hand
${I}_{n}\otimes {A}_{{K}_{k}}$
is the adjacency matrix of the disjoint union of
$k$
cliques and therefore the absolute value of all its eigenvalues is at most
$k1$
. Using these two facts we conclude that
${\lambda}^{\prime}\le \lambda k+k1$
and that
${G}_{k}$
is
$({n}^{\prime}=nk,{d}^{\prime}=dk+k1,{\lambda}^{\prime}=\lambda k+k1)$
graph. Also it is easy to see that the set of vertices of
${G}_{k}$
that corresponds to a vertex in
$G$
has exactly
$dk$
neighbors outside this set. By deleting these neighbors we can disconnect the graph
${G}_{k}$
and thus
$$\kappa \left({G}_{k}\right)\le dk={d}^{\prime}(k1)={d}^{\prime}\Omega \left(({\lambda}^{\prime}{)}^{2}/{d}^{\prime}\right).$$
Sometimes we can improve the result of Theorem 4.1 using the information about codegrees of vertices in our graph. Such result was used in [
61]
to determine the vertexconnectivity of dense random
$d$
regular graphs.
Proposition 4.2
[
61]
Let
$G=(V,E)$
be a
$d$
regular graph on
$n$
vertices such that
$\sqrt{n}logn<d\le 3n/4$
and the number of common neighbors for every two distinct vertices in
$G$
is
$(1+o(1\left)\right){d}^{2}/n$
.
Then the graph
$G$
is
$d$
vertexconnected.
Similarly to vertexconnectivity, define the edgeconnectivity of a graph
$G$
to be the minimum number of edges that we need to delete to make
$G$
disconnected. We denote this parameter by
${\kappa}^{\prime}\left(G\right)$
. Clearly the edgeconnectivity is always at most the minimum degree of a graph. We also say that
$G$
has a perfect matching if there is a set of disjoint edges that covers all the vertices of
$G$
.
Next we show that
$(n,d,\lambda )$
graphs even with a very weak spectral gap are
$d$
edgeconnected and have a perfect matching (if the number of vertices is even).
Theorem 4.3
Let
$G$
be an
$(n,d,\lambda )$
graph with
$d\lambda \ge 2$
. Then
$G$
is
$d$
edgeconnected. When
$n$
is even, it has a perfect matching.
Proof. Let
$U$
be a subset of vertices of
$G$
of size at most
$n/2$
. To prove that
$G$
is
$d$
edgeconnected we need to show that there are always at least
$d$
edges between
$U$
and
$V\left(G\right)U$
. If
$1\le \leftU\right\le d$
, then every vertex in
$U$
has at least
$d\left(\rightU1)$
neighbors outside
$U$
and therefore
$e(U,V(G)U)\ge \leftU\right\left(d\leftU\right+1\right)\ge d$
. On the other hand if
$d\le \leftU\right\le n/2$
, then using that
$d\lambda \ge 2$
together with Theorem 2.11 we obtain that
$$\begin{array}{ccc}e\left(U,V\left(G\right)U\right)& \ge & \frac{d\leftU\right(nU\left\right)}{n}\lambda \sqrt{\leftU\right(nU\left\right)\left(1\frac{\leftU\right}{n}\right)\left(1\frac{n\leftU\right}{n}\right)}\end{array}$$  
$$\begin{array}{ccc}& =& (d\lambda )\frac{(nU\left\right)}{n}\leftU\right\ge 2\cdot \frac{1}{2}\cdot \leftU\right=\leftU\right\ge d,\end{array}$$  
and therefore
${\kappa}^{\prime}\left(G\right)=d$
.
To show that
$G$
contains a perfect matching we apply the celebrated Tutte's condition. Since
$n$
is even, we need to prove that for every nonempty set of vertices
$S$
, the induced graph
$G[VS]$
has at most
$\leftS\right$
connected components of odd size. Since
$G$
is
$d$
edgeconnected we have that there are at least
$d$
edges from every connected component of
$G[VS]$
to
$S$
. On the other hand there are at most
$d\leftS\right$
edges incident with vertices in
$S$
. Therefore
$G[VS]$
has at most
$\leftS\right$
connected components and hence
$G$
contains a perfect matching.
$\square $
4.2 Maximum cut
Let
$G=(V,E)$
be a graph and let
$S$
be a nonempty proper subset of
$V$
. Denote by
$(S,VS)$
the cut of
$G$
consisting of all edges with one end in
$S$
and another one in
$VS$
. The size of the cut is the number of edges in it. The MAX CUT problem is the problem of finding a cut of maximum size in
$G$
. Let
$f\left(G\right)$
be the size of the maximum cut in
$G$
. MAX CUT is one of the most natural combinatorial optimization problems. It is well known that this problem is NPhard [
45]
. Therefore it is useful to have bounds on
$f\left(G\right)$
based on other parameters of the graph, that can be computed efficiently.
Here we describe two such folklore results. First, consider a random partition
$V={V}_{1}\cup {V}_{2}$
, obtained by assigning each vertex
$v\in V$
to
${V}_{1}$
or
${V}_{2}$
with probability
$1/2$
independently. It is easy to see that each edge of
$G$
has probability
$1/2$
to cross between
${V}_{1}$
and
${V}_{2}$
. Therefore the expected number of edges in the cut
$({V}_{1},{V}_{2})$
is
$m/2$
, where
$m$
is the number of edges in
$G$
. This implies that for every graph
$f\left(G\right)\ge m/2$
. The example of a complete graph shows that this lower bound is asymptotically optimal. The second result provides an upper bound for
$f\left(G\right)$
, for a regular graph
$G$
, in terms of the smallest eigenvalue of its adjacency matrix.
Proposition 4.4
Let
$G$
be a
$d$
regular graph (which may have loops) of order
$n$
with
$m=dn/2$
edges and let
${\lambda}_{1}\ge {\lambda}_{2}\ge \dots \ge {\lambda}_{n}$
be the eigenvalues of the adjacency matrix of
$G$
. Then
$$f\left(G\right)\le \frac{m}{2}\frac{{\lambda}_{n}n}{4}.$$
In particular if
$G$
is an
$(n,d,\lambda )$
graph then
$f\left(G\right)\le (d+\lambda )n/4$
.
Proof. Let
$A=\left({a}_{ij}\right)$
be the adjacency matrix of
$G=(V,E)$
and let
$V=\{1,\dots ,n\}$
. Let
$\mathbf{x}=({x}_{1},\dots ,{x}_{n})$
be any vector with coordinates
$\pm 1$
. Since the graph
$G$
is
$d$
regular we have
$${\sum}_{(i,j)\in E}({x}_{i}{x}_{j}{)}^{2}=d{\sum}_{i=1}^{n}{x}_{i}^{2}{\sum}_{i,j}{a}_{ij}{x}_{i}{x}_{j}=dn{\mathbf{x}}^{t}A\mathbf{x}.$$
By the variational definition of the eigenvalues of
$A$
, for any vector
$z\in {R}^{n}$
,
${z}^{t}Az\ge {\lambda}_{n}\parallel z{\parallel}^{2}$
.
Therefore
$$\begin{array}{c}{\sum}_{(i,j)\in E}({x}_{i}{x}_{j}{)}^{2}=dn{\mathbf{x}}^{t}A\mathbf{x}\le dn{\lambda}_{n}\parallel \mathbf{x}{\parallel}^{2}=dn{\lambda}_{n}n.\end{array}$$ 
(11)

Let
$V={V}_{1}\cup {V}_{2}$
be an arbitrary partition of
$V$
into two disjoint subsets and let
$e({V}_{1},{V}_{2})$
be the number of edges in the bipartite subgraph of
$G$
with bipartition
$({V}_{1},{V}_{2})$
. For every vertex
$v\in V\left(G\right)$
define
${x}_{v}=1$
if
$v\in {V}_{1}$
and
${x}_{v}=1$
if
$v\in {V}_{2}$
. Note that for every edge
$(i,j)$
of
$G$
,
$({x}_{i}{x}_{j}{)}^{2}=4$
if this edge has its ends in the distinct parts of the above partition and is zero otherwise. Now using ( 11 ), we conclude that
$$e({V}_{1},{V}_{2})=\frac{1}{4}{\sum}_{(i,j)\in E}({x}_{i}{x}_{j}{)}^{2}\le \frac{1}{4}(dn{\lambda}_{n}n)=\frac{m}{2}\frac{{\lambda}_{n}n}{4}.\square $$
This upper bound is often used to show that some particular results about maximum cuts are tight. For example this approach was used in [
5]
and [
8]
. In these papers the authors proved that for every graph
$G$
with
$m$
edges and girth at least
$r\ge 4$
,
$f\left(G\right)\ge m/2+\Omega \left({m}^{\frac{r}{r+1}}\right)$
. They also show, using Proposition 4.4 and Examples 9, 6 from Section 3, that this bound is tight for
$r=4,5$
.
4.3 Independent sets and the chromatic number
The independence number
$\alpha \left(G\right)$
of a graph
$G$
is the maximum cardinality of a set of vertices of
$G$
no two of which are adjacent. Using Theorem 2.11 we can immediately establish an upper bound on the size of a maximum independent set of pseudorandom graphs.
Proposition 4.5
Let
$G$
be an
$(n,d,\lambda )$
graph, then
$$\alpha \left(G\right)\le \frac{\lambda n}{d+\lambda}.$$
Proof. Let
$U$
be an independent set in
$G$
, then
$e\left(U\right)=0$
and by Theorem 2.11 we have that
$dU{}^{2}/n\le \lambda U\left\right(1\leftU\right/n)$
. This implies that
$\leftU\right\le \lambda n/(d+\lambda )$
.
$\square $
Note that even when
$\lambda =O\left(\sqrt{d}\right)$
this bound only has order of magnitude
$O(n/\sqrt{d})$
. This contrasts sharply with the behavior of random graphs where it is known (see [
20]
and [
49]
) that the independence number of random graph
$G(n,p)$
is only
$\Theta \left(\frac{n}{d}logd\right)$
where
$d=(1+o(1\left)\right)np$
. More strikingly there are graphs for which the bound in Proposition 4.5 cannot be improved. One such graph is the Paley graph
${P}_{q}$
with
$q={p}^{2}$
(Example 3 in the previous section). Indeed it is easy to see that in this case all elements of the subfield
$GF\left(p\right)\subset GF\left({p}^{2}\right)$
are quadratic residues in
$GF\left({p}^{2}\right)$
. This implies that for every quadratic nonresidue
$\beta \in GF\left({p}^{2}\right)$
all elements of any multiplicative coset
$\beta GF\left(p\right)$
form an independent set of size
$p$
. As we already mentioned,
${P}_{q}$
is an
$(n,d,\lambda )$
graph with
$n={p}^{2},d=({p}^{2}1)/2$
and
$\lambda =(p+1)/2$
. Hence for this graph we get
$\alpha \left({P}_{q}\right)=\lambda n/(d+\lambda )$
.
Next we obtain a lower bound on the independence number of pseudorandom graphs. We present a slightly more general result by Alon et al. [
12]
which we will need later.
Proposition 4.6
[
12]
Let
$G$
be an
$(n,d,\lambda )$
graph such that
$\lambda <d\le 0.9n$
. Then the induced subgraph
$G\left[U\right]$
of
$G$
on any subset
$U,\leftU\right=m$
, contains an independent set of size at least
$$\alpha \left(G\right[U\left]\right)\ge \frac{n}{2(d\lambda )}ln\left(\frac{m(d\lambda )}{n(\lambda +1)}+1\right).$$
In particular,
$$\alpha \left(G\right)\ge \frac{n}{2(d\lambda )}ln\left(\frac{(d\lambda )}{(\lambda +1)}+1\right).$$
Sketch of proof. First using Theorem 2.11 it is easy to show that if
$U$
is a set of
$bn$
vertices of
$G$
, then the minimum degree in the induced subgraph
$G\left[U\right]$
is at most
$db+\lambda (1b)=(d\lambda )b+\lambda $
. Construct an independent set
$I$
in the induced subgraph
$G\left[U\right]$
of
$G$
by the following greedyprocedure. Repeatedly choose a vertex of minimum degree in
$G\left[U\right]$
, add it to the independent set
$I$
and delete it and its neighbors from
$U$
, stopping when the remaining set of vertices is empty. Let
${a}_{i},i\ge 0$
be the sequence of numbers defined by the following recurrence formula:
$${a}_{0}=m,{a}_{i+1}={a}_{i}\left(d\frac{{a}_{i}}{n}+\lambda (1\frac{{a}_{i}}{n})+1\right)=\left(1\frac{d\lambda}{n}\right){a}_{i}(\lambda +1),\forall i\ge 0.$$
By the above discussion, it is easy to see that the size of the remaining set of vertices after
$i$
iterations is at least
${a}_{i}$
. Therefore the size of the resulting independent set
$I$
is at least the smallest index
$i$
such that
${a}_{i}\le 0$
. By solving the recurrence equation we obtain that this index satisfies:
$$i\ge \frac{n}{2(d\lambda )}ln\left(\frac{m(d\lambda )}{n(\lambda +1)}+1\right).\square $$
For an
$(n,d,\lambda )$
graph
$G$
with
$\lambda \le {d}^{1\delta},\delta >0$
, this proposition implies that
$\alpha \left(G\right)\ge \Omega \left(\frac{n}{d}logd\right)$
.
This shows that the independence number of a pseudorandom graph with a sufficiently small second eigenvalue is up to a constant factor at least as large as
$\alpha \left(G\right(n,p\left)\right)$
with
$p=d/n$
. On the other hand the graph
${H}_{k}$
(Example 4, Section 3) shows that even when
$\lambda \le O\left(\sqrt{d}\right)$
the independence number of
$(n,d,\lambda )$
graph can be smaller than
$\alpha \left(G\right(n,p\left)\right)$
with
$p=d/n$
. This graph has
$n={2}^{k1}1$
vertices, degree
$d=(1+o(1\left)\right)n/2$
and
$\lambda =\Theta \left(\sqrt{d}\right)$
. Also it is easy to see that every independent set in
${H}_{k}$
corresponds to a family of orthogonal vectors in
${\mathbf{Z}}_{2}^{k}$
and thus has size at most
$k=(1+o(1\left)\right){log}_{2}n$
.
This is only half of the size of a maximum independent set in the corresponding random graph
$G(n,1/2)$
.
A
vertexcoloring of a graph
$G$
is an assignment of a color to each of its vertices. The coloring is proper if no two adjacent vertices get the same color. The chromatic number
$\chi \left(G\right)$
of
$G$
is the minimum number of colors used in a proper coloring of it. Since every color class in the proper coloring of
$G$
forms an independent set we can immediately obtain that
$\chi \left(G\right)\ge \leftV\right(G\left)\right/\alpha \left(G\right)$
. This together with Proposition 4.5 implies the following result of Hoffman [
48]
.
Corollary 4.7
Let
$G$
be an
$(n,d,\lambda )$
graph. Then the chromatic number of
$G$
is at least
$1+d/\lambda $
.
On the other hand, using Proposition 4.6 , one can obtain the following upper bound on the chromatic number of pseudorandom graphs.
Theorem 4.8
[
12]
Let
$G$
be an
$(n,d,\lambda )$
graph such that
$\lambda <d\le 0.9n$
. Then the chromatic number of
$G$
satisfies
$$\chi \left(G\right)\le \frac{6(d\lambda )}{ln\left(\frac{d\lambda}{\lambda +1}+1\right)}.$$
Sketch of proof. Color the graph
$G$
as follows. As long as the remaining set of vertices
$U$
contains at least
$n/ln(\frac{d\lambda}{\lambda +1}+1)$
vertices, by Proposition 4.6 we can find an independent set of vertices in the induced subgraph
$G\left[U\right]$
of size at least
$$\frac{n}{2(d\lambda )}ln\left(\frac{\leftU\right(d\lambda )}{n(\lambda +1)}+1\right)\ge \frac{n}{4(d\lambda )}ln\left(\frac{d\lambda}{\lambda +1}+1\right).$$
Color all the members of such a set by a new color, delete them from the graph and continue.
When this process terminates, the remaining set of vertices
$U$
is of size at most
$n/ln(\frac{d\lambda}{\lambda +1}+1)$
and we used at most
$4(d\lambda )/ln(\frac{d\lambda}{\lambda +1}+1)$
colors so far. As we already mentioned above, for every subset
${U}^{\prime}\subset U$
the induced subgraph
$G\left[{U}^{\prime}\right]$
contains a vertex of degree at most
$$(d\lambda )\frac{\left{U}^{\prime}\right}{n}+\lambda \le (d\lambda )\frac{\leftU\right}{n}+\lambda \le \frac{d\lambda}{ln(\frac{d\lambda}{\lambda +1}+1)}+\lambda \le \frac{2(d\lambda )}{ln(\frac{d\lambda}{\lambda +1}+1)}1.$$
Thus we can complete the coloring of
$G$
by coloring
$G\left[U\right]$
using at most
$2(d\lambda )/ln(\frac{d\lambda}{\lambda +1}+1)$
additional colors. The total number of colors used is at most
$6(d\lambda )/ln(\frac{d\lambda}{\lambda +1}+1)$
.
$\square $
For an
$(n,d,\lambda )$
graph
$G$
with
$\lambda \le {d}^{1\delta},\delta >0$
this proposition implies that
$\chi \left(G\right)\le O\left(\frac{d}{logd}\right)$
.
This shows that the chromatic number of a pseudorandom graph with a sufficiently small second eigenvalue is up to a constant factor at least as small as
$\chi \left(G\right(n,p\left)\right)$
with
$p=d/n$
. On the other hand, the Paley graph
${P}_{q},q={p}^{2}$
, shows that sometimes the chromatic number of a pseudorandom graph can be much smaller than the above bound, even in the case
$\lambda =\Theta \left(\sqrt{d}\right)$
. Indeed, as we already mentioned above, all elements of the subfield
$GF\left(p\right)\subset GF\left({p}^{2}\right)$
are quadratic residues in
$GF\left({p}^{2}\right)$
.
This implies that for every quadratic nonresidue
$\beta \in GF\left({p}^{2}\right)$
all elements of a multiplicative coset
$\beta GF\left(p\right)$
form an independent set of size
$p$
. Also all additive cosets of
$\beta GF\left(p\right)$
are independent sets in
${P}_{q}$
. This implies that
$\chi \left({P}_{q}\right)\le \sqrt{q}=p$
. In fact
${P}_{q}$
contains a clique of size
$p$
(all elements of a subfield
$GF\left(p\right)$
), showing that
$\chi \left({P}_{q}\right)=\sqrt{q}\ll q/logq$
. Therefore the bound in Corollary 4.7 is best possible.
A more complicated quantity related to the chromatic number is the
listchromatic number
${\chi}_{l}\left(G\right)$
of
$G$
, introduced in [
34]
and [
82]
. This is the minimum integer
$k$
such that for every assignment of a set
$S\left(v\right)$
of
$k$
colors to every vertex
$v$
of
$G$
, there is a proper coloring of
$G$
that assigns to each vertex
$v$
a color from
$S\left(v\right)$
. The study of this parameter received a considerable amount of attention in recent years, see, e.g., [
2]
, [
57]
for two surveys. Note that from the definition it follows immediately that
${\chi}_{l}\left(G\right)\ge \chi \left(G\right)$
and it is known that the gap between these two parameters can be arbitrarilylarge. The listchromatic number of pseudorandom graphs was studied by Alon, Krivelevich and Sudakov [
12]
and independently by Vu [
84]
. In [
12]
and [
84]
the authors mainly considered graphs with all degrees
$(1+o(1\left)\right)np$
and all codegrees
$(1+o(1\left)\right)n{p}^{2}$
. Here we use ideas from these two papers to obtain an upper bound on the listchromatic number of an
$(n,d,\lambda )$
graphs. This bound has the same order of magnitude as the list chromatic number of the truly random graph
$G(n,p)$
with
$p=d/n$
(for more details see [
12]
, [
84]
).
Theorem 4.9
Suppose that
$0<\delta <1$
and let
$G$
be an
$(n,d,\lambda )$
graph satisfying
$\lambda \le {d}^{1\delta}$
,
$d\le 0.9n$
. Then the listchromatic number of
$G$
is bounded by
$${\chi}_{l}\left(G\right)\le O\left(\frac{d}{\delta logd}\right).$$
Proof. Suppose that
$d$
is sufficiently large and consider first the case when
$d\le {n}^{1\delta /4}$
. Then by Theorem 2.11 the neighbors of every vertex in
$G$
span at most
${d}^{3}/n+\lambda d\le O\left({d}^{2\delta /4}\right)$
edges. Now we can apply the result of Vu [
84]
which says that if the neighbors of every vertex in a graph
$G$
with maximum degree
$d$
span at most
$O\left({d}^{2\delta /4}\right)$
edges then
${\chi}_{l}\left(G\right)\le O\left(d/(\delta logd)\right).$
Now consider the case when
$d\ge {n}^{1\delta /4}$
. For every vertex
$v\in V$
, let
$S\left(v\right)$
be a list of at least
$\frac{7d}{\delta logn}$
colors. Our objective is to prove that there is a proper coloring of
$G$
assigning to each vertex a color from its list. As long as there is a set
$C$
of at least
${n}^{1\delta /2}$
vertices containing the same color
$c$
in their lists we can, by Proposition 4.6 , find an independent set of at least
$\frac{\delta n}{6d}logn$
vertices in
$C$
, color them all by
$c$
, omit them from the graph and omit the color
$c$
from all lists. The total number of colors that can be deleted in this process cannot exceed
$\frac{6d}{\delta logn}$
(since in each such deletion at least
$\frac{\delta n}{6d}logn$
vertices are deleted from the graph). When this process terminates, no color appears in more than
${n}^{1\delta /2}$
lists, and each list still contains at least
$\frac{d}{\delta logn}>{n}^{1\delta /2}$
colors. Therefore, by Hall's theorem, we can assign to each of the remaining vertices a color from its list so that no color is being assigned to more than one vertex, thus completing the coloring and the proof.
$\square $
4.4 Small subgraphs
We now examine small subgraphs of pseudorandom graphs. Let
$H$
be a fixed graph of order
$s$
with
$r$
edges and with automorphism group
$Aut\left(H\right)$
. Using the second moment method it is not difficult to show that for every constant
$p$
the random graph
$G(n,p)$
contains
$$(1+o(1\left)\right){p}^{r}(1p{)}^{\left(\genfrac{}{}{0ex}{}{s}{2}\right)r}\frac{{n}^{s}}{\leftAut\right(H\left)\right}$$
induced copies of
$H$
. Thomason extended this result to jumbled graphs. He showed in [
79]
that if a graph
$G$
is
$(p,\alpha )$
jumbled and
${p}^{s}n\gg 42\alpha {s}^{2}$
then the number of induced subgraphs of
$G$
which are isomorphic to
$H$
is
$(1+o(1\left)\right){p}^{s}(1p{)}^{\left(\genfrac{}{}{0ex}{}{s}{2}\right)r}{n}^{s}/Aut\left(H\right)$
.
Here we present a result of Noga Alon [
6]
that proves that every large subset of the set of vertices of
$(n,d,\lambda )$
graph contains the ”correct” number of copies of any fixed sparse graph. An additional advantage of this result is that its assertion depends not on the number of vertices
$s$
in
$H$
but only on its maximum degree
$\Delta $
which can be smaller than
$s$
. Special cases of this result have appeared in various papers including [
11]
, [
13]
and probably other papers as well. The approach here is similar to the one in [
13]
.
Theorem 4.10
[
6]
Let
$H$
be a fixed graph with
$r$
edges,
$s$
vertices and maximum degree
$\Delta $
, and let
$G=(V,E)$
be an
$(n,d,\lambda )$
graph, where, say,
$d\le 0.9n$
. Let
$m<n$
satisfy
$m\gg \lambda (\frac{n}{d}{)}^{\Delta}$
.
Then, for every subset
${V}^{\prime}\subset V$
of cardinality
$m$
, the number of (not necessarily induced) copies of
$H$
in
${V}^{\prime}$
is
$$\left(1+o\left(1\right)\right)\frac{{m}^{s}}{\leftAut\right(H\left)\right}{\left(\frac{d}{n}\right)}^{r}.$$
Note that this implies that a similar result holds for the number of induced copies of
$H$
. Indeed, if
$n\gg d$
and
$m\gg \lambda (\frac{n}{d}{)}^{\Delta +1}$
then the number of copies of each graph obtained from
$H$
by adding to it at least one edge is, by the above Theorem, negligible compared to the number of copies of
$H$
, and hence almost all copies of
$H$
in
${V}^{\prime}$
are induced. If
$d=\Theta \left(n\right)$
then, by inclusionexclusion, the number of induced copies of
$H$
in
${V}^{\prime}$
as above is also roughly the ”correct” number. A special case of the above theorem implies that if
$\lambda =O\left(\sqrt{d}\right)$
and
$d\gg {n}^{2/3}$
, then any
$(n,d,\lambda )$
graph contains many triangles. As shown in Example 9, Section 3, this is not true when
$d=(\frac{1}{4}+o(1\left)\right){n}^{2/3}$
, showing that the assertion of the theorem is not far from being best possible.
Proof of Theorem 4.10 . To prove the theorem, consider a random onetoone mapping of the set of vertices of
$H$
into the set of vertices
${V}^{\prime}$
. Denote by
$A\left(H\right)$
the event that every edge of
$H$
is mapped on an edge of
$G$
. In such a case we say that the mapping is an embedding of
$H$
. Note that it suffices to prove that
$$\begin{array}{c}Pr\left(A\right(H\left)\right)=(1+o(1\left)\right){\left(\frac{d}{n}\right)}^{r}.\end{array}$$ 
(12)

We prove ( 12 ) by induction on the number of edges
$r$
. The base case
$(r=0)$
is trivial. Suppose that ( 12 ) holds for all graphs with less than
$r$
edges, and let
$uv$
be an edge of
$H$
. Let
${H}_{uv}$
be the graph obtained from
$H$
by removing the edge
$uv$
(and keeping all vertices). Let
${H}_{u}$
and
${H}_{v}$
be the induced subgraphs of
$H$
on the sets of vertices
$V\left(H\right)\backslash \left\{v\right\}$
and
$V\left(H\right)\backslash \left\{u\right\}$
, respectively, and let
${H}^{\prime}$
be the induced subgraph of
$H$
on the set of vertices
$V\left(H\right)\backslash \{u,v\}$
. Let
${r}^{\prime}$
be the number of edges of
${H}^{\prime}$
and note that
$r{r}^{\prime}\le 2(\Delta 1)+1=2\Delta 1.$
Clearly
$Pr\left(A\right({H}_{uv}\left)\right)=Pr\left(A\right({H}_{uv}\left)\rightA\left({H}^{\prime}\right))\cdot Pr(A\left({H}^{\prime}\right))$
.
Thus, by the induction hypothesis applied to
${H}_{uv}$
and to
${H}^{\prime}$
:
$$Pr\left(A\right({H}_{uv}\left)\rightA\left({H}^{\prime}\right))=(1+o\left(1\right)){\left(\frac{d}{n}\right)}^{r1{r}^{\prime}}.$$
For an embedding
${f}^{\prime}$
of
${H}^{\prime}$
, let
$\nu (u,{f}^{\prime})$
be the number of extensions of
${f}^{\prime}$
to an embedding of
${H}_{u}$
in
${V}^{\prime}$
;
$\nu (v,{f}^{\prime})$
denotes the same for
$v$
. Clearly, the number of extensions of
${f}^{\prime}$
to an embedding of
${H}_{uv}$
in
${V}^{\prime}$
is at least
$\nu (u,{f}^{\prime})\nu (v,{f}^{\prime})min\left(\nu \right(u,{f}^{\prime}),\nu (v,{f}^{\prime}\left)\right)$
and at most
$\nu (u,{f}^{\prime})\nu (v,{f}^{\prime})$
. Thus we have
$$\frac{\nu (u,{f}^{\prime})\nu (v,{f}^{\prime})min\left(\nu \right(u,{f}^{\prime}),\nu (v,{f}^{\prime}\left)\right)}{(ms+2)(ms+1)}\le Pr\left(A\left({H}_{uv}\right){f}^{\prime}\right)\le \frac{\nu (u,{f}^{\prime})\nu (v,{f}^{\prime})}{(ms+2)(ms+1)}.$$
Taking expectation over all embeddings
${f}^{\prime}$
the middle term becomes
$Pr\left(A\right({H}_{uv}\left)\rightA\left({H}^{\prime}\right))$
, which is
$(1+o(1\left)\right)(\frac{d}{n}{)}^{r1{r}^{\prime}}$
. Note that by our choice of the parameters and the well known fact that
$\lambda =\Omega \left(\sqrt{d}\right)$
, the expectation of the term
$min\left(\nu \right(u,{f}^{\prime}),\nu (v,{f}^{\prime}\left)\right)(\le m)$
is negligible and we get
$${E}_{{f}^{\prime}}\left(\nu (u,{f}^{\prime})\nu (v,{f}^{\prime})\leftA\right({H}^{\prime})\right)=(1+o(1\left)\right){m}^{2}{\left(\frac{d}{n}\right)}^{r1{r}^{\prime}}.$$
Now let
$f$
be a random onetoone mapping of
$V\left(H\right)$
into
${V}^{\prime}$
. Let
${f}^{\prime}$
be a fixed embedding of
${H}^{\prime}$
.
Then
$$P{r}_{f}\left(A\left(H\right)f{}_{V\left(H\right)\backslash \{u,v\}}={f}^{\prime}\right)=\left(\frac{d}{n}\right)\frac{\nu (u,{f}^{\prime})\nu (v,{f}^{\prime})}{(ms+2)(ms+1)}+\delta ,$$
where
$\left\delta \right\le \lambda \frac{\sqrt{\nu (u,{f}^{\prime})\nu (v,{f}^{\prime})}}{(ms+2)(ms+1)}$
. This follows from Theorem 2.11 , where we take the possible images of
$u$
as the set
$U$
and the possible images of
$v$
as the set
$W$
. Averaging over embeddings
${f}^{\prime}$
we get
$Pr\left(A\right(H\left)\rightA\left({H}^{\prime}\right))$
on the left hand side. On the right hand side we get
$(1+o(1\left)\right)(\frac{d}{n}{)}^{r{r}^{\prime}}$
from the first term plus the expectation of the error term
$\delta $
. By Jensen's inequality, the absolute value of this expectation is bounded by
$$\lambda \frac{\sqrt{E\left(\nu \right(u,{f}^{\prime}\left)\nu \right(v,{f}^{\prime}\left)\right)}}{(ms+2)(ms+1)}=(1+o(1\left)\right)\frac{\lambda}{m}{\left(\frac{d}{n}\right)}^{(r{r}^{\prime}1)/2}.$$
Our assumptions on the parameters imply that this is negligible with respect to the main term.
Therefore
$Pr\left(A\right(H\left)\right)=Pr\left(A\right(H\left)\rightA\left({H}^{\prime}\right))\cdot Pr(A\left({H}^{\prime}\right))=(1+o\left(1\right)){\left(\frac{d}{n}\right)}^{r}$
, completing the proof of Theorem 4.10 .
$\square $
If we are only interested in the existence of one copy of
$H$
then one can sometimes improve the conditions on
$d$
and
$\lambda $
in Theorem 4.10 . For example if
$H$
is a complete graph of order
$r$
thenthe following result was proved in [
11]
.
Proposition 4.11
[
11]
Let
$G$
be an
$(n,d,\lambda )$
graph. Then for every integer
$r\ge 2$
every set of vertices of
$G$
of size more than
$$\frac{(\lambda +1)n}{d}\left(1+\frac{n}{d}+\dots +{\left(\frac{n}{d}\right)}^{r2}\right)$$
contains a copy of a complete graph
${K}_{r}$
.
In particular, when
$d\ge \Omega \left({n}^{2/3}\right)$
and
$\lambda \le O\left(\sqrt{d}\right)$
then any
$(n,d,\lambda )$
graph contains a triangle and as shows Example 9 in Section 3 this is tight. Unfortunately we do not know if this bound is also tight for
$r\ge 4$
. It would be interesting to construct examples of
$(n,d,\lambda )$
graphs with
$d=\Theta \left({n}^{11/(2r3)}\right)$
and
$\lambda \le O\left(\sqrt{d}\right)$
which contain no copy of
${K}_{r}$
.
Finally we present one additional result about the existence of odd cycles in pseudorandom graphs.
Proposition 4.12
Let
$k\ge 1$
be an integer and let
$G$
be an
$(n,d,\lambda )$
graph such that
${d}^{2k}/n\gg {\lambda}^{2k1}$
. Then
$G$
contains a cycle of length
$2k+1$
.
Proof. Suppose that
$G$
contains no cycle of length
$2k+1$
. For every two vertices
$u,v$
of
$G$
denote by
$d(u,v)$
the length of a shortest path from
$u$
to
$v$
. For every
$i\ge 1$
let
${N}_{i}\left(v\right)=\{ud(u,v)=i\}$
be the set of all vertices in
$G$
which are at distance exactly
$i$
from
$v$
. In [
32]
Erdős et al. proved that if
$G$
contains no cycle of length
$2k+1$
then for any
$1\le i\le k$
the induced graph
$G\left[{N}_{i}\right(v\left)\right]$
contains an independent set of size
$\left{N}_{i}\right(v\left)\right/(2k1)$
. This result together with Proposition 4.5 implies that for every vertex
$v$
and for every
$1\le i\le k$
,
$\left{N}_{i}\right(v\left)\right\le (2k1)\lambda n/d$
. Since
${d}^{2k}/n\gg {\lambda}^{2k1}$
we have that
$\lambda =o\left(d\right)$
. Therefore by Theorem 2.11
$$e\left({N}_{i}\left(v\right)\right)\le \frac{d}{2n}\left{N}_{i}\right(v){}^{2}+\lambda {N}_{i}\left(v\right)\le \frac{d}{n}\frac{(2k1)\lambda n}{2d}{N}_{i}\left(v\right)+\lambda {N}_{i}\left(v\right)<2k\lambda {N}_{i}\left(v\right)=o\left(d\left{N}_{i}\right(v\left)\right\right).$$
Next we prove by induction that for every
$1\le i\le k$
,
$\frac{\left{N}_{i+1}\right(v\left)\right}{\left{N}_{i}\right(v\left)\right}\ge (1o(1\left)\right){d}^{2}/{\lambda}^{2}$
. By the above discussion the number of edges spanned by
${N}_{1}\left(v\right)$
is
$o\left({d}^{2}\right)$
and therefore
$e\left({N}_{1}\left(v\right),{N}_{2}\left(v\right)\right)={d}^{2}o\left({d}^{2}\right)=(1o(1\left)\right){d}^{2}$
. On the other hand, by Theorem 2.11
$$\begin{array}{ccc}e\left({N}_{1}\left(v\right),{N}_{2}\left(v\right)\right)& \le & \frac{d}{n}\left{N}_{1}\right(v\left)\right\left{N}_{2}\right(v\left)\right+\lambda \sqrt{\left{N}_{1}\right(v\left)\right\left{N}_{2}\right(v\left)\right}\le \frac{d}{n}d\frac{(2k1)\lambda n}{d}+\lambda \sqrt{d\left{N}_{2}\right(v\left)\right}\end{array}$$  
$$\begin{array}{ccc}& =& \lambda d\sqrt{\frac{\left{N}_{2}\right(v\left)\right}{d}}+O\left(\lambda d\right)=\lambda d\sqrt{\frac{\left{N}_{2}\right(v\left)\right}{\left{N}_{1}\right(v\left)\right}}+o\left({d}^{2}\right).\end{array}$$  
Therefore
$\frac{\left{N}_{2}\right(v\left)\right}{\left{N}_{1}\right(v\left)\right}\ge (1o(1\left)\right){d}^{2}/{\lambda}^{2}$
. Now assume that
$\frac{\left{N}_{i}\right(v\left)\right}{\left{N}_{i1}\right(v\left)\right}\ge (1o(1\left)\right){d}^{2}/{\lambda}^{2}$
. Since the number of edges spanned by
${N}_{i}\left(v\right)$
is
$o\left(d\left{N}_{i}\right(v\left)\right\right)$
we obtain
$$\begin{array}{ccc}e\left({N}_{i}\left(v\right),{N}_{i+1}\left(v\right)\right)& =& d\left{N}_{i}\right(v\left)\right2e\left({N}_{i}\left(v\right)\right)e\left({N}_{i1}\left(v\right),{N}_{i}\left(v\right)\right)\end{array}$$  
$$\begin{array}{ccc}& \ge & d\left{N}_{i}\right(v\left)\righto\left(d\left{N}_{i}\right(v\left)\right\right)d\left{N}_{i1}\right(v\left)\right\end{array}$$  
$$\begin{array}{ccc}& \ge & (1o(1\left)\right)d\left{N}_{i}\right(v\left)\right(1+o(1\left)\right)d({\lambda}^{2}/{d}^{2})\left{N}_{i}\right(v\left)\right\end{array}$$  
$$\begin{array}{ccc}& =& (1o(1\left)\right)d\left{N}_{i}\right(v\left)\righto\left(d\left{N}_{i}\right(v\left)\right\right)=(1o(1\left)\right)d\left{N}_{i}\right(v\left)\right.\end{array}$$  
On the other hand, by Theorem 2.11
$$\begin{array}{ccc}e\left({N}_{i}\left(v\right),{N}_{i+1}\left(v\right)\right)& \le & \frac{d}{n}\left{N}_{i}\right(v\left)\right\left{N}_{i+1}\right(v\left)\right+\lambda \sqrt{\left{N}_{i}\right(v\left)\right\left{N}_{i+1}\right(v\left)\right}\end{array}$$  
$$\begin{array}{ccc}& \le & \frac{d}{n}\frac{(2k1)\lambda n}{d}\left{N}_{i}\right(v\left)\right+\lambda \sqrt{\left{N}_{i}\right(v\left)\right\left{N}_{i+1}\right(v\left)\right}\end{array}$$  
$$\begin{array}{ccc}& =& O\left(\lambda \right{N}_{i}\left(v\right)\left\right)+\lambda \left{N}_{i}\right(v\left)\right\sqrt{\frac{\left{N}_{i+1}\right(v\left)\right}{\left{N}_{i}\right(v\left)\right}}=\lambda \left{N}_{i}\right(v\left)\right\sqrt{\frac{\left{N}_{i+1}\right(v\left)\right}{\left{N}_{i}\right(v\left)\right}}+o\left(d\left{N}_{i}\right(v\left)\right\right).\end{array}$$  
Therefore
$\frac{\left{N}_{i+1}\right(v\left)\right}{\left{N}_{i}\right(v\left)\right}\ge (1o(1\left)\right){d}^{2}/{\lambda}^{2}$
and we proved the induction step.
Finally note that
$$\left{N}_{k}\right(v\left)\right={d}^{k1}{\prod}_{i=1}\frac{\left{N}_{i+1}\right(v\left)\right}{\left{N}_{i}\right(v\left)\right}\ge (1+o(1\left)\right)d{\left(\frac{{d}^{2}}{{\lambda}^{2}}\right)}^{k1}=(1+o(1\left)\right)\frac{{d}^{2k1}}{{\lambda}^{2k2}}\gg (2k1)\frac{\lambda n}{d}.$$
This contradiction completes the proof.
$\square $
This result implies that when
$d\gg {n}^{\frac{2}{2k+1}}$
and
$\lambda \le O\left(\sqrt{d}\right)$
then any
$(n,d,\lambda )$
graph contains a cycle of length
$2k+1$
. As shown by Example 10 of the previous section this result is tight. It is worth mentioning here that it follows from the result of Bondy and Simonovits [
22]
that any
$d$
regular graph with
$d\gg {n}^{1/k}$
contains a cycle of length
$2k$
. Here we do not need to make any assumption about the second eigenvalue
$\lambda $
. This bound is known to be tight for
$k=2,3,5$
(see Examples 6,7, Section 3).
4.5 Extremal properties
Turán's theorem [
81]
is one of the fundamental results in Extremal Graph Theory. It states that among
$n$
vertex graphs not containing a clique of size
$t$
the complete
$(t1)$
partite graph with (almost) equal parts has the maximum number of edges. For two graphs
$G$
and
$H$
we define the Turán number
$ex(G,H)$
of
$H$
in
$G$
, as the largest integer
$e$
, such that there is an
$H$
free subgraph of
$G$
with
$e$
edges. Obviously
$ex(G,H)\le \leftE\right(G\left)\right$
, where
$E\left(G\right)$
denotes the edge set of
$G$
. Turán's theorem, in an asymptotic form, can be restated as
$$ex({K}_{n},{K}_{t})=\left(\frac{t2}{t1}+o\left(1\right)\right)\left(\genfrac{}{}{0ex}{}{n}{2}\right),$$
that is the largest
${K}_{t}$
free subgraph of
${K}_{n}$
contains approximately
$\frac{t2}{t1}$
fraction of its edges. Here we would like to describe an extension of this result to
$(n,d,\lambda )$
graphs.
For an arbitrary graph
$G$
on
$n$
vertices it is easy to give a lower bound on
$ex(G,{K}_{t})$
following Turán's construction. One can partition the vertex set of
$G$
into
$t1$
parts such that the degree of each vertex within its own part is at most
$\frac{1}{t1}$
times its degree in
$G$
. Thus the subgraph consisting of the edges of
$G$
connecting two different parts has at least a
$\frac{t2}{t1}$
fraction of the edges of
$G$
and is clearly
${K}_{t}$
free. We say that a graph (or rather a family of graphs) is
$t$
Turán if this trivial lower bound is essentially an upper bound as well. More precisely,
$G$
is
$t$
Turán if
$ex(G,{K}_{t})=\left(\frac{t2}{t1}+o\left(1\right)\right)\leftE\right(G\left)\right$
.
It has been shown that for any fixed
$t$
, there is a number
$m(t,n)$
such that almost all graphs on
$n$
vertices with
$m\ge m(t,n)$
edges are
$t$
Turán (see [
77]
, [
51]
for the most recent estimate for
$m(t,n)$
). However, these results are about random graphs and do not provide a deterministic sufficient condition for a graph to be
$t$
Turán. It appears that such a condition can be obtained by a simple assumption about the spectrum of the graph. This was proved by Sudakov, Szabó and Vu in [
75]
. They obtained the following result.
Theorem 4.13
[
75]
Let
$t\ge 3$
be an integer and let
$G=(V,E)$
be an
$(n,d,\lambda )$
graph. If
$\lambda =o({d}^{t1}/{n}^{t2})$
then
$$ex(G,{K}_{t})=\left(\frac{t2}{t1}+o\left(1\right)\right)\leftE\right(G\left)\right.$$
Note that this theorem generalizes Turán's theorem, as the second eigenvalue of the complete graph
${K}_{n}$
is 1.
Let us briefly discuss the sharpness of Theorem
4.13 . For
$t=3$
, one can show that its condition involving
$n,d$
and
$\lambda $
is asymptotically tight. Indeed, in this case the above theorem states that if
${d}^{2}/n\gg \lambda $
, then one needs to delete about half of the edges of
$G$
to destroy all the triangles.
On the other hand, by taking the example of Alon (Section
3 , Example 9) whose parameters are:
$d=\Theta \left({n}^{2/3}\right)$
,
$\lambda =\Theta \left({n}^{1/3}\right)$
, and blowing it up (which means replacing each vertex by an independent set of size
$k$
and connecting two vertices in the new graph if and only if the corresponding vertices of
$G$
are connected by an edge) we get a graph
$G\left(k\right)$
with the following properties:
$\leftV\right(G\left(k\right)\left)\right={n}_{k}=nk$
;
$G\left(k\right)$
is
${d}_{k}=dk$
regular;
$G\left(k\right)$
is trianglefree;
$\lambda \left(G\right(k\left)\right)=k\lambda $
and
$\lambda \left(G\right(k\left)\right)=\Omega \left({d}_{k}^{2}/{n}_{k}\right)$
.
The above bound for the second eigenvalue of
$G\left(k\right)$
can be obtained by using well known results on the eigenvalues of the tensor product of two matrices, see [
59]
for more details. This construction implies that for
$t=3$
and any sensible degree
$d$
the condition in Theorem 4.13 is not far from being best possible.
4.6 Factors and fractional factors
Let
$H$
be a fixed graph on
$n$
vertices. We say that a graph
$G$
on
$n$
vertices has an
$H$
factor if
$G$
contains
$n/h$
vertex disjoint copies of
$H$
. Of course, a trivial necessary condition for the existence of an
$H$
factor in
$G$
is that
$h$
divides
$n$
. For example, if
$H$
is just an edge
$H={K}_{2}$
, then an
$H$
factor is a perfect matching in
$G$
.
One of the most important classes of graph embedding problems is to find sufficient conditions for the existence of an
$H$
factor in a graph
$G$
, usually assuming that
$H$
is fixed while the order
$n$
of
$G$
grows. In many cases such conditions are formulated in terms of the minimum degree of
$G$
.
For example, the classical result of Hajnal and Szemerédi [
47]
asserts that if the minimum degree
$\delta \left(G\right)$
satisfies
$\delta \left(G\right)\ge (1\frac{1}{r})n$
, then
$G$
contains
$\lfloor n/r\rfloor $
vertex disjoint copies of
${K}_{r}$
. The statement of this theorem is easily seen to be tight.
It turns our that pseudorandomness allows in many cases to significantly weaken sufficient conditions for
$H$
factors and to obtain results which fail to hold for general graphs of the same edge density.
Consider first the case of a constant edge density
$p$
. In this case the celebrated Blowup Lemma of Komlós, Sárközy and Szemerédi [
54]
can be used to show the existence of
$H$
factors. In order to formulate the Blowup Lemma we need to introduce the notion of a superregular pair. Given
$\epsilon >0$
and
$0<p<1$
, a bipartite graph
$G$
with bipartition
$({V}_{1},{V}_{2})$
,
$\left{V}_{1}\right=\left{V}_{2}\right=n$
, is called super
$(p,\epsilon )$
regular if

1.
For all vertices
$v\in V\left(G\right)$
,
$$(p\epsilon )n\le d\left(v\right)\le (p+\epsilon )n;$$

2.
For every pair of sets
$(U,W)$
,
$U\subset {V}_{1}$
,
$W\subset {V}_{2}$
,
$\leftU\right,\leftW\right\ge \epsilon n$
,
$$\left\frac{e(U,W)}{\leftU\right\leftW\right}\frac{\leftE\right(G\left)\right}{{n}^{2}}\right\le \epsilon .$$
Theorem 4.14
[
54]
For every choice of integers
$r$
and
$\Delta $
and a real
$0<p<1$
there exist an
$\epsilon >0$
and an integer
${n}_{0}\left(\epsilon \right)$
such that the following is true. Consider an
$r$
partite graph
$G$
with all partition sets
${V}_{1},\dots ,{V}_{r}$
of order
$n>{n}_{0}$
and all
$\left(\genfrac{}{}{0ex}{}{r}{2}\right)$
bipartite subgraphs
$G[{V}_{i},{V}_{j}]$
super
$(p,\epsilon )$
regular. Then for every
$r$
partite graph
$H$
with maximum degree
$\Delta \left(H\right)\le \Delta $
and all partition sets
${X}_{1},\dots ,{X}_{r}$
of order
$n$
, there exists an embedding
$f$
of
$H$
into
$G$
with each set
${X}_{i}$
mapped onto
${V}_{i}$
,
$i=1,\dots ,r$
.
(The above version of the Blowup Lemma, due to Rödl and Ruciński [71] , is somewhat differentfrom and yet equivalent to the original formulation of Komlós et al. We use it here as it is somewhat closer in spirit to the notion of pseudorandomness).
The Blowup Lemma is a very powerful embedding tool. Combined with another ”big cannon”, the Szemerédi Regularity Lemma, it can be used to obtain approximate versions of many of the most famous embedding conjectures. We suggest the reader to consult a survey of Komlós [
53]
for more details and discussions.
It is easy to show that if
$G$
is an
$(n,d,\lambda )$
graph with
$d=\Theta \left(n\right)$
and
$\lambda =o\left(n\right)$
, and
$h$
divides
$n$
, then a random partition of
$V\left(G\right)$
into
$h$
equal parts
${V}_{1},\dots ,{V}_{h}$
produces almost surely
$\left(\genfrac{}{}{0ex}{}{h}{2}\right)$
super
$(d/n,\epsilon )$
regular pairs. Thus the Blowup Lemma can be applied to the obtained
$h$
partite subgraph of
$G$
and we get:
Corollary 4.15
Let
$G$
be an
$(n,d,\lambda )$
graph with
$d=\Theta \left(n\right)$
,
$\lambda =o\left(n\right)$
. If
$h$
divides
$n$
, then
$G$
contains an
$H$
factor, for every fixed graph
$H$
on
$h$
vertices.
The case of a vanishing edge density
$p=o\left(1\right)$
is as usual significantly more complicated. Here a sufficient condition for the existence of an
$H$
factor should depend heavily on the graph
$H$
, as there may exist quite dense pseudorandom graphs without a single copy of
$H$
, see, for example, the Alon graph (Example 9 of Section 3 ). When
$H={K}_{2}$
, already a very weak pseudorandomness condition suffices to guarantee an
$H$
factor, or a perfect matching, as provided by Theorem 4.3 . We thus consider the case
$H={K}_{3}$
, the task here is to guarantee a triangle factor, i.e. a collection of
$n/3$
vertex disjoint triangles. This problem has been treated by Krivelevich, Sudakov and Szabó [
59]
who obtained the following result:
For best pseudorandom graphs with
$\lambda =\Theta \left(\sqrt{d}\right)$
the condition of the above theorem is fulfilled when
$d\gg {n}^{4/5}{log}^{2/5}n$
.
To prove Theorem
4.16 Krivelevich et al. first partition the vertex set
$V\left(G\right)$
into three parts
${V}_{1},{V}_{2},{V}_{3}$
of equal cardinality at random. Then they choose a perfect matching
$M$
between
${V}_{1}$
an
${V}_{2}$
at random and form an auxiliary bipartite graph
$\Gamma $
whose parts are
$M$
and
${V}_{3}$
, and whose edges are formed by connecting
$e\in M$
and
$v\in {V}_{3}$
if both endpoints of
$e$
are connected by edges to
$v$
in
$G$
. The existence of a perfect matching in
$\Gamma $
is equivalent to the existence of a triangle factor in
$G$
.
The authors of [