%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% LaTeX2e file for the paper                                         %
%                                                                    %
% Szemer\'edi's regularity lemma and quasi-randomness                %
%                                                                    %
% by Y. Kohayakawa and V. R\"odl                                     %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Thursday 08 Mar 2001 07:09:15pm BRST yoshi@jaca>   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[reqno]{amsart}

\usepackage[colorlinks,backref]{hyperref}

\setcounter{tocdepth}{3}

\def\({\left(}
\def\){\right)}  
\def\<{\left\langle}
\def\>{\right\rangle}

\def\llfloor{\left\lfloor}
\def\rrfloor{\right\rfloor}
\def\llceil{\left\lceil}
\def\rrceil{\right\rceil}

\let\epsilon=\varepsilon
\let\rho=\varrho
\let\:=\colon
\let\deg=d

\def\bfA{{\bf A}}
\def\bfw{{\bf w}}
\def\bfv{{\bf v}}
\def\bfu{{\bf u}}
\def\bfx{{\bf x}}
\def\bfy{{\bf y}}
\def\bfone{{\bf 1}}

\def\tB{{\widetilde B}}

\def\RR{{\mathbb R}}
\def\cA{{\mathcal A}}
\def\cB{{\mathcal B}}
\def\cG{{\mathcal G}}
\def\cP{{\mathcal P}}
\def\cPw{{\mathcal P}_{\rm w}}
\def\cR{{\mathcal R}}
\def\cU{{\mathcal U}}

%\def\yk#1{\textrm{[\textit{yk}: \textsf{#1}]}}
\def\ykcomm#1{\marginpar{\footnotesize#1}}
\def\dHp{d_{H,p}}
\def\dG{d_G}
\let\symmdiff=\bigtriangleup
\let\sdiff=\symmdiff
\let\vartriangle=\sdiff
\newcommand{\dHr}{d_{H,\rho}}
\newcommand{\PJsdiff}{P_{J,\symmdiff}}
%\newcommand{\Ave}{\mathop\protect{\rm Ave}\limits}
%\def\tPi{{\widetilde\Pi}}
\def\tP{{\widetilde P}}
\def\Forb{{\mathop{\rm Forb}\nolimits}}
\def\Forbind{\Forb_{\rm ind}}


%
% macros.tex
%
\def\dHG{d_{H,G}}
\def\eG{e_G}
\def\eH{e_H}
\def\dstS{d^*_{s,t}}
\let\epsilon=\varepsilon
\def\ind{\mathop{\rm ind}\nolimits}
\def\disc{\mathop{\rm disc}\nolimits}
\def\G{{\mathcal G}}
%
\def\indarrow{{\displaystyle
  \mathrel{\mathop{\longrightarrow}\limits^{\hbox{\tiny ind}}}}}
%
\let\deffont=\it
%
\makeatletter
\def\cases#1{\left\{\,\vcenter{\normalbaselines\m@th
    \ialign{$##\hfil$&\quad##\hfil\crcr#1\crcr}}\right.}
\makeatother
%
\def\endassertion{\egroup\par\ifdim\lastskip<\smallskipamount
                \removelastskip\penalty-20\smallskip\fi}
\def\assertion#1{\smallbreak\noindent
  \textrm{#1}\enspace\ignorespaces\bgroup\sl}
%
\newcommand{\Ave}{\mathop\protect{\rm Ave}}
\newcommand{\SkU}{S_k^U}
\newcommand{\sumijU}{\sum\nolimits_{ij\in J}^U}
\newcommand{\SkUW}{S_k^{(U,W)}}
\newcommand{\sumijUW}{\sum\nolimits_{ij\in H}^{(U,W)}}

\newtheorem{theorem}          {Theorem}       %[section]
\newtheorem{claim}      [theorem] {Claim}         %[section]
\newtheorem{lemma}      [theorem] {Lemma}         %[section]
\newtheorem{corollary}  [theorem] {Corollary}     %[section]
\newtheorem{fact}       [theorem] {Fact}          %[section]
\newtheorem{conjecture} [theorem] {Conjecture}    %[section]
%\newtheorem{problem}    [theorem] {Problem}       %[section]

\newtheoremstyle{note}% name
  {4pt}%      Space above
  {4pt}%      Space below
  {\sl}%      Body font
  {}%         Indent amount (empty = no indent, \parindent = para indent)
  {\itshape}% Thm head font
  {.}%        Punctuation after thm head
  {.5em}%     Space after thm head: " " = normal interword space;
        %       \newline = linebreak
  {}%         Thm head spec (can be left empty, meaning `normal')

\theoremstyle{note}
\newtheorem{remark}             {Remark}       
\newtheorem{example}   [theorem] {Example}       
\newtheorem{note}      [theorem] {Note}       
\newtheorem{definition}[theorem] {Definition}       
\newtheorem{case}               {Case}       

\newtheoremstyle{NBs}% name
  {4pt}%      Space above
  {4pt}%      Space below
  {\rm}%      Body font
  {}%         Indent amount (empty = no indent, \parindent = para indent)
  {\itshape}% Thm head font
  {.}%        Punctuation after thm head
  {.5em}%     Space after thm head: " " = normal interword space;
        %       \newline = linebreak
  {}%         Thm head spec (can be left empty, meaning `normal')

\theoremstyle{NBs}
\newtheorem{Remark}    [theorem] {Remark}       

\newtheoremstyle{Problems}% name
  {4pt}%      Space above
  {4pt}%      Space below
  {\it}%      Body font
  {}%         Indent amount (empty = no indent, \parindent = para indent)
  {\sc}%      Thm head font
  {.}%        Punctuation after thm head
  {.5em}%     Space after thm head: " " = normal interword space;
        %       \newline = linebreak
  {}%         Thm head spec (can be left empty, meaning `normal')

\theoremstyle{Problems}
\newtheorem{problem}    [theorem] {Problem}       %[section]

\begin{document}
\title[Regularity and quasi-randomness]%
{Szemer\'edi's regularity lemma and quasi-randomness}
\author{Y.~Kohayakawa}
\address{Instituto de Matem\'atica e Estat\'\i stica, Universidade de S\~ao
  Paulo, Rua do Mat\~ao 1010, 05508--900 S\~ao Paulo, Brazil}
\email{yoshi@ime.usp.br}
\author{V.~R\"odl}
\address{Department of Mathematics and Computer Science, Emory University,
  Atlanta, GA 30322, USA}
\email{rodl@mathcs.emory.edu}
\thanks{The first author was partially supported by MCT/CNPq through ProNEx
  Programme (Proc.\ CNPq 664107/1997--4), by CNPq (Proc.~300334/93--1
  and~468516/2000--0), and by FAPESP (Proj.~96/04505--2).  The second author
  was partially supported by NSF Grant~0071261. The collaboration between
  the authors is supported by a CNPq/NSF cooperative grant.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\date{Preliminary manuscript.  Copy produced on \today}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{abstract}
  The first half of this paper is mainly expository, and aims at introducing
  the regularity lemma of Szemer\'edi.  Among others, we discuss an early
  application of the regularity lemma that relates the notions of
  \textit{universality} and \textit{uniform distribution of edges}, a form of
  `pseudorandomness' or `quasi-randomness'.  We then state two closely related
  variants of the regularity lemma for sparse graphs and present a proof for
  one of them.
  
  In the second half of the paper, we discuss a basic idea underlying the
  algorithmic version of the original regularity lemma: we discuss a `local'
  condition on graphs that turns out to be, roughly speaking, equivalent to
  the regularity condition of Szemer\'edi.  Finally, we show how the sparse
  version of the regularity lemma may be used to prove the equivalence of a
  related, local condition for regularity.  This new condition turns out to
  give a~$O(n^2)$ time algorithm for testing the quasi-randomness of an
  $n$-vertex graph.
\end{abstract}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\maketitle
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\thispagestyle{empty}
\bgroup
\vspace{-1truecm}
\footnotesize
\tableofcontents
\egroup

\section{Introduction}
\label{sec:intro}

A beautiful result of Szemer\'edi on the asymptotic structure of graphs is his
regularity lemma.  Roughly speaking, this result tells us that \textit{any}
large graph may be written as a union of induced, random looking bipartite
graphs.  There are many applications of this result---the reader is urged to
consult the excellent survey of Koml\'os and
Simonovits~\cite{KomlosSimonovits96} for a thorough discussion on this
fundamental result.

The original regularity lemma is best suited for attacking problems involving
`dense' graphs, that is, $n$-vertex graphs with~$\geq cn^2$ edges for some
constant~$c>0$.  In the case of `sparse graphs', that is, $n$-vertex graphs
with~$o(n^2)$ edges, one has to adapt the definitions to take into account the
vanishing density of the graphs in question.  It turns out that regularity
lemmas for certain classes of such sparse graphs may be proved easily.  More
importantly, such results turned out to be quite important in dealing with
certain extremal and Ramsey type problems involving subgraphs of random
graphs.  The interested reader is referred to~\cite{Kohayakawa97Szemeredi}.

One of our aims in this paper is to focus on a circle of ideas that concern
`local' characterizations of regularity, which we believe should be better
known.  One tool that will be required is the regularity lemma for sparse
graphs.  Since we would also like this paper to be useful as an introduction
to the regularity lemma, we include some expository sections.

The contents of this paper fall naturally into four parts.  We start by
presenting the basic concepts and the statement of the regularity lemma in
Section~\ref{sec:prelim-defns_and_original}.  In
Sections~\ref{sec:first-version} and~\ref{sec:variants}, we state two variants
of the regularity lemma for sparse graphs.

If the reader is not too familiar with the regularity lemma, we suggest
skipping Sections~\ref{sec:first-version} and~\ref{sec:variants} at first, and
advancing directly to the second part of this paper,
Section~\ref{sec:universality}, where we discuss in detail an application of
the regularity lemma in its original form.  The result we prove in
Section~\ref{sec:universality}, which closely follows parts of~\cite{rodl86},
shows that if the edges of a graph are `uniformly distributed', then the graph
must have a rich subgraph structure.  This result,
Theorem~\ref{thm:universality1}, will be used to confirm a conjecture of Erd\H
os and we shall also mention a classical result in Ramsey theory that may be
deduced easily from this result.  We believe that
Theorem~\ref{thm:universality1} also illustrates the importance of the notion
of `quasi-randomness', addressed later in Section~\ref{sec:checking}.  The
proof of Theorem~\ref{thm:universality1} also illustrates a typical
application of the regularity lemma.  We hope that the uninitiated readers who
are interested in regularity will study this proof in detail.

In Section~\ref{sec:further_appls} we mention some other applications of the
regularity lemma that have emerged more recently.  Our choice of topics for
Section~\ref{sec:further_appls} has to do in part with the ideas and
techniques that appear in Section~\ref{sec:universality} and some natural
questions that they suggest.  One application we discuss has an algorithmic
flavour (see Section~\ref{sec:property_testing}).  In the following section,
Section~\ref{sec:construction}, we prove the version of the regularity lemma
for sparse graphs given in Section~\ref{sec:first-version}.

In the third part of this paper, Section~\ref{sec:local}, we discuss a key
fact that states that a certain local property of bipartite graphs is, roughly
speaking, equivalent to the property of being regular in the sense of
Szemer\'edi.  This fact was the key tool for the development of the
algorithmic version of the regularity lemma.

In the final part of this paper, Section~\ref{sec:checking}, we discuss a new
quasi-random graph property, by which we mean, following Chung, Graham, and
Wilson~\cite{chung89}, a property that belongs to a certain rather large and
disparate collection of equivalent graph properties, shared by almost all
graphs.  To prove that our property is a quasi-random property in the sense
of~\cite{chung89}, we shall make use of the sparse regularity lemma.

A few remarks are in order.  To focus on the main point in
Section~\ref{sec:local}, we carry out our discussion on the local condition
for regularity restricting ourselves to the very basic case, namely, the case
of $n$~by~$n$ bipartite graphs with edge density~$1/2$.  In fact, for the sake
of convenience, instead of talking about bipartite graphs, we shall consider
$n$~by~$n$ matrices whose entries are are~$+1$s and~$-1$s (and whose density
of~$+1$s will turn out to be~$\sim1/2$).  We shall see that if the rows of a
$\{\pm1\}$-matrix are pairwise orthogonal, then the matrix has small
\textit{discrepancy}, which may be thought of as an indication that our matrix
is `random looking'.  The reader may find a fuller discussion of this in
Frankl, R\"odl, and Wilson~\cite{frankl88:_hadam}.

The relevance of the ideas in Section~\ref{sec:local} may be illustrated by
the fact that several authors have made use of them, in some form, in
different contexts;
see~\cite{%
alon85:_expan,%
alon86:_eigen_ramsey,%
AlonDLRY92,%  
alon94,%
babai86:_compl,%
chung89,%
DukeLefmannRodlcount,%
thomason87,%
thomason87:_random%,%
} and the proof of the upper bound in Theorem~15.2 in~\cite{erd74:_probab},
due to J.$\,$H.~Lindsey.  We believe that these ideas should be carried over
to the sparse case in some way as well, since this may prove to be quite
fruitful; the interested reader is referred
to~\cite{kohayakawa00:_regul_i,kohayakawa00:_regul_ii} and to Alon, Capalbo,
Kohayakawa, R\"odl, Ruci\'nski, and Szemer\'edi~\cite{alon00:_univer}.

We hope that our discussion in Section~\ref{sec:local} will naturally lead the
reader to the results in the final part of the paper, namely, the results
concerning our quasi-random graph property.  Indeed,
Sections~\ref{sec:lindsey} and~\ref{sec:converse}, which capture the essence
of our discussion in Section~\ref{sec:local}, are quite gentle and we hope
that the reader will find them useful as a preparation for the technically
more involved Section~\ref{sec:checking}.  Before we close the introduction,
we mention that our quasi-random property allows one to check whether an
$n$-vertex graph is quasi-random in time~$O(n^2)$.  The fastest algorithms so
far had time complexity~$O(M(n))=O(n^{2.376})$, where~$M(n)$ denotes the time
needed to square a $\{0,1\}$-matrix over the
integers~\cite{coppersmith90:_matrix}.  Furthermore, in a forthcoming paper
with Thoma~\cite{kohayakawa00:_optimal_SzRL}, we shall present how this
quasi-random property may be used to develop a deterministic~$O(n^2)$ time
algorithm for the regularity lemma, improving on the result of Alon, Duke,
Lefmann, R\"odl, and Yuster~\cite{AlonDLRY92,alon94}.  The reader is referred
to~\cite{kohayakawa00:_algor} for a discussion on the algorithmic aspects of
regularity.

\subsection{Remarks on notation and terminology}
\label{sec:notation}
If~$\delta>0$, we write~$A\sim_\delta B$ to mean that
\begin{equation}
  \label{eq:def_sim_delta}
  {1\over1+\delta}B\leq A\leq(1+\delta)B.
\end{equation}
We shall use the following non-standard notation: we shall write~$O_1(x)$ for
any term~$y$ that satisfies~$|y|\leq x$.  Clearly, if~$A\sim_\delta B$,
then~$A=(1+O_1(\delta))B$.

Given an integer~$n$, we write~$[n]$ for the set~$\{1,\dots,n\}$.  If~$X$ is a
set and~$k$ is an integer, we write~${X\choose k}$ for the set of all
$k$-element subset of~$X$.  We write~$X\symmdiff Y$ for the symmetric
difference~$(X\setminus Y)\cup(Y\setminus X)$ of the sets~$X$ and~$Y$.

We usually write~$G^n$ for a graph on~$n$ vertices.  We denote the complete
graph on~$k$ vertices by~$K^k$.  We usually write~$e(G)$ for the number of
edges in the graph~$G$.  We denote the set of neighbours of a vertex~$x$ in a
graph~$G$ by~$\Gamma(x)=\Gamma_G(x)$.  If~$G$ is a graph and~$\{u,w\}\in
E(G)\subset{V(G)\choose2}$ is an edge of~$G$, we often write~$uw$ and~$wu$ for
this edge~$\{u,w\}$.  Sometimes we write~$B=(U,W;E)$ for a bipartite graph~$B$
with a fixed bipartition~$V(B)=U\cup W$, where~$E=E(B)$.

As customary, if~$G=(V,E)$ and~$H=(U,F)$ are graphs with~$U\subset V$
and~$F\subset E$, then we say that~$H$ is a \textit{subgraph} of~$G$, and we
write~$H\subset G$.  Moreover, if~$U=V$, then we say that~$H$ is a
\textit{spanning} subgraph of~$G$.  If~$W\subset V$, then the subgraph of~$G$
\textit{induced} by~$W$ in~$G$ is the subgraph
\begin{equation}
  \label{eq:induced_subgraph}
  \(W,E\cap{W\choose2}\),
\end{equation}
usually denoted by~$G[W]$.  A subgraph~$H$ of~$G$ is an \textit{induced
  subgraph} if~$H=G[V(H)]$, that is, every edge of~$G$ that has both its
endpoints in the vertex set~$V(H)$ of~$H$ is necessarily an edge of~$H$ as
well.

\subsection*{Acknowledgement}
\label{acknowledgement}
The authors are very grateful to the editors of this volume for their extreme
patience.

\section{The regularity lemma}
\label{sec:prelims}

Our aim in this section is to present the original regularity lemma of
Szemer\'edi and two closely related versions of the regularity lemma for
sparse graphs.  

\subsection{Preliminary definitions and the regularity lemma}
\label{sec:prelim-defns_and_original}
Let a graph $G=G^n$ of order~$|V(G)|=n$ be fixed.  For~$U$, $W\subset V=V(G)$, we
write $E(U,W)=E_G(U,W)$ for the set of edges of~$G$ that have one endvertex
in~$U$ and the other in~$W$.  We set~$e(U,W)=\eG(U,W)=|E(U,W)|$.  The rather
natural concept of \textit{density}~$d(U,W)=\dG(U,W)$ of a pair~$(U,W)$ in~$G$
is defined as follows: for any two disjoint non-empty sets~$U$, $W\subset V$,
we let
\begin{equation}
  \label{eq:def_Szemeredi_density}
  \dG(U,W)={e_G(U,W)\over|U||W|}.
\end{equation}
Szemer\'edi's regularity lemma asserts the existence of partitions of graphs
into a bounded number of remarkably `uniform' pieces, known as
\textit{$\epsilon$-regular pairs}.  

\begin{definition}[$\epsilon$-regular pair]
  \label{def:regular-pair}
  Let~$0<\epsilon\leq1$ be a real number.  Suppose~$G$ is a graph and~$U$
  and~$W\subset V=V(G)$ are two disjoint, non-empty sets of vertices of~$G$.
  We say that the pair~$(U,W)$ is \textit{$(\epsilon,G)$-regular}, or simply
  \textit{$\epsilon$-regular}, if we have
  \begin{equation}
    \label{eq:def_regular_pair}
    |\dG(U',W')-\dG(U,W)|\leq\epsilon
  \end{equation}
  for all~$U'\subset U$ and~$W'\subset W$ with
  \begin{equation}
    \label{eq:def_size_of_witness}
    |U'|\geq\epsilon|U|
    \quad\text{and}\quad
    |W'|\geq\epsilon|W|.
  \end{equation}
\end{definition}

If a pair~$(U,W)$ \textit{fails} to be $\epsilon$-regular, then a
pair~$(U',W')$ that certifies this fact is called a \textit{witness} for the
$\epsilon$-irregularity of~$(U,W)$.  Thus, if~$(U',W')$ is such a witness,
then~\eqref{eq:def_size_of_witness} holds but~\eqref{eq:def_regular_pair}
fails.

In the regularity lemma, the vertex set of the graphs will be partitioned into
a bounded number of blocks, basically all of the same size.  

\begin{definition}[$(\epsilon,k)$-equitable partition]
  \label{def:equitable_partition}
  Given a graph~$G$, a real number~$0<\epsilon\leq1$, and an integer~$k\geq1$,
  we say that a partition~$Q=(C_i)_0^k$ of~$V=V(G)$ is
  \textit{$(\epsilon,k)$-equitable} if we have
  \begin{enumerate}
  \item[\textrm{(\textit{i})}]$|C_0|\leq\epsilon n$,
  \item[\textrm{{(\textit{ii})}}]$|C_1|=\ldots=|C_k|$.  
  \end{enumerate}
  The class~$C_0$ is referred to as the \textit{exceptional} class of~$Q$.
\end{definition}

When the value of~$\epsilon$ is not relevant, we refer to an
$(\epsilon,k)$-equitable partition as a \textit{$k$-equitable} partition.
Similarly, $Q$~is an \textit{equitable} partition of~$V$ if it is a
$k$-equitable partition for some~$k$.  We may now introduce the key notion of
$\epsilon$-regular \textit{partitions} for the graph~$G$.

\begin{definition}[$\epsilon$-regular partition]
  \label{def:regular_partition}
  Given a graph~$G$, we say that an $(\epsilon,k)$-equitable
  partition~$Q=(C_i)_0^k$ of~$V=V(G)$ is \textit{$(\epsilon,G)$-regular}, or
  simply \textit{$\epsilon$-regular}, if at most~$\epsilon{k\choose2}$
  pairs~$(C_i,C_j)$ with~$1\leq i<j\leq k$ are not $\epsilon$-regular.
\end{definition}

We may now state the celebrated lemma of Szemer\'edi~\cite{szemeredi76}. 

\begin{theorem}[The regularity lemma]
  \label{thm:Original}
  For any given $\epsilon>0$ and~$k_0\geq1$, there are constants
  $K_0=K_0(\epsilon,k_0)\geq k_0$ and~$N_0=N_0(\epsilon,k_0)$ such that any
  graph~$G=G^n$ with~$n\geq N_0$ vertices admits an $(\epsilon,G)$-regular,
  $(\epsilon,k)$-equitable partition of its vertex set with $k_0\leq k\leq
  K_0$.
\end{theorem}

We shall not prove Theorem~\ref{thm:Original} here.  However, a proof of a
generalization of this result will be presented in detail later (see
Section~\ref{sec:construction}).

\subsubsection{Some remarks on Theorem~\ref{thm:Original}}
\label{sec:remarks_on_formulation}
Before we proceed, we make a few quite simple remarks on the concept of
regularity and on the formulation of Theorem~\ref{thm:Original}.  The remarks
below are primarily intended for the readers with little familiarity with the
regularity lemma.

\begin{Remark}
  \label{rem:a.a._are_regular}
  Let~$B=(U,W;E)$ be a bipartite graph with vertex classes~$U$ and~$W$ and
  edge set~$E$.  Suppose~$|U|=|W|=m$ and, say, $|E|=\llfloor m^2/2\rrfloor$.
  Is such a graph typically $\epsilon$-regular?  I.e., is the pair~$(U,W)$
  typically $\epsilon$-regular?  It turns out that this is indeed the case.

  \begin{fact}
    \label{fact:a.a._are_regular}
    Let~$\cB(U,W;m,M)$ be the collection of all bipartite graphs~$B=(U,W;E)$
    on a fixed pair of sets~$U$ and~$W$ with~$|U|=|W|=m$ and~$|E|=M$.
    For~$0<\epsilon\leq1$, let~$\cR(U,W;m,M;\epsilon)\subset\cB(U,W;m,M)$ be
    the set of all $\epsilon$-regular bipartite graphs
    in~$\cB(U,W;m,M)$.  If~$0<\epsilon\leq1$ is a fixed constant and~$M(m)$ is
    such that, say,
    \begin{equation}
      \label{eq:good_M}
      \lim_{m\to\infty}M(m)/m^2=p,
    \end{equation}
    where~$0<p<1$, then
    \begin{equation}
      \label{eq:a.a._are_regular}
      \lim_{m\to\infty}{|\cR(U,W;m,M(m);\epsilon)|\over|\cB(U,W;m,M(m))|}=1. 
    \end{equation}
  \end{fact}
  
  The result above tells us that `almost all' (dense) bipartite graphs are
  $\epsilon$-regular.  Fact~\ref{fact:a.a._are_regular} follows easily from
  standard large deviation inequalities.  The reader is referred to, say,
  Chapter~7 of~\cite{Bollobas,bollobas98:_moder} (the well-known
  monographs~\cite{BBf,janson00:_random_graph} will also certainly do).
\end{Remark}

\begin{Remark}
  \label{rem:too_sparse_is_regular}
  Bipartite graphs that are very sparse are necessarily $\epsilon$-regular.
  We may make this observation precise as follows.
  Suppose~$B=(U,W;E)\in\cB(U,W;m,M)$, where~$d(U,W)=M/m^2\leq\epsilon^3$.
  Then~$B$ is automatically $\epsilon$-regular.  Indeed, a witness~$(U',W')$
  to the $\epsilon$-irregularity of~$(U,W)$ must be such that
  \begin{equation}
    \label{eq:too_sparse_is_regular}
    d(U',W')>d(U,W)+\epsilon\geq\epsilon.
  \end{equation}
  Therefore~$e(U,W)\geq e(U',W')\geq
  d(U',W')|U'||W'|>\epsilon|U'||W'|\geq\epsilon^3m^2$.  However, by
  assumption, $e(U,W)=M\leq\epsilon^3m^2$.  This contradiction shows that such
  a witness cannot exist.  Therefore~$B$ is indeed $\epsilon$-regular.
  
  It should be also clear that bipartite graphs that are very dense are also
  automatically $\epsilon$-regular.  The reader is invited to work out the
  details. 
\end{Remark}

\begin{Remark}
  \label{rem:Inside_edges}
  Suppose we have a graph~$G=G^n$.  Trivially, any $k$-equitable partition
  of~$V(G)$ with~$k=1$ is $\epsilon$-regular.  However, in an
  $\epsilon$-regular partition~$(C_i)_0^k$ for~$G$, we do not have any
  information about the edges incident to the exceptional class~$C_0$, nor do
  we have any information about the edges contained within the~$C_i$ ($1\leq
  i\leq k$).  Therefore the $1$-equitable partitions of~$G$ are of no
  interest.  The lower bound~$k_0$ in the statement of
  Theorem~\ref{thm:Original} may be used to rule out partitions into a small
  number of blocks.
  
  In fact, the number of edges within the~$C_i$ ($1\leq i\leq k$) in an
  $(\epsilon,k)$-equitable partition is at most~$k^{-1}{n\choose2}\leq
  k_0^{-1}{n\choose2}$, and the number of edges incident to~$C_0$ is at
  most~$\epsilon n^2$, since~$|C_0|\leq\epsilon n$.  Therefore, one usually
  chooses~$k_0$ and~$\epsilon$ so that
  \begin{equation}
    \label{eq:negligible}
    {1\over k_0}{n\choose2}+\epsilon n^2
  \end{equation}
  is a negligible number of edges for the particular application in question.
\end{Remark}

\begin{Remark}
  \label{rem:no_exceptional}
  Let~$G=G^n$ be a given graph.  Sometimes it is a little more convenient to
  consider regular partitions for~$G$ in which no exceptional class is
  allowed.  One may instead require that the partition~$(C_i)_1^k$ of~$V=V(G)$
  should be such that
  \begin{equation}
    \label{eq:nearly_equal}
    \llfloor n\over k\rrfloor\leq|C_1|
    \leq\dots\leq|C_k|\leq\llceil n\over k\rrceil, 
  \end{equation}
  and such that~$\geq(1-\epsilon){k\choose2}$ of the pairs~$(C_i,C_j)$ with
  $1\leq i< j\leq k$ are $\epsilon$-regular.  We leave it as an exercise to
  deduce this version of the regularity lemma from Theorem~\ref{thm:Original}.
\end{Remark}

\begin{Remark}
  \label{rem:no_N_0}
  Suppose we allow regular partitions as in Remark~\ref{rem:no_exceptional}
  above.  Then, as a side effect, we may omit the condition that the
  graph~$G=G^n$ should satisfy~$n\geq N_0(\epsilon,k_0)$.  Indeed, it suffices
  to use the fact that the partition of the vertex set of a graph into
  singletons is $\epsilon$-regular.  Indeed, let~$K_0=K_0(\epsilon,k_0)$ be
  the upper bound for the number of classes in the $\epsilon$-regular
  partitions with at least~$k_0$ parts, in the sense of
  Remark~\ref{rem:no_exceptional}, whose existence may be ensured, and
  suppose~$N_0=N_0(\epsilon,k_0)$ is such that any graph with~$n\geq N_0$
  vertices is guaranteed to admit such a partition.  Now
  let~$K_0'=\max\{K_0,N_0\}$, and observe that, then, \textit{any} graph
  admits an $\epsilon$-regular partition into~$k$ parts, where~$k_0\leq k\leq
  K_0'$.  Indeed, if the given graph~$G$ has fewer than~$N_0$ vertices, it
  suffices to consider the partition of~$V(G)$ into singletons.
\end{Remark}

For the sake of completeness, we explicitly state the conclusion of
Remarks~\ref{rem:no_exceptional} and~\ref{rem:no_N_0} as a theorem.  

\begin{theorem}\label{thm:Original2}
  For any given $\epsilon>0$ and~$k_0\geq1$, there is a constant
  $K_0=K_0(\epsilon,k_0)\geq k_0$ such that any graph~$G$ admits a
  partition~$(C_i)_1^k$ of its vertex set such that
  \begin{enumerate}
  \item[\textrm{(\textit{i})}] $k_0\leq k\leq K_0$, 
  \item[\textrm{(\textit{ii})}] $\llfloor n/k\rrfloor\leq|C_1|
    \leq\dots\leq|C_k|\leq\llceil n/k\rrceil$, and
  \item[\textrm{(\textit{iii})}] at least~$(1-\epsilon){k\choose2}$ of the
    pairs~$(C_i,C_j)$ with $1\leq i< j\leq k$ are $\epsilon$-regular.
  \end{enumerate}
\end{theorem}

\subsubsection{Irregular pairs and the number of blocks in regular partitions}
\label{sec:gowers}
The notion of an $\epsilon$-regular partition given in
Definition~\ref{def:regular_partition} gives us a little breathing room in
that it allows up to $\epsilon{k\choose2}$ irregular pairs~$(C_i,C_j)$ in a
$k$-equitable partition $\bigcup_{0\leq i\leq k}C_i$.  Whether this is
required is a rather natural question (already raised by
Szemer\'edi~\cite{szemeredi76}): is there a strengthening of the regularity
lemma that guarantees the existence of an $(\epsilon,k)$-equitable partition
with all the~${k\choose2}$ pairs $\epsilon$-regular for any large enough
graph?

As observed by several researchers, Lov\'asz, Seymour, Trotter, and the
authors of~\cite{alon94} among others (see~\cite[p.~82]{alon94}), the
irregular pairs \textit{are required}.  A simple example that shows this is as
follows: let~$B=(U,W;E)$ be the bipartite graph with~$U=W=[n]$, and~$ij\in E$
if and only if~$i\leq j$.  The reader is invited to prove that, for small
enough~$\epsilon>0$, any $(\epsilon,k)$-equitable, $\epsilon$-regular
partition of this graph requires at least~$ck$ $\epsilon$-irregular pairs,
where~$c=c(\epsilon)>0$ is some constant that depends only on~$\epsilon$.

Let us now turn to the value of the constants~$K_0=K_0(\epsilon,k_0)$
and~$N_0=N_0(\epsilon,k_0)$ in the statement of the regularity lemma,
Theorem~\ref{thm:Original}.  As we discussed in Remark~\ref{rem:no_N_0}, the
requirement that we should only deal with graphs~$G=G^n$ with~$n\geq N_0$ is
not important.  However, $K_0=K_0(\epsilon,k_0)$~is much more interesting.

The original proof of Theorem~\ref{thm:Original} gave for~$K_0$ a tower
of~$2$s of height proportional to~$\epsilon^{-5}$, which is quite a large
constant for any reasonable~$\epsilon$.  (How such a number comes about may be
seen very clearly in the proof of Theorem~\ref{thm:SSz}, given in
Section~\ref{sec:construction}.)  As proved by Gowers~\cite{gowers97:_lower},
there are graphs for which such a huge number of classes are required in any
$\epsilon$-regular partition.  We only give a weak form of the main result
in~\cite{gowers97:_lower} (see Theorem~15 in~\cite{gowers97:_lower}).

\begin{theorem}
  \label{thm:gowers_lwbd}
  There exist absolute constants~$\epsilon_0>0$ and~$c_0>0$ for which the
  following holds.  For any~$0<\epsilon\leq\epsilon_0$, there is a graph~$G$
  for which the number of classes in any $\epsilon$-regular partition of its
  vertex set must be at least as large as a tower of~$2$s of height at
  least~$c_0\epsilon^{-1/16}$.
\end{theorem}

Roughly speaking, the strongest result in~\cite{gowers97:_lower} states that
one may weaken the requirements on the $\epsilon$-regular partition in certain
natural ways and still have the same lower bound as in
Theorem~\ref{thm:gowers_lwbd}.  The interested reader should study the
ingenious probabilistic constructions in~\cite{gowers97:_lower}.

Before we proceed, let us mention again that the readers who are not too
familiar with the regularity lemma may at first prefer to skip the next two
sections, namely, Sections~\ref{sec:first-version} and~\ref{sec:variants}, and
proceed directly to Section~\ref{sec:universality}, where a typical
application of Theorem~\ref{thm:Original} is discussed in detail.

\subsection{A regularity lemma for sparse graphs}
\label{sec:first-version}
We shall now state a version of the regularity lemma for sparse graphs.  We in
fact consider a slightly more general situation, including the case of
$\ell$-partite graphs~$G$, where~$\ell$ is some fixed integer.

Let a partition~$P_0=(V_i)_1^\ell$ ($\ell\geq1$) of~$V=V(G)$ be fixed.  For
convenience, let us write~$(U,W)\prec P_0$ if~$U\cap W=\emptyset$ and
either~$\ell=1$ or else~$\ell\geq2$ and for some~$i\neq j$ ($1\leq
i,\,j\leq\ell$) we have~$U\subset V_i$, $W\subset V_j$.

Suppose~$0<\eta\leq1$.  We say that~$G$ is \textit{$(P_0,\eta)$-uniform}
if, for some~$0<p\leq1$, we have that for all~$U$, $W\subset V$
with~$(U,W)\prec P_0$ and~$|U|$, $|W|\geq\eta n$, we have
\begin{equation}
  \label{eq:Unif}
  \big|\eG(U,W)-p|U||W|\big|\leq\eta p|U||W|.
\end{equation}
As mentioned above, the partition~$P_0$ is introduced to handle the case of
$\ell$-partite graphs ($\ell\geq2$).  If~$\ell=1$, that is, if the
partition~$P_0$ is trivial, then we are thinking of the case of ordinary
graphs.  In this case, we shorten the term $(P_0,\eta)$-uniform to
\textit{$\eta$-uniform}.

The prime example of an $\eta$-uniform graph is of course a \textit{random
  graph}~$G_p=G_{n,p}$.  For any~$\eta>0$ a random graph~$G_p$
with~$p=p(n)=C/n$ is almost surely $\eta$-uniform provided~$C\geq
C_0=C_0(\eta)$, where~$C_0(\eta)$ depends only on~$\eta$.  Let~$0<p=p(n)\leq1$
be given.  The standard binomial random graph~$G_p=G_{n,p}$ has as vertex set
a fixed set~$V(G_p)$ of cardinality~$n$ and two such vertices are adjacent
in~$G_p$ with probability~$p$, with all such adjacencies independent.  For
concepts and results concerning random graphs, see, e.g.,
Bollob\'as~\cite{BBf} or Janson, \L uczak, and
Ruci\'nski~\cite{janson00:_random_graph}.  (A lighter introduction may be
Chapter~7 of Bollob\'as~\cite{Bollobas,bollobas98:_moder}.)

We still need to introduce a few further definitions.  Let a graph~$G=G^n$ be
fixed as before.  Let~$H\subset G$ be a spanning subgraph of~$G$.  For~$U$,
$W\subset V$, let
$$
\dHG(U,W)=\cases{\eH(U,W)/\eG(U,W)  &if~$\eG(U,W)>0$ \cr
                 0                  &if~$\eG(U,W)=0$. \cr
                }
$$
Suppose~$\epsilon>0$, $U$, $W\subset V$, and~$U\cap W=\emptyset$. We
say that the pair~$(U,W)$ is \textit{$(\epsilon,H,G)$-regular}, or
simply \textit{$\epsilon$-regular}, if for all~$U'\subset U$, $W'\subset
W$ with~$|U'|\geq\epsilon|U|$ and~$|W'|\geq\epsilon|W|$, we have
$$
|\dHG(U',W')-\dHG(U,W)|\leq\epsilon.
$$

If~$P$ and~$Q$ are two equitable partitions of~$V$ (see
Definition~\ref{def:equitable_partition} in
Section~\ref{sec:prelim-defns_and_original}), we say that~$Q$
\textit{refines}~$P$ if every non-exceptional class of~$Q$ is contained in
some non-exceptional class of~$P$.  If~$P'$ is an arbitrary partition of~$V$,
then~$Q$ \textit{refines}~$P'$ if every non-exceptional class of~$Q$ is
contained in some block of~$P'$.  Finally, we say that an
$(\epsilon,k)$-equitable partition~$Q=(C_i)_0^k$ of~$V$ is
\textit{$(\epsilon,H,G)$-regular}, or simply \textit{$\epsilon$-regular}, if
at most~$\epsilon{k\choose2}$ pairs~$(C_i,C_j)$ with~$1\leq i<j\leq k$ are not
$\epsilon$-regular.  We may now state an extension of Szemer\'edi's lemma to
subgraphs of $(P_0,\eta)$-uniform graphs.

\begin{theorem}\label{thm:SSz}
  Let $\epsilon>0$ and $k_0$, $\ell\geq1$ be fixed. Then there are constants
  $\eta=\eta(\epsilon,k_0,\ell)>0$, $K_0=K_0(\epsilon,k_0,\ell)\geq k_0$,
  and~$N_0=N_0(\epsilon,k_0,\ell)$ satisfying the following.  For any
  $(P_0,\eta)$-uniform graph $G=G^n$ with~$n\geq N_0$, where
  $P_0=(V_i)_1^\ell$ is a partition of $V=V(G)$, if $H\subset G$ is a spanning
  subgraph of $G$, then there exists an $(\epsilon,H,G)$-regular
  $(\epsilon,k)$-equitable partition of~$V$ refining~$P_0$ with $k_0\leq k\leq
  K_0$.
\end{theorem}

\begin{Remark}
  \label{rem:recover_original}
  To recover the original regularity lemma of Szemer\'edi from
  Theorem~\ref{thm:SSz}, simply take~$G=K^n$, the complete graph on~$n$
  vertices.
\end{Remark}

\subsection{A second regularity lemma for sparse graphs}
\label{sec:variants}
In some situations, the sparse graph~$H$ to which one would like to apply the
regularity lemma is not a subgraph of some fixed $\eta$-uniform graph~$G$.  A
simple variant of Theorem~\ref{thm:SSz} may be useful in this case.  For
simplicity, we shall not state this variant for `$P_0$-partite' graphs as we
did in Section~\ref{sec:first-version}.

Let a graph~$H=H^n$ of order~$|V(H)|=n$ be fixed.  Suppose~$0<\eta\leq1$,
$D\geq1$, and~$0<p\leq1$ are given.  We say that~$H$ is an
\textit{$(\eta,D)$-upper-uniform graph with respect to density~$p$} if, for
all~$U$, $W\subset V$ with~$U\cap W=\emptyset$ and~$|U|$, $|W|\geq\eta n$, we
have $e_H(U,W)\le Dp|U||W|$.  In what follows, for any two disjoint non-empty
sets~$U$, $W\subset V$, let the \textit{normalized $p$-density}~$\dHp(U,W)$
of~$(U,W)$ be
\begin{equation}
  \label{eq:def_p-density}
  \dHp(U,W)={e_H(U,W)\over p|U||W|}.
\end{equation}
Now suppose~$\epsilon>0$, $U$, $W\subset V$, and~$U\cap W=\emptyset$.
We say that the pair~$(U,W)$ is \textit{$(\epsilon,H,p)$-regular},
or simply \textit{$(\epsilon,p)$-regular}, if for all~$U'\subset
U$, $W'\subset W$ with~$|U'|\geq\epsilon|U|$ and~$|W'|\geq\epsilon|W|$
we have
$$
|\dHp(U',W')-\dHp(U,W)|\leq\epsilon.
$$

We say that an $(\epsilon,k)$-equitable partition~$P=(C_i)_{0}^k$ of~$V$ is
\textit{$(\epsilon,H,p)$-regular}, or simply \textit{$(\epsilon,p)$-regular},
if at most~$\epsilon{k\choose2}$ pairs~$(C_i,C_j)$ with~$1\leq i<j\leq k$ are
not $(\epsilon,p)$-regular.  We may now state a version of Szemer\'edi's
regularity lemma for $(\eta,D)$-upper-uniform graphs.

\begin{theorem}\label{thm:SSzp}
  For any given $\epsilon>0$, $k_0\geq1$, and~$D\geq1$, there are constants
  $\eta=\eta(\epsilon,k_0,D)>0$, $K_0=K_0(\epsilon,k_0,D)\geq k_0$,
  and~$N_0=N_0(\epsilon,k_0,D)$ such that any graph~$H=H^n$ with~$n\geq N_0$
  vertices that is $(\eta,D)$-upper-uniform with respect to density $0<p\leq1$
  admits an $(\epsilon,H,p)$-regular $(\epsilon,k)$-equitable partition of its
  vertex
  set with $k_0\leq k\leq K_0$.
\end{theorem}

\section{An application of the regularity lemma}
\label{sec:universality}
Here we present an application of the regularity lemma.  We believe that this
is a fairly illustrative example and we also hope that it will introduce the
notion of pseudorandomness in a natural way.  We follow certain parts
of~\cite{rodl86} closely.

\subsection{A simple fact about almost all graphs}
\label{sec:r.gs_obs}
We start with two definitions.  We shall say that a graph~$G$ is
\textit{$k$-universal} if~$G$ contains all graphs with $k$~vertices as induced
subgraphs.  As we shall see below, large graphs are typically $k$-universal
for any small~$k$.  Our second definition captures another property of typical
graphs, namely, the property that their edges are `uniformly distributed'.

\begin{definition}[Property~$\cR(\gamma,\delta,\sigma)$]
  \label{def:gamma_delta_sigma}
  We say that a graph~$G=G^n$ of order~$n$ has
  property~$\cR(\gamma,\delta,\sigma)$ if, for all~$S\subset V=V(G)$
  with~$|S|\geq\gamma n$, the number of edges~$e(S)=e(G[S])$ induced by~$S$
  in~$G$ satisfies
  \begin{equation}
    \label{eq:cU_property}
    e(S)=(\sigma+O_1(\delta)){|S|\choose2}.
  \end{equation}
\end{definition}

Let us write~$\cG(n,M)$ for the set of all graphs on the vertex
set~$[n]=\{1,\dots,n\}$ with~$M$ edges.  Clearly, we have
\begin{equation}
  \label{eq:no_elements_in_GnM}
  |\cG(n,M)|={{n\choose2}\choose M}
\end{equation}
for all integers~$n\geq0$ and~$0\leq M\leq{n\choose2}$.  Let~$\cU(n,M;k)$ be
the subset of~$\cG(n,M)$ of all the $k$-universal graphs, and
let~$\cR(n,M;\gamma,\delta,\sigma)$ be the subset of~$\cG(n,M)$ of all the
graphs~$G\in\cG(n,M)$ satisfying property~$\cR(\gamma,\delta,\sigma)$.

The following fact is easy to prove.

\begin{fact}
  \label{fact:2r.gs_facts}
  Let~$k\geq1$ be an integer and let~$0<\gamma\leq1$, $0<\delta\leq1$,
  and~$0<\sigma<1$ be real numbers.
  Put~$M=M(n)=\llfloor\sigma{n\choose2}\rrfloor$.  Then we have
  \begin{equation}
    \label{eq:r.gs_fact_i}
    \lim_{n\to\infty}{|\cU(n,M;k)|\over|\cG(n,M)|}=1
  \end{equation}
  and
  \begin{equation}
    \label{eq:r.gs_fact_ii}
    \lim_{n\to\infty}{|\cR(n,M;\gamma,\delta,\sigma)|\over|\cG(n,M)|}=1. 
  \end{equation}
\end{fact}

In the usual language of random graphs, one says that \textit{almost
  all}~$G\in\cG(n,M)$ are $k$-universal to mean that~\eqref{eq:r.gs_fact_i}
holds.  Similarly, one says that almost all~$G\in\cG(n,M)$
satisfy~$\cR(\gamma,\delta,\sigma)$ because of~\eqref{eq:r.gs_fact_ii}.
If~$\gamma$ and~$\delta$ are small, the latter assertion may be interpreted to
mean that the edges of a typical graph~$G\in\cG(n,M)$ are uniformly
distributed.

The most direct way to verify Fact~\ref{fact:2r.gs_facts} is by
proving~\eqref{eq:r.gs_fact_i} and~\eqref{eq:r.gs_fact_ii} independently.
However, it turns out that, for \textit{any deterministic graph}~$G=G^n$,
having property~$\cR(\gamma,\delta,\sigma)$ for any fixed~$0<\sigma<1$ implies
the $k$-universality of~$G$.  (Of course, the constants~$\gamma$ and~$\delta$
have to be suitably small with respect to~$k$, and~$n$ has to be suitably
large with respect to~$k$.)  Thus, roughly speaking, having uniformly
distributed edges is a \textit{stronger} property than being universal.
(Quite surprisingly, if one strengthens the notion of $k$-universality to
include information on the number of copies of all $k$-vertex graphs for
fixed~$k\geq4$, these properties become \textit{equivalent} in a certain
precise sense; see Section~\ref{sec:equivalence} for a short discussion on
this point.)

We shall prove that uniform distribution of edges implies universality by
making use of the regularity lemma.  We shall in fact prove a stronger
statement, and we shall see that this statement, coupled with an auxiliary
result, confirms a conjecture of Erd\H os.

\subsection{The statement of the results}
\label{sec:state_results}
Let us state the first result we discuss in this section.

\begin{theorem}
  \label{thm:universality1}
  For all integers~$k\geq1$ and real numbers~$0<\sigma<1$ and~$0<\delta<1$
  with~$\delta<\sigma<1-\delta$, there exist~$\gamma>0$ and~$N_0$ for which
  the following holds.  If~$G=G^n$ is a graph of order~$n\geq N_0$ that
  satisfies property $\cR(\gamma,\delta,\sigma)$, then~$G$ is $k$-universal.
\end{theorem}

We shall prove Theorem~\ref{thm:universality1} in
Section~\ref{sec:proof_of_universal}.  It may be worth mentioning that the
constant~$\delta$, which controls the `error' in~\eqref{eq:cU_property}, is
quantified \textit{universally} in Theorem~\ref{thm:universality1} (under the
obviously necessary condition that we should have~$\delta<\sigma<1-\delta$).
Thus, the result above tells us that, whatever the magnitude of the error, we
may ensure $k$-universality by requiring control over small enough sets.
Somewhat surprisingly, one may also prove a result in which it is the
quantity~$\gamma$ that is quantified universally, that is, we are told that we
have control over sets of some fixed cardinality, say~$\lfloor n/2\rfloor$,
and we would like to guarantee $k$-universality by requiring a tight enough
control over such sets.  We make this precise in the following result, proved
in~\cite{rodl86}.

\begin{theorem}
  \label{thm:universality2}
  For all integers~$k\geq1$ and real numbers~$0<\sigma<1$ and~$0<\gamma<1$,
  there exist~$\delta>0$ and~$N_1$ for which the following holds.  If~$G=G^n$
  is a graph of order~$n\geq N_1$ that satisfies property
  $\cR(\gamma,\delta,\sigma)$, then~$G$ is $k$-universal.
\end{theorem}

We shall not prove the above result here.  We only remark that the proof of
Theorem~\ref{thm:universality2} is based on the same tools that are used to
prove Theorem~\ref{thm:universality1}, but it is a little more delicate.
Theorem~\ref{thm:universality2} is closely related to the following result,
which was conjectured by Erd\H os (see~\cite{erdos79:_some}
or~\cite[Chapter~VI, p.~363]{BBegt}).

\begin{theorem}
  \label{conj:Erdos}
  For every integer~$k\geq1$ and real number~$0<\sigma<1$, there is
  an~$\epsilon>0$ for which the following holds.  Suppose a graph~$G=G^n$
  has~$M=\llfloor\sigma{n\choose2}\rrfloor$ edges, and for all~$W\subset
  V=V(G)$ with~$|W|=\lfloor n/2\rfloor$ we have
  \begin{equation}
    \label{eq:Erdos_conj}
    e(G[W])\geq\sigma{\lfloor n/2\rfloor\choose2}(1-\epsilon).
  \end{equation}
  Then, if~$n\geq n_0(k,\sigma)$, the graph~$G$ contains a~$K^k$.
\end{theorem}

We shall deduce Theorem~\ref{conj:Erdos} from Theorem~\ref{thm:universality1}
in Section~\ref{sec:proof_erdos} below.  Nikiforov~\cite{nikiforov99:_erdos_k}
recently proved Theorem~\ref{conj:Erdos} by making use of different
techniques.

\subsubsection{Proof of Theorem~\ref{conj:Erdos}}
\label{sec:proof_erdos}
Theorem~\ref{conj:Erdos} follows from Theorem~\ref{thm:universality1} and the
auxiliary claim below.

\begin{claim}
  \label{claim:jump}
  For all real numbers~$0<\gamma<1$, $0<\delta<1$, and~$0<\sigma<1$, there is
  an~$\epsilon>0$ for which the following holds.  Suppose a graph~$G=G^n$
  has~$M=\llfloor\sigma{n\choose2}\rrfloor$ edges, and for all~$W\subset
  V=V(G)$ with~$|W|=\lfloor n/2\rfloor$ inequality~\eqref{eq:Erdos_conj}
  holds.  Then, if~$n\geq n_1(\gamma,\delta,\sigma)$, the graph~$G$ is such
  that for all~$U\subset V=V(G)$ with~$|U|\geq\gamma n$ we have
  \begin{equation}
    \label{eq:jump_conclusion}
    e(G[U])\geq(\sigma-\delta){|U|\choose2}.
  \end{equation}
\end{claim}

Observe that the conclusion about~$G$ in Claim~\ref{claim:jump} above is very
close to property~$\cR(\gamma,\delta,\sigma)$.  Clearly, the difference is
that we do not have the upper bound in~\eqref{eq:cU_property} in
Definition~\ref{def:gamma_delta_sigma}, which is natural, given the one-sided
hypothesis about~$G$ in Claim~\ref{claim:jump}.  Let us now prove
Theorem~\ref{conj:Erdos} assuming Theorem~\ref{thm:universality1} and
Claim~\ref{claim:jump}.

\begin{proof}[Proof of Theorem~\ref{conj:Erdos}]
  Let~$k$ and~$\sigma$ as in the statement of Theorem~\ref{conj:Erdos} be
  given.  Put
  \begin{equation}
    \label{eq:delta_def}
    \delta={1\over2}\sigma,
  \end{equation}
  and let
  \begin{equation}
    \label{eq:primes_def}
    \sigma'={1\over2}\(\(1-{1\over k}\)+(\sigma-\delta)\)
    \quad\text{and}\quad
    \delta'={1\over2}\(\(1-{1\over k}\)-(\sigma-\delta)\).
  \end{equation}
  Clearly, we have
  \begin{equation}
    \label{eq:new_interval}
    0<\sigma'-\delta'=\sigma-\delta
    <\sigma'+\delta'=1-{1\over k}<1,
  \end{equation}
  and, in particular, $\delta'<\sigma'<1-\delta'$.  Hence, we may invoke
  Theorem~\ref{thm:universality1} with~$k$, $\sigma'$, and~$\delta'$.
  Theorem~\ref{thm:universality1} then gives us
  \begin{equation}
    \label{eq:gamma_N_0_def}
    \gamma=\gamma(k,\sigma',\delta')
    \quad\text{and}\quad
    N_0(k,\sigma',\delta').
  \end{equation}
  Let us now feed~$\gamma$, $\delta$, and~$\sigma$ into
  Claim~\ref{claim:jump}.  We obtain
  \begin{equation}
    \label{eq:epsilon_n_1_def}
    \epsilon=\epsilon(\gamma,\delta,\sigma)
    \quad\text{and}\quad
    n_1(\gamma,\delta,\sigma).
  \end{equation}
  Finally, let~$n_0(k)$ be such that any graph with~$n\geq n_0(k)$ vertices
  and~$>(1-1/k){n\choose2}$ edges must contain a~$K^k$.  Put
  \begin{equation}
    \label{eq:n_0_def}
    n_0=n_0(k,\sigma)
    =\max\left\{
      N_0(k,\sigma',\delta'),n_1(\gamma,\delta,\sigma),{1\over\gamma}n_0(k)
    \right\}.
  \end{equation}
  We claim that~$\epsilon$ given in~\eqref{eq:epsilon_n_1_def} and~$n_0$ given
  in~\eqref{eq:n_0_def} will do in Theorem~\ref{conj:Erdos}. 
  
  To verify this claim, suppose a graph~$G=G^n$ with~$n\geq n_0$ vertices
  has~$M=\llfloor\sigma{n\choose2}\rrfloor$ edges, and for all~$W\subset
  V=V(G)$ with~$|W|=\lfloor n/2\rfloor$ inequality~\eqref{eq:Erdos_conj}
  holds.  Then, by the choice of~$\epsilon$ and~$n_0\geq
  n_1(\gamma,\delta,\sigma)$ (see~\eqref{eq:epsilon_n_1_def}), we may deduce
  from Claim~\ref{claim:jump} that
  %
  \assertion{(\ddag)}for all~$U\subset V=V(G)$ with~$|U|\geq\gamma n$
  inequality~\eqref{eq:jump_conclusion} holds.
  \endassertion
  %
  Now, since~$n\geq n_0\geq\gamma^{-1}n_0(k)$, we know that if~$U\subset
  V=V(G)$ is such that~$|U|\geq\gamma n$ and
  \begin{equation}
    \label{eq:apply_Turan}
    e(G[U])>\(1-{1\over k}\){|U|\choose2},
  \end{equation}
  then~$G[U]\supset K^k$.  Therefore we may assume that
  %
  \assertion{(\ddag\ddag)}inequality~\eqref{eq:apply_Turan} fails for
  all~$U\subset V=V(G)$ with~$|U|\geq\gamma n$.
  \endassertion
  %
  Assertions~(\ddag) and~(\ddag\ddag) imply that
  property~$\cR(\gamma,\delta',\sigma')$ holds for~$G$
  (see~\eqref{eq:new_interval}).  By the choice of~$\gamma$ and~$n_0\geq
  N_0(k,\sigma',\delta')$ (see~\eqref{eq:gamma_N_0_def}), we may now deduce
  from Theorem~\ref{thm:universality1} that~$G$ is $k$-universal.  This
  completes the proof of Theorem~\ref{conj:Erdos}.
\end{proof}

We shall now turn to Claim~\ref{claim:jump}, but before we proceed, we state
the following basic fact.  Given a set of vertices~$W\subset V(G)$
with~$|W|\geq2$ in a graph~$G$, the \textit{edge density}~$d(W)$ of~$W$ is
defined to be~$e(G[W]){|W|\choose2}^{-1}$.

\begin{fact}
  \label{fact:ave_of_ave}
  Let~$G$ be a graph and suppose we are given~$W\subset V(G)$
  with~$|W|\geq2$.  Suppose also that~$2\leq u\leq|W|$ is fixed.  Then 
  \begin{equation}
    \label{eq:ave_of_ave}
    d(W)=\Ave_Ud(U),
  \end{equation}
  where the average is taken over all~$U\subset W$ with~$|U|=u$.
\end{fact}
\begin{proof}
  The one-line proof goes as follows:
  \begin{multline}
    \label{eq:double_counting}
    \Ave_Ud(U)={|W|\choose u}^{-1}\sum_Ud(U)
    ={|W|\choose u}^{-1}\sum_Ue(G[U]){|U|\choose2}^{-1}\\
    =e(G[W]){|W|\choose u}^{-1}{u\choose2}^{-1}{|W|-2\choose u-2}
    =e(G[W]){|W|\choose2}^{-1},
  \end{multline}
  where, clearly, the average and the sums are over all~$U\subset W$
  with~$|U|=u$.
\end{proof}

Let us now prove Claim~\ref{claim:jump}.  

\begin{proof}
  Let~$0<\gamma<1$, $0<\delta<1$, and~$0<\sigma<1$ be fixed, and suppose that
  the graph~$G=G^n$ is as in the statement of the Claim~\ref{claim:jump}.  We
  shall prove that if~$\epsilon$ is small enough and~$n$ is large enough, then
  inequality~\eqref{eq:jump_conclusion} holds for all~$U\subset V=V(G)$
  with~$|U|\geq\gamma n$.
  
  Observe first that it suffices to consider sets~$U\subset V$
  with~$|U|=\lceil\gamma n\rceil$, because of Fact~\ref{fact:ave_of_ave}.  We
  may also suppose that~$\lceil\gamma n\rceil<\lfloor n/2\rfloor$ and, in
  fact, $0<\gamma<1/2$.
   
  Let~$U\subset V$ be such that~$u=|U|=\lceil\gamma n\rceil$.
  Put~$T=V\setminus U$.  Let the number of edges between~$U$ and~$T$
  be~$\sigma_1ut$, where~$t=|T|=n-u$.  Let also~$\sigma_2{t\choose2}$ be the
  number of edges induced by~$T$ in~$G$.  We have
  \begin{equation}
    \label{eq:tot_no_edges}
    e(G[U])+\sigma_1ut+\sigma_2{t\choose2}=\llfloor\sigma{n\choose2}\rrfloor. 
  \end{equation}
  Put~$t'=\lfloor n/2\rfloor-u>0$.  We now select a $t'$-element subset~$T'$
  of~$T$ uniformly at random, and consider the edges that are induced
  by~$U\cup T'$.  Fix an edge~$xy$ of~$G$, with~$x\in U$ and~$y\in T$.  Then,
  $xy$~will be induced by~$U\cup T'$ if and only if~$y\in T'$.  However, this
  happens with probability~${t-1\choose t'-1}{t\choose t'}^{-1}={t'/t}$.
  Given that there are~$\sigma_1ut$ such edges~$xy$, the expected number of
  these edges that will be induced by~$U\cup T'$ is
  \begin{equation}
    \label{eq:el_in_prob}
    \sigma_1ut\times{t'\over t}=\sigma_1ut'.
  \end{equation}
  Now fix an edge~$xy$ of~$G$ with both~$x$ and~$y$ in~$T$.  Then, $xy$~will
  be induced by~$U\cup T'$ with probability
  \begin{equation}
    \label{eq:2el_in_prob}
    {t-2\choose t'-2}{t\choose t'}^{-1}={t'(t'-1)\over t(t-1)}.
  \end{equation}
  Since there are~$\sigma_2{t\choose2}$ such edges~$xy$, the expected number
  of these edges that will be induced by~$U\cup T'$
  is
  \begin{equation}
    \label{eq:no_induced_edges}
    \sigma_2{t\choose2}{t'(t'-1)\over t(t-1)}=\sigma_2{t'\choose2}.
  \end{equation}
  Therefore, by~\eqref{eq:el_in_prob} and~\eqref{eq:no_induced_edges}, the
  expected number of edges that are induced by~$U\cup T'$ is
  \begin{equation}
    \label{eq:expectation}
    e(G[U])+\sigma_1ut'+\sigma_2{t'\choose2}.  
  \end{equation}
  For the remainder of the proof, we fix a set~$T'$ such that this number of
  induced edges~$e(G[U\cup T'])$ is at least as large as given
  in~\eqref{eq:expectation}.  Since~$U\cup T'$ is a set with~$\lfloor
  n/2\rfloor$ vertices, by our hypothesis on~$G$ we have
  \begin{equation}
    \label{eq:expected_lwbd}
    e(G[U])+\sigma_1ut'+\sigma_2{t'\choose2}
    \geq\sigma{\lfloor n/2\rfloor\choose2}(1-\epsilon).
  \end{equation}
  Subtracting~\eqref{eq:expected_lwbd} from~\eqref{eq:tot_no_edges}, we obtain 
  \begin{equation}
    \label{eq:claim_first_ineq}
    \sigma_1u(t-t')+\sigma_2\({t\choose2}-{t'\choose2}\)
    \leq\sigma\({n\choose2}-(1-\epsilon){\lfloor n/2\rfloor\choose2}\). 
  \end{equation}
  Suppose now that~$U$ induces fewer than~$(\sigma-\delta){u\choose2}$ edges.
  Then~\eqref{eq:expected_lwbd} gives that
  \begin{equation}
    \label{eq:expected_lwbd2}
    (\sigma-\delta){u\choose2}+\sigma_1ut'+\sigma_2{t'\choose2}
    >\sigma{\lfloor n/2\rfloor\choose2}(1-\epsilon). 
  \end{equation}
  We deduce that
  \begin{equation}
    \label{eq:sigma1u_lwbd}
    \sigma_1u
    >{1\over t'}\(\sigma{\lfloor n/2\rfloor\choose2}(1-\epsilon)
    -\sigma_2{t'\choose2}-(\sigma-\delta){u\choose2}\).
  \end{equation}
  Plugging~\eqref{eq:sigma1u_lwbd} into~\eqref{eq:claim_first_ineq}, we obtain 
  \begin{multline}
    \label{eq:plugging_in}
    \({t\over t'}-1\)\(\sigma{\lfloor n/2\rfloor\choose2}(1-\epsilon)
    -\sigma_2{t'\choose2}-(\sigma-\delta){u\choose2}\)\\
    +\sigma_2\({t\choose2}-{t'\choose2}\)
    <\sigma\({n\choose2}-(1-\epsilon){\lfloor n/2\rfloor\choose2}\).
  \end{multline}
  Observe that~$t/t'-1\to1/(1-2\gamma)$ as~$n\to\infty$.  Therefore,
  dividing~\eqref{eq:plugging_in} by~$n^2$ and letting~$n\to\infty$, we obtain
  \begin{multline}
    \label{eq:constants_plugging_in}
    {1\over1-2\gamma}
    \({\sigma\over8}(1-\epsilon)-{1\over2}\sigma_2\({1\over2}-\gamma\)^2
    -{1\over2}(\sigma-\delta)\gamma^2\)\\
    +{1\over2}\sigma_2\({3\over4}-\gamma\)
    \leq{\sigma\over2}\({1\over2}-{1-\epsilon\over8}\),
  \end{multline}
  or, rearranging terms, 
  \begin{equation}
    \label{eq:constants_plugging_in2}
    \begin{split}
      {\sigma\over8}(1-\epsilon)+{1\over4}\sigma_2(1-2\gamma)(1-\gamma)
      &-{1\over2}(\sigma-\delta)\gamma^2\\
      &\qquad\leq\sigma\({1\over2}-{1-\epsilon\over8}\)(1-2\gamma).
    \end{split}
  \end{equation}
  We now observe that Fact~\ref{fact:ave_of_ave} and our hypothesis on~$G$
  implies that~$\sigma_2\geq\sigma(1-\epsilon)$.
  Therefore~\eqref{eq:constants_plugging_in2} implies that
  \begin{equation}
    \label{eq:constants_plugging_in3}
    \begin{split}
      {\sigma\over8}(1-\epsilon)
      +{1\over4}\sigma(1-\epsilon)(1-2\gamma)(1-\gamma)
      &-{1\over2}(\sigma-\delta)\gamma^2\\
      &\qquad\leq\sigma\({1\over2}-{1-\epsilon\over8}\)(1-2\gamma).
    \end{split}
  \end{equation}
  Letting~$\epsilon\to0$ in~\eqref{eq:constants_plugging_in3}, we obtain 
  \begin{equation}
    \label{eq:constants_plugging_in4}
    {\sigma\over8}
    +{1\over4}\sigma(1-2\gamma)(1-\gamma)
    -{1\over2}(\sigma-\delta)\gamma^2
    \leq{3\over8}\sigma(1-2\gamma).
  \end{equation}
  However, inequality~\eqref{eq:constants_plugging_in4} reduces to
  \begin{equation}
    \label{eq:constants_plugging_in5}
    {1\over2}\delta\gamma^2\leq0,
  \end{equation}
  which does not hold.  Therefore, there is
  an~$\epsilon_0=\epsilon_0(\gamma,\delta,\sigma)>0$ such
  that~\eqref{eq:constants_plugging_in3} fails for
  all~$0<\epsilon\leq\epsilon_0$.  Moreover, there
  is~$n_0=n_0(\gamma,\delta,\sigma)\geq1$ such that~\eqref{eq:plugging_in}
  fails for all~$n\geq n_0$.  However, this implies that
  if~$0<\epsilon\leq\epsilon_0$ and~$n\geq n_0$, then~$U$ induces at least
  than~$(\sigma-\delta){u\choose2}$ edges.  We have thus
  found~$\epsilon_0=\epsilon_0(\gamma,\delta,\sigma)$
  and~$n_0=n_0(\gamma,\delta,\sigma)$ as required, and Claim~\ref{claim:jump}
  is proved.
\end{proof}

\subsubsection{An application in Ramsey theory}
\label{sec:application_to_Ramsey}
Before we proceed to the proof of Theorem~\ref{thm:universality1}, we state a
pleasant corollary to that result.  Let~$G$ and~$H_1,\dots,H_r$ be graphs.  We
write
\begin{equation}
  \label{eq:Rado_arrow}
  G\indarrow(H_1,\dots,H_r)
\end{equation}
to mean that, however we colour the edges of~$G$ with colours~$c_1,\dots,c_r$,
there must be some~$i$ such that~$G$ contains an \textit{induced}
subgraph~$H'$ isomorphic to~$H_i$ and with all its edges coloured with
colour~$c_i$.

\begin{theorem}
  \label{thm:Induced_Ramsey}
  For any collection of graphs~$H_1,\dots,H_r$, there is a graph~$G$ for
  which~\eqref{eq:Rado_arrow} holds.
\end{theorem}

Theorem~\ref{thm:Induced_Ramsey} was independently proved by
Deuber~\cite{Deu}, Erd\H os, Hajnal, and P\'osa~\cite{EHP}, and
R\"odl~\cite{RoThesis}.  We leave it as an exercise for the reader to deduce
from Theorem~\ref{thm:universality1} that, in fact, \textit{almost all}
graphs~$G\in\cG(n,M)$ satisfy~\eqref{eq:Rado_arrow}
if~$M=\llfloor\sigma{n\choose2}\rrfloor$, where~$0<\sigma<1$ is any fixed
constant (see~\cite{nesetril79:_partit}).

\subsubsection{Uniform edge distribution and subgraph frequency}
\label{sec:equivalence}
The proof of Theorem~\ref{thm:universality1} given below may be adapted to
prove the following result: for any~$\epsilon>0$ and~$0<\sigma<1$, and any
integer~$k\geq1$, there is a~$\delta>0$ such that if~$G=G^n$ satisfies
property~$\cR(\delta,\delta,\sigma)$, then, as long as~$n\geq
n_0(\epsilon,\sigma,k)$,
%
\assertion{(*)}for any graph~$H=H^k$ on~$k$ vertices, the number of induced
embeddings $f\:V(H)\to V(G)$ of~$H$ in~$G$ is
\begin{equation}
  \label{eq:correct_frequency}
  (1+O_1(\epsilon))(n)_k\sigma^{e(H)}(1-\sigma)^{{k\choose2}-e(H)}.
\end{equation}
\endassertion
%
\noindent 
As customary, above we write~$(a)_b$ for~$a(a-1)\dots(a-b+1)$.  It is
straightforward that the expected number of embeddings~$f$ as above in the
random graph~$G\in\cG(n,M)$ is given by~\eqref{eq:correct_frequency},
where~$M=M(n)=\llfloor\sigma{n\choose2}\rrfloor$, and in fact the number of
such embeddings \textit{is} this number for almost all~$G\in\cG(n,M)$.  Thus,
again, the deterministic property~$\cR(\delta,\delta,\sigma)$ captures a
feature of random graphs.  Surprisingly, this `numerical' version of
$k$-universality for~$k=4$, that is, property~(*) for~$k=4$, implies
property~$\cR(\delta,\delta,\sigma)$, as long as~$\epsilon$ is small enough
with respect to~$\delta$ and~$\sigma$.

The properties above, together with several others, are now known as
\textit{quasi-random} graph properties.  The interested reader is referred to
Thomason~\cite{thomason87,thomason87:_random}, Frankl, R\"odl, and
Wilson~\cite{frankl88:_hadam}, and Chung, Graham, and Wilson~\cite{chung89}
(see also Alon and Spencer~\cite[Chapter~9]{AS}).  The study of
quasi-randomness is appealing in its own right, but one may perhaps argue that
investigating quasi-randomness for graphs is especially important because of
the intimate relation between quasi-randomness, $\epsilon$-regularity, and the
regularity lemma.

In Section~\ref{sec:checking}, we shall introduce a new quasi-random property
for graphs.

\subsection{The proof of Theorem~\ref{thm:universality1}}
\label{sec:proof_of_universal}
The proof of Theorem~\ref{thm:universality1} is based on the regularity lemma,
Theorem~\ref{thm:Original}, and on an \textit{embedding lemma}, which asserts
the existence of certain embeddings of graphs.

In this proof, $\gamma$, $\delta$, $\sigma$, $\epsilon$, $\beta$,
and~$\epsilon_k$ will always denote positive constants smaller than~$1$.

\subsubsection{The embedding lemma}
\label{sec:embedding_lemma}
We start with a warm-up.  Suppose we have a tripartite graph~$G=G^{3\ell}$,
with tripartition~$V(G)=B_1\cup B_2\cup B_3$,
where~$|B_1|=|B_2|=|B_3|=\ell>0$.  Suppose also that all the~$3$
pairs~$(B_i,B_j)$, $1\leq i<j\leq3$, are $\epsilon$-regular,
with~$d(B_i,B_j)=\sigma>0$ for all~$1\leq i<j\leq3$.

We claim that, then, the graph~$G$ contains a triangle provided~$\epsilon$ is
small with respect to~$\sigma$.  To prove this claim, first observe that, from
the $\epsilon$-regularity of~$(B_1,B_2)$ and of~$(B_1,B_3)$, one may deduce
that there are at least~$(1-4\epsilon)\ell>0$ vertices~$b_1$ in~$B_1$ such
that their degrees into~$B_2$ and~$B_3$ are both at
least~$(\sigma-\epsilon)\ell$ and at most~$(\sigma+\epsilon)\ell$ (see
Claim~\ref{claim:normal_degrees} below).  However, by the
$\epsilon$-regularity of~$(B_2,B_3)$, at least
\begin{equation}
  \label{eq:warm-up}
  (\sigma-\epsilon)|\Gamma(b_1)\cap B_2||\Gamma(b_1)\cap B_3|
  \geq(\sigma-\epsilon)^3\ell^2>0
\end{equation}
edges are induced by the pair~$(\Gamma(b_1)\cap B_2,\Gamma(b_1)\cap B_3)$ as
long as~$\sigma-\epsilon\geq\epsilon$, that is, $\epsilon<\sigma/2$.  Thus the
claim is proved.  Note that, in fact, we have proved that
if~$\epsilon<\sigma/2$, then the number of triangles in~$G$ is at least
\begin{equation}
  \label{eq:warm-up_counting}
  c\ell^3=c(\sigma,\epsilon)\ell^3,
\end{equation}
where~$c(\sigma,\epsilon)=(1-4\epsilon)(\sigma-\epsilon)^3$.  Clearly,
$c(\sigma,\epsilon)\to\sigma^3$ as~$\epsilon\to0$.  For comparison, let us
observe that the number of triangles is~$\sim\sigma^3\ell^3$
as~$\ell\to\infty$ if~$G$ is drawn at random from all the tripartite graphs
on~$(B_1,B_2,B_3)$ with~$\llfloor\sigma\ell^2\rrfloor$ edges within all the
pairs~$(B_i,B_j)$.

Let us now turn to the embedding lemma that we shall use to prove
Theorem~\ref{thm:universality1}.  We have already seen the essence of the
proof of this lemma in the warm-up above.  In order to state the lemma
concisely, we introduce the following definition.

\begin{definition}[Property~$\cP(k,\ell,\beta,\epsilon)$]
  \label{def:for_embedding_lemma}
  A graph~$G$ has property $\cP(k,\ell,\beta,\epsilon)$ if it admits a
  partition~$V=V(G)=\bigcup_{1\leq i\leq k}B_i$ of its vertex set such that
  \begin{enumerate}
  \item[\textrm{(\textit{i})}]$|B_i|=\ell$ for all~$1\leq i\leq k$,
  \item[\textrm{(\textit{ii})}]all the~${k\choose2}$ pairs~$(B_i,B_j)$,
    where~$1\leq i<j\leq k$, are $\epsilon$-regular, and
  \item[\textrm{(\textit{iii})}]$\beta<d(B_i,B_j)<1-\beta$ for all~$1\leq
    i<j\leq k$. 
  \end{enumerate}
\end{definition}

The embedding lemma is as follows.

\begin{lemma}
  \label{lem:embedding}
  For all~$0<\beta<1/2$ and~$k\geq1$, there
  exist~$\epsilon_k=\epsilon_k(k,\beta)>0$ and~$\ell_k=\ell_k(k,\beta)$ so
  that every graph with property~$\cP(k,\ell,\beta,\epsilon_k)$
  with~$\ell\geq\ell_k$ is $k$-universal.
\end{lemma}

\begin{Remark}
  \label{rem:counting_instead}
  If~$H$ is some graph on~$k$ vertices and~$G$ is a graph satisfying
  property~$\cP(k,\ell,\beta,\epsilon_k)$, then one may in fact estimate the
  number of copies of~$H$ in~$G$ (cf.~\eqref{eq:warm-up_counting}).  Variants
  of Lemma~\ref{lem:embedding} that give such numerical information are
  sometimes referred to as \textit{counting lemmas}.
\end{Remark}

Before we start the proof of Lemma~\ref{lem:embedding}, we state and prove a
simple claim on regular pairs.  If~$u$ is a vertex in a graph~$G$
and~$W\subset V(G)$, then we write~$d_W(u)$ for the degree~$|\Gamma(u)\cap W|$
of~$u$ `into'~$W$.

\begin{claim}
  \label{claim:normal_degrees}
  Let~$(U,W)$ be an $\epsilon$-regular pair in a graph~$G$, and
  suppose~$d(U,W)=\rho$.  Then the number of vertices~$u\in U$ satisfying 
  \begin{equation}
    \label{eq:degree_bds}
    (\rho-\epsilon)|W|
    \leq d_W(u)=|\Gamma(u)\cap W|
    \leq(\rho+\epsilon)|W|
  \end{equation}
  is more than~$(1-2\epsilon)|U|$.
\end{claim}
\begin{proof}
  Suppose for a contradiction that Claim~\ref{claim:normal_degrees} is false.
  Let~$U^-\subset U$ be the set of~$u\in U$ for which the \textit{first}
  inequality in~\eqref{eq:degree_bds} fails, and let~$U^+\subset U$ be the set
  of~$u\in U$ for which the \textit{second} inequality
  in~\eqref{eq:degree_bds} fails.  We are assuming that~$|U^+\cup
  U^-|\geq2\epsilon|U|$.  Therefore, say, $|U^+|\geq\epsilon|U|$.  However, we
  then have
  \begin{equation}
    \label{eq:degree_contradiction}
    d(U^+,W)>\rho+\epsilon.
  \end{equation}
  Since~$(U,W)$ is $\epsilon$-regular, such a witness of
  $\epsilon$-irregularity cannot exist.  The case in
  which~$|U^-|\geq\epsilon|U|$ is similar.  This proves
  Claim~\ref{claim:normal_degrees}.
\end{proof}

We now give the proof of the embedding lemma, Lemma~\ref{lem:embedding}. 

\begin{proof}[Proof of Lemma~\ref{lem:embedding}]
  The proof will be by induction on~$k$.  For~$k=1$ the statement of the lemma
  is trivial.  For~$k=2$, it suffices to
  take~$\epsilon_2=\epsilon_2(2,\beta)=\beta$ and~$\ell_2(2,\beta)=1$.
  Indeed, observe that the fact that~$0<d(B_1,B_2)<1$ implies that there must
  be~$b_i$ and~$b_i'\in B_i$ ($i\in\{1,2\}$) such that~$b_1b_2$ is an edge
  and~$b_1'b_2'$ is not an edge.  For the induction step, suppose
  that~$k\geq3$ and that the assertion of the lemma is true for smaller values
  of~$k$ and for all~$0<\beta<1/2$.
  
  Suppose we are given some~$\beta$, with~$0<\beta<1/2$.  Let
  \begin{equation}
    \label{eq:epsilon_k_def}
    \epsilon_k=\epsilon_k(k,\beta)
    =\min\left\{{1\over2k},{1\over2}\beta\epsilon_{k-1}\right\},
  \end{equation}
  and
  \begin{equation}
    \label{eq:ell_k_def}
    \ell_k=\ell_k(k,\beta)
    =\max\left\{2\llceil\ell_{k-1}\over\beta\rrceil,k\right\},
  \end{equation}
  where
  \begin{equation}
    \label{eq:previous_epsilon_beta}
    \epsilon_{k-1}=\epsilon_{k-1}(k-1,\beta/2)
    \quad\text{and}\quad
    \ell_{k-1}=\ell_{k-1}(k-1,\beta/2).
  \end{equation}
  We claim that the choices for~$\epsilon_k$ and~$\ell_k$
  in~\eqref{eq:epsilon_k_def} and~\eqref{eq:ell_k_def} will do.  Thus, let~$G$
  be a graph satisfying property~$\cP(k,\ell,\beta,\epsilon_k)$,
  where~$\ell\geq\ell_k$.  Let~$B_1,\dots,B_k$ be the blocks of the partition
  of~$V=V(G)$ ensured by Definition~\ref{def:for_embedding_lemma}.
  Suppose~$H$ is a graph on the vertices $x_1,\dots,x_k$.  We shall show that
  there exist $b_1,\dots,b_k$, with~$b_i\in B_i$, such that the
  map~$\phi\:x_i\mapsto b_i$ is an embedding of~$H$ into~$G$ (that is, $\phi$
  is an isomorphism between~$H$ and~$G[b_1,\dots,b_k]$, the graph induced by
  the~$b_i$ in~$G$).

  Pick a vertex~$b_k\in B_k$ for which
  \begin{equation}
    \label{eq:degree_conds}
    (d(B_k,B_j)-\epsilon_k)\ell
    <d_{B_j}(b_k)=|\Gamma(b_k)\cap B_j|
    <(d(B_k,B_j)+\epsilon_k)\ell
  \end{equation}
  for all~$1\leq j<k$.  The existence of such a vertex~$b_k$ follows from
  Claim~\ref{claim:normal_degrees}.  Indeed, the claim tells us that the
  number of vertices that fail~\eqref{eq:degree_conds} for some~$1\leq j<k$ is
  at most
  \begin{equation}
    \label{eq:exceptional_vertices_upbd}
    2(k-1)\epsilon_k\ell<\ell=|B_k|,
  \end{equation}
  since~$\epsilon_k\leq1/2k$ (see~\eqref{eq:epsilon_k_def}).  For all~$1\leq
  j<k$, we now choose sets~$\tB_j\subset B_j$ satisfying the following
  properties: 
  \begin{enumerate}
  \item[\textrm{(\textit{i})}]$|\tB_j|=\llceil\beta\ell/2\rrceil\geq\ell_{k-1}$,  
  \item[\textrm{(\textit{ii})}]if~$x_jx_k\in E(H)$, then~$bb_k\in E(G)$ for
    all~$b\in\tB_j$, and if~$x_jx_k\notin E(H)$, then~$bb_k\notin E(G)$ for
    all~$b\in\tB_j$.
  \end{enumerate}
  The existence of the sets~$\tB_j$ ($1\leq j<k$) follows from our choice
  of~$b_k$.  Indeed, \eqref{eq:degree_conds}~tells us that~$b_k$ has more than
  \begin{equation}
    \label{eq:nbhd_lwbd}
    (d(B_k,B_j)-\epsilon_k)\ell
    >(\beta-\epsilon_k)\ell
    \geq\(\beta-{1\over2}\beta\epsilon_{k-1}\)\ell
    \geq{1\over2}\beta\ell
  \end{equation}
  neighbours in~$B_j$.  Similarly, \eqref{eq:degree_conds}~tells us
  that~$b_k$ has more than
  \begin{equation}
    \label{eq:nbhd_upbd}
    (1-d(B_k,B_j)-\epsilon_k)\ell
    >(\beta-\epsilon_k)\ell
    \geq{1\over2}\beta\ell
  \end{equation}
  non-neighbours in~$B_j$.

  Now fix a pair~$1\leq i<j<k$, and let~$X_i\subset\tB_i$
  and~$X_j\subset\tB_j$ be such that~$|X_i|\geq\epsilon_{k-1}|\tB_i|$
  and~$|X_j|\geq\epsilon_{k-1}|\tB_j|$.  Then
  \begin{equation}
    \label{eq:size_lwbd}
    \min\{|X_i|,|X_j|\}
    \geq\epsilon_{k-1}|\tB_i|
    =\epsilon_{k-1}|\tB_j|
    \geq{2\epsilon_k\over\beta}\llceil\beta\ell\over2\rrceil
    \geq\epsilon_k\ell.
  \end{equation}
  From the $\epsilon_k$-regularity of the pair~$(B_i,B_j)$, we deduce that 
  \begin{multline}
    \label{eq:inherited_regularity}
    |d(X_i,X_j)-d(\tB_i,\tB_j)|\\
    \leq|d(X_i,X_j)-d(B_i,B_j)|+|d(B_i,B_j)-d(\tB_i,\tB_j)|
    \leq2\epsilon_k\leq\epsilon_{k-1}.
  \end{multline}
  Therefore all the pairs~$(\tB_i,\tB_j)$ with~$1\leq i<j<k$ are
  $\epsilon_{k-1}$-regular.  Our induction hypothesis then tells us that there
  exist $b_j\in B_j$ ($1\leq j<k$) for which the map~$x_j\mapsto b_j$ ($1\leq
  j<k$) is an isomorphism between~$H-x_k$ and~$G[b_1,\dots,b_{k-1}]$.
  Clearly, $\phi\:x_j\mapsto b_j$ ($1\leq j\leq k$) is an isomorphism
  between~$H$ and~$G[b_1,\dots,b_k]$.
\end{proof}

\subsubsection{Proof of Theorem~\ref{thm:universality1}}
\label{sec:proof_of_universal_main}
We are now able to prove Theorem~\ref{thm:universality1}.  We shall make use
of two well known results from graph theory: Ramsey's theorem and Tur\'an's
theorem.

\begin{proof}[Proof of Theorem~\ref{thm:universality1}]
  Let~$\delta_1=\max\{\sigma+\delta-1/2,1/2-\sigma+\delta\}$.  We clearly
  have~$0<\delta_1<1/2$ and in fact
  \begin{equation}
    \label{eq:wlog_calculation}
    \begin{split}
      0<{1\over2}-\delta_1&\leq{1\over2}-\({1\over2}-\sigma+\delta\)\\
      &\quad=\sigma-\delta\leq\sigma+\delta
      ={1\over2}+\(\sigma+\delta-{1\over2}\)
      \leq{1\over2}+\delta_1<1.
    \end{split}
  \end{equation}
  The inequalities in~\eqref{eq:wlog_calculation} imply that
  property~$\cR(\gamma,\delta,\sigma)$ implies
  property~$\cR(\gamma,\delta_1,1/2)$.  Therefore we may assume in
  Theorem~\ref{thm:universality1} that~$\sigma=1/2$ and~$0<\delta<1/2$.  We
  may further assume that
  \begin{equation}
    \label{eq:k_is_big}
    k\geq{3\over\beta},\quad\text{where}\quad\beta={1\over2}-\delta>0.
  \end{equation}

  We now define the constants~$\gamma$ and~$N_0$ promised in
  Theorem~\ref{thm:universality1}.  Put
  \begin{equation}
    \label{eq:epsilon_def}
    \epsilon=\min\left\{{1\over R(k,k,k)},
      \epsilon_k\right\},
  \end{equation}
  where~$\epsilon_k=\epsilon_k(k,\beta/2)$ is the number whose existence is
  guaranteed by Lemma~\ref{lem:embedding}, and $R(k,k,k)$ is the usual Ramsey
  number for~$K^k$ and three colours: $R(k,k,k)$~is the minimal integer~$R$
  such that, in any colouring of the edges of~$K^R$ with three colours, we
  must have a~$K^k$ all of whose edges are coloured with the same colour.
  
  Put~$k_0=R(k,k,k)$, and invoke Theorem~\ref{thm:Original} with this~$k_0$
  and~$\epsilon$ given in~\eqref{eq:epsilon_def}.  We obtain
  constants~$K_0(\epsilon,k_0)\geq k_0$ and~$N_0(\epsilon,k_0)$.  Now let
  \begin{equation}
    \label{eq:N_0_def}
    N_0=\max\left\{N_0(\epsilon,k_0),
      {1\over1-\epsilon}{K_0(\epsilon,k_0)\ell_k}\right\},
  \end{equation}
  where~$\ell_k=\ell_k(k,\beta/2)$ is given by Lemma~\ref{lem:embedding}.
  Furthermore, we let
  \begin{equation}
    \label{eq:gamma_def}
    \gamma={k(1-\epsilon)\over K_0(\epsilon,k_0)}.
  \end{equation}
  Our aim is to show that the choices for~$N_0$ and~$\gamma$ given
  in~\eqref{eq:N_0_def} and~\eqref{eq:gamma_def} will do.
  
  Suppose a graph~$G=G^n$ with~$n\geq N_0$ vertices satisfies
  property~$\cR(\gamma,\delta,1/2)$.  We shall use the regularity lemma to
  find an induced subgraph~$G'$ of~$G$ that satisfies
  property~$\cP(k,\ell,\beta/2,\epsilon_k)$, where~$\ell\geq\ell_k$.  An
  application of the embedding lemma, Lemma~\ref{lem:embedding}, will then
  complete the proof.
  
  Let~$V=V(G)=\bigcup_{0\leq i\leq t}C_i$ be an $\epsilon$-regular,
  $(\epsilon,t)$-equitable partition for~$G$ with~$k_0\leq t\leq
  K_0(\epsilon,k_0)$.  The existence of such a partition is ensured by
  Theorem~\ref{thm:Original}.  Let~$\ell=|C_i|$ ($1\leq i\leq t$).  
  
  Consider the graph~$F$ on the vertex set~$[t]=\{1,\dots,t\}$, where $ij\in
  E(F)$ if and only if~$(C_i,C_j)$ is an $\epsilon$-regular pair in~$G$.  We
  know that~$F$ has at least $(1-\epsilon){t\choose2}$ edges.  By the
  well-known theorem of Tur\'an~\cite{Turan41}, it follows that~$F$ has a
  clique with~$R=R(k,k,k)$ vertices.  Adjust the notation so that this clique
  is induced by the vertices~$1,\dots,R$.  Then the blocks~$C_i$ ($1\leq i\leq
  R$) are such that all the pairs~$(C_i,C_j)$ with $1\leq i<j\leq R$ are
  $\epsilon$-regular.
  
  We now define a partition~$T_1\cup T_2\cup T_3$ of the
  set~${[R]\choose2}$ of the pairs~$ij$ ($1\leq i<j\leq R$) as
  follows: the pair~$ij$ belongs to~$T_1$ if and only
  if~$d(C_i,C_j)\leq\beta/2$; the pair~$ij$ belongs to~$T_2$ if and only
  if~$\beta/2<d(C_i,C_j)<1-\beta/2$; and, finally, the pair~$ij$ belongs
  to~$T_3$ if and only if~$d(C_i,C_j)\geq1-\beta/2$.
  
  By the definition of~$R=R(k,k,k)$, we know that there is a set~$J\subset[R]$
  with~$|J|=k$ such that~$F[J]$ is monochromatic, that is, ${J\choose2}\subset
  T_\alpha$ for some~$\alpha\in\{1,2,3\}$.  We consider the graph
  \begin{equation}
    \label{eq:G'_def}
    G'=G\bigg[\bigcup_{j\in J}C_j\bigg]
  \end{equation}
  induced by~$\bigcup_{j\in J}C_j$ in~$G$.  Suppose~$\alpha=1$.  Then the
  number of edges~$e(G')$ in~$G'$ satisfies
  \begin{equation}
    \label{eq:case_sparse}
    e(G')\leq{k\choose2}{\beta\over2}\ell^2+k{\ell\choose2}
    \leq{\beta k^2\ell^2\over4}+{k\ell^2\over2}
    <\({1\over2}-\delta\){k\ell\choose2},
  \end{equation}
  where we have used~\eqref{eq:k_is_big} and the fact that~$k\ell\geq k>6$.
  Since~$|V(G')|=k\ell\geq(1-\epsilon)kn/K_0(\epsilon,k_0)=\gamma n$
  (see~\eqref{eq:gamma_def}), inequality~\eqref{eq:case_sparse} contradicts
  property~$\cP(\gamma,\delta,1/2)$.  This contradiction shows
  that~$\alpha\neq1$.  If~$\alpha=3$, then we obtain a similar contradiction.
  In this case, as a little calculation using~\eqref{eq:k_is_big} shows, the
  graph~$G'$ satisfies
  \begin{equation}
    \label{eq:case_dense}
    e(G')\geq{k\choose2}\(1-{\beta\over2}\)\ell^2
    >\({1\over2}+\delta\){k\ell\choose2}.
  \end{equation}
  Thus~$\alpha\neq3$ and we conclude that~$\alpha=2$.  We finally observe
  that, by~\eqref{eq:N_0_def}, we have
  \begin{equation}
    \label{eq:ell_is_large}
    \ell\geq{(1-\epsilon)n\over K_0(\epsilon,k_0)}
    \geq{(1-\epsilon)N_0\over K_0(\epsilon,k_0)}\geq\ell_k.
  \end{equation}
  Therefore, as promised, the graph~$G'$ satisfies property
  $\cP(k,\ell,\beta/2,\epsilon_k)$ for~$\ell\geq\ell_k$.  To complete the
  induction step, it suffices to invoke Lemma~\ref{lem:embedding}.

  The proof of Theorem~\ref{thm:universality1} is complete.
\end{proof}


\section{Further applications}
\label{sec:further_appls}

In this section, we mention a few more applications of the regularity lemma to
illustrate some further aspects of its uses.

\subsection{Embedding large bounded degree graphs}
\label{sec:blow-up}
Lemma~\ref{lem:embedding}, the embedding lemma, deals with induced embedding,
that is, there we are concerned with embedding certain graphs as
\textit{induced} subgraphs in a given graph.  In several applications, one is
interested in finding embeddings as subgraphs that need not be necessarily
induced.  In this section, we shall briefly discuss some variants of
Lemma~\ref{lem:embedding} for `non-induced' embeddings.

Let us say that a graph~$G$ has property~$\cPw(k,\ell,\beta,\epsilon)$ if it
satisfies the conditions in Definition~\ref{def:for_embedding_lemma}, except
that, instead of~(\textit{iii}) in that definition, we only require the
following weaker property:
\begin{enumerate}
\item[\textrm{(\textit{iv})}]$d(B_i,B_j)>\beta$ for all~$1\leq i<j\leq k$.
\end{enumerate}
We now state a variant of the embedding lemma for subgraphs; at the expense of
requiring that the graph to be embedded should have bounded degree, we gain on
the size of the graph that we are able to embed.  For convenience, let us say
that a graph~$H$ is of \textit{type~$(m,k)$} if~$H$ admits a proper vertex
colouring with~$k$ colours in such a way that every colour occurs at most~$m$
times.

\begin{lemma}
  \label{lem:CRTSz_embedding}
  For all~$k\geq1$, $\beta>0$ and~$\Delta\geq1$, there
  exist~$\epsilon=\epsilon(k,\beta,\Delta)>0$, $\nu=\nu(k,\beta,\Delta)>0$,
  and~$\ell_0=\ell_0(k,\beta,\Delta)$ so that every graph with
  property~$\cPw(k,\ell,\beta,\epsilon)$ with~$\ell\geq\ell_0$ contains all
  graphs of type~$(\nu\ell,k)$ that have maximum degree at most~$\Delta$.
\end{lemma}

Let us stress that the lemma above allows us to embed bounded degree graphs
$H=H^n$ in certain graphs~$G=G^N$ with~$N$ only linearly larger than~$n$.  The
regularity lemma and Lemma~\ref{lem:CRTSz_embedding} were the key tools in
Chv\'atal, R\"odl, Szemer\'edi, and Trotter~\cite{ChvRoSzT}, where it is
proved that the Ramsey number of a bounded degree graph~$H=H^n$ is linear
in~$n$.

The proof of Lemma~\ref{lem:CRTSz_embedding} in~\cite{ChvRoSzT} gives
for~$\nu$ an exponentially small quantity in~$\Delta$.  Thus, one has to have
`a lot of extra room' for the embedding.  A recent, beautiful result of
Koml\'os, S\'ark\"ozy, and Szemer\'edi~\cite{komlos97:_blow}
(see~\cite{komlos98} for an algorithmic version), known as the \textit{blow-up
  lemma}, shows that one need not waste so much room; in fact, one does not
have to waste any room at all if a small extra hypothesis is imposed on the
graph where the embedding is to take place.

Let~$(U,W)$ be an $\epsilon$-regular pair in a graph~$G$.  We say that~$(U,W)$
is \textit{$(\epsilon,\delta)$-super-regular} if
%
\assertion{(\dag)} for all~$u\in U$, we have~$d(u)\geq\delta|W|$, and for
all~$w\in W$, we have~$d(w)\geq\delta|U|$.  
\endassertion
%
\noindent Observe that~(\dag) implies that~$d(U,W)\geq\delta$.  Let us say
that a graph~$G$ satisfies property~$\cPw(k,\ell,\beta,\epsilon,\delta)$ if it
satisfies~$\cPw(k,\ell,\beta,\epsilon)$, with~(\textit{ii}) in the definition
of property~$\cP(k,\ell,\beta,\epsilon)$,
Definition~\ref{def:for_embedding_lemma}, strengthened to
\begin{enumerate}
\item[\textrm{(\textit{v})}]all the~${k\choose2}$ pairs~$(B_i,B_j)$,
  where~$1\leq i<j\leq k$, are $(\epsilon,\delta)$-super-regular.
\end{enumerate}
We may now state the blow-up lemma.

\begin{theorem}
  \label{thm:blow-up}
  For all~$k\geq1$, $\beta>0$, $\delta>0$, and~$\Delta\geq1$, there
  exist~$\epsilon=\epsilon(k,\beta,\delta,\Delta)>0$
  and~$\ell_0=\ell_0(k,\beta,\delta,\Delta)$ so that every graph that
  satisfies property~$\cPw(k,\ell,\beta,\epsilon,\delta)$
  with~$\ell\geq\ell_0$ contains all graphs of type~$(\ell,k)$ that have
  maximum degree at most~$\Delta$.
\end{theorem}

The striking difference between Lemma~\ref{lem:CRTSz_embedding} and
Theorem~\ref{thm:blow-up} is that, with the rather weak additional
condition~(\dag), we are able to embed \textit{spanning subgraphs} (that is,
we may take~$\nu=1$).

Theorem~\ref{thm:blow-up} is one of the key ingredients in the recent
successes of Koml\'os, S\'ark\"ozy, and Szemer\'edi in tackling well-known,
hard conjectures such as Seymour's conjecture and P\'osa's conjecture on
powers of Hamiltonian
cycles~\cite{komlos98:_posa_seymour,komlos98:_proof_seymour}, a conjecture of
Bollob\'as on graph packings~\cite{komlos95:_proof_bollob}, and Alon and
Yuster's conjecture~\cite{alon96:_yuster_JCTB} (see~\cite[p.~175]{komlos99}).

We shall not discuss the proof of Theorem~\ref{thm:blow-up}, which is indeed
quite difficult
(see~\cite{rodl99:_perfec_blow_lemma,roedl98:_algorithmic_blowup} for
alternative proofs).  The reader should consult Koml\'os~\cite{komlos99} for a
survey on the blow-up lemma.

\subsection{Property testing}
\label{sec:property_testing}
We shall now discuss a recent application of regularity to a complexity
problem.  We shall see how the regularity lemma may be used to prove the
correctness of certain algorithms.  This section is based on results due to
Alon, Fischer, Krivelevich, and
Szegedy~\cite{alon99:_effic_full,alon99:_effic}.  These authors develop a new
variant of the regularity lemma and use it to prove a far reaching result
concerning the \textit{testability} of certain graph properties.

As a starting point, we state the following result, which the reader should
first try to prove with bare hands.

\begin{theorem}
  \label{thm:Rusza-Szemeredi}
  For any~$\epsilon>0$ there is a~$\delta>0$ for which the following holds.
  Suppose a graph~$G=G^n=(V,E)$ is such that~$G-F=(V,E\setminus F)$
  contains a triangle for any set~$F\subset{V\choose2}$
  with~$|F|\leq\epsilon{n\choose2}$.  Then~$G$ contains at least~$\delta n^3$
  triangles.
\end{theorem}

The theorem above follows easily from the warm-up result in
Section~\ref{sec:embedding_lemma} and the regularity lemma.  A proof of
Theorem~\ref{thm:Rusza-Szemeredi} that does not use the regularity lemma (in
any form!) would be of considerable interest.

Theorem~\ref{thm:Rusza-Szemeredi} implies that we may efficiently distinguish
triangle-free graphs from graphs that contain triangles in a robust way, that
is, graphs~$G$ as in the statement of this theorem.  Indeed, one may simply
randomly pick a number of vertices, say~$N$, from the input graph~$G=G^n$ and
then check whether a triangle is induced.  If we catch no triangle, we return
the answer `yes, the graph~$G$ is triangle-free'.  If we do catch a triangle,
we return the answer `no, the graph~$G$ is ``$\epsilon$-far'' from being
triangle-free'.

The striking fact about the algorithm above is that it will return the correct
answer with high probability if~$N$ is a large enough constant with respect
to~$\epsilon$.  Here, $N$~need not grow with~$n$, the number of vertices in
the input graph~$G=G^n$, and hence this is a \textit{constant time} algorithm.
In this section, we shall briefly discuss some far reaching generalizations of
this result.

\subsubsection{Definitions and the testability result}
\label{sec:testability}
The general notion of property testing was introduced by Rubinfeld and
Sudan~\cite{RubinfeldS1996}, but in the context of combinatorial
testing it is the work of Goldreich and his
co-authors~\cite{goldreich99:_combin,%
goldreich96:_proper,%
goldreich98:_proper,%
goldreich97:bound_degree,%
oded99:_sublin_bipar_tester_bound_degree_graph} that are most relevant
to us.

Let~$\cG^n$ be the collection of all graphs on a fixed $n$-vertex set,
say~$[n]=\{1,\dots,n\}$.  Put~$\cG=\bigcup_{n\geq1}\cG^n$.  A
\textit{property} of graphs is simply a subset~$\cP\subset\cG$ that is
closed under isomorphisms.  There is a natural notion of distance in
each~$\cG^n$, the \textit{normalized Hamming distance}: the
distance~$d(G,H)=d_n(G,H)$ between two graphs~$G$ and~$H\in\cG^n$ is
$|E(G)\vartriangle E(H)|{n\choose2}^{-1}$, where~$E(G)\vartriangle
E(H)$ denotes the symmetric difference of the edge sets of~$G$
and~$H$.

We say that a graph~$G$ is \textit{$\epsilon$-far} from having
property~$\cP$ if 
\begin{equation}
  \label{eq:distance_def}
  d(G,\cP)=\min_{H\in\cP}d(G,H)\geq\epsilon,
\end{equation}
that is, a total of~$\geq\epsilon{n\choose2}$ edges have to be added to or
removed from~$G$ to turn it into a graph that satisfies~$\cP$.

An \textit{$\epsilon$-test} for a graph property~$\cP$ is a randomized
algorithm~$\cA$ that receives as input a graph~$G$ and behaves as
follows: if~$G$ has~$\cP$ then with probability~$\geq2/3$ we
have~$\cA(G)=1$, and if~$G$ is $\epsilon$-far from having~$\cP$ then
with probability~$\geq2/3$ we have~$\cA(G)=0$.  The graph~$G$ is given
to~$\cA$ through an oracle; we assume that~$\cA$ is able to generate random 
vertices from~$G$ and it may \textit{query} the oracle whether
two vertices that have been generated are adjacent.

We say that a graph property~$\cP$ is \textit{testable} if, for
all~$\epsilon>0$, it admits an $\epsilon$-test that makes at most~$Q$
queries to the oracle, where~$Q=Q(\epsilon)$ is a constant that
depends only on~$\epsilon$.  Note that, in particular, we require the
number of queries to be independent of the order of the input graph.

Goldreich, Goldwasser, and Ron~\cite{goldreich96:_proper,%
goldreich98:_proper%,%
}, besides showing that there exist NP graph properties that are not
testable, proved that a large class of interesting graph properties \textit{are}
testable, including the property of being $k$-colourable, of having a
clique with $\geq\rho n$ vertices, and of having a cut with $\geq\rho
n^2$ edges, where~$n$ is the order of the input graph.  The regularity
lemma is not used in~\cite{goldreich96:_proper,%
goldreich98:_proper%,%
}.  The fact that $k$-colourability is testable had in fact been
proved implicitly in~\cite{RodlDuke}, where regularity is used.

We are now ready to turn to the result of Alon, Fischer, Krivelevich,
and Szegedy~\cite{alon99:_effic_full,alon99:_effic}.  Let us consider
properties from the first order theory of graphs.  Thus, we are
concerned with properties that may be expressed through quantification
of vertices, Boolean connectives, equality, and adjacency.  Of
particular interest are the properties that may be expressed in the
form 
\begin{equation}
  \label{eq:formula_def}
  \exists x_1,\dots,x_r\;\forall y_1,\dots,y_s\;
  A(x_1,\dots,x_r,y_1,\dots,y_s),
\end{equation}
where~$A$ is a quantifier-free first order expression.  Let us call
such properties \textit{of type~$\exists\forall$}.  Similarly, we
define properties \textit{of type~$\forall\exists$}.  The main result
of~\cite{alon99:_effic_full,alon99:_effic} is as follows.

\begin{theorem}
  \label{thm:alon_et_al}
  All first order properties of graphs that may be expressed with at most one
  quantifier as well as all properties that are of type~$\exists\forall$ are
  testable.  Furthermore, there exist first order properties of
  type~$\forall\exists$ that are not testable.
\end{theorem}

The first part of the proof of the positive result in
Theorem~\ref{thm:alon_et_al} involves the reduction, up to testability, of
properties of 
type~$\exists\forall$ to a certain generalized colourability property.
A new variant of the regularity lemma is then used to handle this
generalized colouring problem.

\subsubsection{A variant of the regularity lemma}
\label{sec:alon_et_al_regularity}
In this section we shall state a variant of the regularity lemma
proved in~\cite{alon99:_effic_full,alon99:_effic}.  

Let us say that a partition~$P=(C_i)_{i=1}^k$ of a set~$V$ is an
\textit{equipartition} of~$V$ if all the sets~$C_i$ ($1\leq i\leq k$) differ
by at most~$1$ in size.  In this section, we shall be interested in partitions
as in Remark~\ref{rem:no_exceptional} and Theorem~\ref{thm:Original2}.  Below,
we shall have an equipartition of~$V$
$$
P'=\{C_{i,j}\:1\leq i\leq k,\;1\leq j\leq\ell\}
$$
that is a refinement of a given partition~$P=(C_i)_{i=1}^k$.  In
this notation, we understand that, for all~$i$, all the $C_{i,j}$
($1\leq j\leq\ell$) are contained in~$C_i$.

\begin{theorem}
  \label{thm:alon_et_al_regularity}
  For every integer~$k_0$ and every function~$0<\epsilon(r)<1$ defined
  on the positive integers, there are constants~$K=K(k_0,\epsilon)$
  and~$N=N(k_0,\epsilon)$ with the following property.  If~$G$ is any
  graph with at least~$N$ vertices, then there exist
  equipartitions~$P=(C_i)_{1\leq i\leq k}$
  and~$P'=(C_{i,j})_{1\leq i\leq k,\;1\leq j\leq\ell}$ of~$V=V(G)$
  such that the following hold{\rm:}
  \begin{enumerate}
  \item[{\rm(\textit{i})}]$|P|=k\geq k_0$ and~$|P'|=k\ell\leq K$;
  \item[{\rm(\textit{ii})}]at least~$(1-\epsilon(0)){k\choose2}$ of
    the pairs~$(C_i,C_{i'})$ with~$1\leq i<i'\leq k$ are
    $\epsilon(0)$-regular;
  \item[{\rm(\textit{iii})}]for all~$1\leq i<i'\leq k$, at
    least~$(1-\epsilon(k))\ell^2$ of the pairs~$(C_{i,j},C_{i',j'})$ with~$j$,
    $j'\in[\ell]$ are $\epsilon(k)$-regular;
  \item[{\rm(\textit{iv})}]for at least~$(1-\epsilon(0)){k\choose2}$
    of the pairs~$1\leq i<i'\leq k$, we have that for at
    least~$(1-\epsilon(0))\ell^2$ of the pairs~$j$, $j'\in[\ell]$ we
    have
    $$
    |d_G(C_i,C_{i'})-d_G(C_{i,j},C_{i',j'})|\leq\epsilon(0).
    $$
  \end{enumerate}
\end{theorem}

Suppose we have partitions~$P$ and~$P'$ as in
Theorem~\ref{thm:alon_et_al_regularity} above and that $\epsilon(k)\ll1/k$.
It is not difficult to see that then, for many `choice' functions
$j\:[k]\to[\ell]$, we have that~$\tP=(C_{i,j(i)})_{1\leq i\leq k}$ is an
equipartition of an induced subgraph of~$G$ such that the following hold:
\begin{enumerate}
\item[(\textit{a})]\textit{all} the pairs~$(C_{i,j(i)},C_{i',j(i')})$
  are $\epsilon(k)$-regular,
\item[(\textit{b})]for at least~$(1-\epsilon(0)){k\choose2}$ of the
  pairs~$1\leq i<i'\leq k$, we have
  $$
  |d_G(C_i,C_{i'})-d_G(C_{i,j(i)},C_{i',j(i')})|\leq\epsilon(0).
  $$
\end{enumerate}
Roughly speaking, this consequence of Theorem~\ref{thm:alon_et_al_regularity}
lets us have some grip on the irregular pairs.  Even if~$(C_i,C_{i'})$ is
irregular, the pair~$(C_{i,j(i)},C_{i',j(i')})$ is regular and hence we have
some control over the induced bipartite graph~$G[C_i,C_{i'}]$.  For instance,
if in some application we have to construct some bipartite graph
within~$G[C_i,C_{i'}]$, we may do so by working on the
subgraph~$G[C_{i,j(i)},C_{i',j(i')}]$.

We have already observed that we must allow irregular pairs in
Theorem~\ref{thm:Original} (see Section~\ref{sec:gowers}).  In a way,
Theorem~\ref{thm:alon_et_al_regularity} presents a way around this difficulty.

Theorem~\ref{thm:alon_et_al_regularity} and its corollary mentioned above are
the main ingredients in the proof of the following result
(see~\cite{alon99:_effic_full,alon99:_effic} for details). 

\begin{theorem}
  \label{thm:abundant}
  For every~$\epsilon>0$ and~$h\geq1$, there is~$\delta=\delta(\epsilon,h)>0$
  for which the following holds.
  Let~$H$ be an arbitrary graph on~$h$ vertices and
  let~$\cP=\Forbind(H)$ be the property of \textsl{not} containing~$H$
  as an induced subgraph.  If an $n$-vertex graph~$G$ is
  $\epsilon$-far from~$\cP$, then $G$~contains $\delta n^h$ induced
  copies of~$H$.
\end{theorem}

The case in which~$H$ is a complete graph follows from the original regularity
lemma (the warm-up observation of Section~\ref{sec:embedding_lemma} proved
this for~$H=K^3$), but the general case requires the corollary to
Theorem~\ref{thm:alon_et_al_regularity} discussed above.  Note that
Theorem~\ref{thm:abundant} immediately implies that the property of membership
in~$\Forbind(H)$ (in order words, the property of not containing an induced
copy of~$H$) is a testable property for any graph~$H$.

The proof of Theorem~\ref{thm:alon_et_al} requires a generalization of
Theorem~\ref{thm:abundant} related to the colouring problem alluded to
at the end of Section~\ref{sec:testability}.  We refer the reader
to~\cite{alon99:_effic_full,alon99:_effic}.  We close by remarking
that Theorem~\ref{thm:alon_et_al_regularity} has an algorithmic
version, although we stress that this is not required in the proof of
Theorem~\ref{thm:alon_et_al}.

\section{Proof of the regularity lemma}
\label{sec:construction}

We now prove the regularity lemma for sparse graphs.  We shall prove
Theorem~\ref{thm:SSz}.  The proof of Theorem~\ref{thm:SSzp} is similar.  We
observe that the proof below follows very closely the proof of the original
regularity lemma, Theorem~\ref{thm:Original}.  Indeed, to recover a proof of
Theorem~\ref{thm:Original} from the proof below, it suffices to set~$G=K^n$. 

\subsection{The refining procedure}
\label{sec:refinment}
Fix~$G=G^n$ and put~$V=V(G)$.  Also, assume that~$P_0=(V_i)_1^\ell$ is a fixed
partition of~$V$, and that~$G$ is $(P_0,\eta)$-uniform for
some~$0<\eta\leq1$.  Moreover, let~$p=p(G)$ be as in~\eqref{eq:Unif}.

We start with a `continuity' result.  Let~$H\subset G$ be a spanning subgraph
of~$G$.

\begin{lemma}
  \label{lem:LemmaB}
Let~$0<\delta\leq10^{-2}$ be fixed. Let~$U$,
$W\subset V(G)$ be such that~$(U,W)\prec P_0$, and~$\delta|U|$,
$\delta|W|\geq\eta n$. If~$U^*\subset U$, $W^*\subset W$,
$|U^*|\geq(1-\delta)|U|$, and~$|W^*|\geq(1-\delta)|W|$, then
\begin{enumerate}
\item[(\textit{i})]$|\dHG(U^*,W^*)-\dHG(U,W)|\leq5\delta$,
\item[(\textit{ii})]$|\dHG(U^*,W^*)^2-\dHG(U,W)^2|\leq9\delta$.
\end{enumerate}
\end{lemma}
\begin{proof}
  Note first that we have~$\eta\leq\delta$, as~$\eta n\leq\delta|U|$,
  $\delta|W|\leq\delta n$. Let~$U^*$, $W^*$ be as given in the lemma.  We
  first check~({\it i\/}).
  
  ({\it i\/})~We start by noticing that
  \begin{multline*}
    \dHG(U^*,W^*)\geq{\eH(U,W)-2(1+\eta)p\delta|U||W|\over\eG(U,W)}\\
    \geq\dHG(U,W)-2\delta{1+\eta\over1-\eta}\geq\dHG(U,W)-3\delta.
  \end{multline*}
  Moreover,
  \begin{equation*}
    \begin{split}
      &\dHG(U^*,W^*)\leq{\eH(U,W)\over\eG(U^*,W^*)}
      \leq{\eH(U,W)\over(1-\eta)p|U^*||W^*|}\\
      &\hspace{1.5cm}\leq{\eH(U,W)\over(1-\eta)p(1-\delta)^2|U||W|}
      \leq{1+\eta\over(1-\eta)(1-\delta)^2}\dHG(U,W)\\
      &\hspace{1.5cm}\leq\dHG(U,W)+5\delta.
    \end{split}
  \end{equation*}
  Thus~({\it i\/}) follows.
  
  ({\it ii\/})~The argument here is similar. First
  \begin{equation*}
    \begin{split}
      \dHG(U^*,W^*)
      &\geq{\big(\eH(U,W)-2(1+\eta)p\delta|U||W|\big)^2\over\eG(U,W)^2}\\
      &\geq\dHG(U,W)^2-{4(1+\eta)p\delta|U||W|\eH(U,W)
        \over\eG(U,W)(1-\eta)p|U||W|} \\
      &\geq\dHG(U,W)^2-4\delta{1+\delta\over1-\delta} \geq\dHG(U,W)^2-5\delta.
    \end{split}
  \end{equation*}
  Secondly,
  \begin{equation*}
    \begin{split}
      \dHG(U^*,W^*)^2&\leq{\eH(U,W)^2\over\eG(U^*,W^*)^2}\cr
      &\leq{\eH(U,W)^2\over(1-\eta)^2p^2|U^*|^2|W^*|^2}
      \leq{\eH(U,W)^2\over(1-\eta)^2(1-\delta)^4p^2|U||W|}\cr
      &\leq\(1+\eta\over(1-\eta)(1-\delta)^2\)^2\dHG(U,W)^2
      \leq\dHG(U,W)^2+9\delta.
    \end{split}
  \end{equation*}
  Thus~({\it ii\/}) follows.
\end{proof}

In what follows, a constant~$0<\epsilon\leq1/2$ and a spanning
subgraph~$H\subset G$ of~$G$ is fixed. Also, we let~$P=(C_i)_0^k$ be an
$(\epsilon,k)$-equitable partition of~$V=V(G)$ refining~$P_0$,
where~$4^k\geq\epsilon^{-5}$.  Moreover, we assume
that~$\eta\leq\eta_0=\eta_0(k)=1/k4^{k+1}$ and that~$n=|G|\geq
n_0=n_0(k)=k4^{1+2k}$.

We now define an equitable partition~$Q=Q(P)$ of~$V=V(G)$ from~$P$ as
follows. First, for each $(\epsilon,H,G)$-irregular pair~$(C_s,C_t)$ of~$P$ 
with~$1\leq s<t\leq k$, we choose~$X=X(s,t)\subset C_s$, $Y=Y(s,t)\subset C_t$
such that ({\it i\/})~$|X|$, $|Y|\geq\epsilon|C_s|=\epsilon|C_t|$, and ({\it
ii\/})~$|\dHG(X,Y)-\dHG(C_s,C_t)|\geq\epsilon$. For fixed~$1\leq s\leq k$, the
sets~$X(s,t)$ in
$$
\{X=X(s,t)\subset C_s:1\leq t\leq k
      \hbox{ and~$(C_s,C_t)$ is not $(\epsilon,H,G)$-regular}\}
$$
define a natural partition of~$C_s$ into at most~$2^{k-1}$ blocks. Let us call
such blocks the {\deffont atoms\/} of~$C_s$. Now let~$q=4^k$ and
set~$m=\lfloor|C_s|/q\rfloor$ ($1\leq s\leq k$). Note
that~$\lfloor|C_s|/m\rfloor=q$ as~$|C_s|\geq n/2k\geq2q^2$. Moreover, for
later use, note that~$m\geq\eta n$. We now let~$Q'$ be a partition of~$V=V(G)$
refining~$P$ such that ({\it i\/})~$C_0$ is a block of~$Q'$, ({\it ii\/})~all
other blocks of~$Q'$ have cardinality~$m$, except for possibly one, which has
cardinality at most~$m-1$, ({\it iii\/})~for all~$1\leq s\leq k$, every
atom~$A\subset C_s$ contains exactly~$\lfloor|A|/m\rfloor$ blocks of~$Q'$,
({\it iv\/})~for all~$1\leq s\leq k$, the set~$C_s$ contains
exactly~$q=\lfloor|C_s|/m\rfloor$ blocks of~$Q'$.

Let~$C'_0$ be the union of the blocks of~$Q'$ that are not contained in any
class~$C_s$ ($1\leq s\leq k$), and let~$C'_i$ ($1\leq i\leq k'$) be the
remaining blocks of~$Q'$. We are finally ready to define our equitable
partition~$Q=Q(P)$: we let~$Q=(C'_i)_1^{k'}$. 

\begin{lemma}
  \label{lem:LemmaC}
  The partition~$Q=Q(P)=(C'_i)_0^{k'}$ defined from~$P$ as above is a
  $k'$-equitable partition of~$V=V(G)$ refining~$P$, where~$k'=kq=k4^k$,
  and~$|C'_0|\leq|C_0|+n4^{-k}$.
\end{lemma}
\begin{proof}
  Clearly~$Q$ refines~$P$. Moreover, clearly~$m=|C'_1|=\ldots=|C'_{k'}|$ and,
  for all~$1\leq s\leq k$, we
  have~$|C'_0|\leq|C_0|+k(m-1)\leq|C_0|+k|C_s|/q\leq|C_0|+n4^{-k}$.
\end{proof}

In what follows, for~$1\leq s\leq k$, we let~$C_s(i)$ ($1\leq i\leq q$) be the
classes of~$Q'$ that are contained in the class~$C_s$ of~$P$. Also, for
all~$1\leq s\leq k$, we set~$C_s^*=\bigcup_{1\leq i\leq q}C_s(i)$.  Now
let~$1\leq s\leq k$ be fixed. Note
that~$|C_s^*|\geq|C_s|-(m-1)\geq|C_s|-q^{-1}|C_s|\geq|C_s|(1-q^{-1})$.
As~$q^{-1}\leq10^{-2}$ and~$q^{-1}|C_s|\geq m\geq\eta n$, by
Lemma~\ref{lem:LemmaB} we have, for all~$1\leq s<t\leq k$,
\begin{equation}
  \label{eq:S}
  |\dHG(C_s^*,C_t^*)-\dHG(C_s,C_t)|\leq5q^{-1} 
\end{equation}
and
\begin{equation}
  \label{eq:SS}
  |\dHG(C_s^*,C_t^*)^2-\dHG(C_s,C_t)^2|\leq9q^{-1}.
\end{equation}

\subsection{Defect form of the Cauchy--Schwarz inequality}
\label{sec:CS}
As in~\cite{szemeredi76}, the following `defect' form of the Cauchy--Schwarz
inequality will be used in the proof of Theorem~\ref{thm:SSz}.

\begin{lemma}
  \label{lem:LemmaDefCS}
  Let~$y_1,\ldots,y_v\geq0$ be given.  Suppose~$0\leq\rho=u/v<1$,
  and~$\sum_{1\leq i\leq u}y_i=\alpha\rho\sum_{1\leq i\leq v}y_i$.  Then
  \begin{equation}
    \label{eq:lemmaDefCSConcl}
    \sum_{1\leq i\leq v}y_i^2
     \geq{1\over v}\(1+(\alpha-1)^2{\rho\over1-\rho}\)
      \bigg\{\sum_{1\leq i\leq v}y_i\bigg\}^2.
  \end{equation}
\end{lemma}

Since it is for the same price, we prove a weighted version of
Lemma~\ref{lem:LemmaDefCS}.  The statement and proof of
Lemma~\ref{lem:LemmaDefCSFR} below are from~\cite{frankl_rodl00:_extrem} (see
also~\cite{frankl92,szemeredi76}).

\begin{lemma}
  \label{lem:LemmaDefCSFR}
  Let $\sigma_i$ and~$d_i$ $(i\in I)$ be non-negative reals with
  $\sum_{i\in I}\sigma_i=1$.  Set $d=\sum_{i\in I}\sigma_id_i$.  Let $J\subset
  I$ be a proper subset of~$I$ such that $\sum_{j\in J}\sigma_j=\sigma<1$ and
  $$ 
  \sum_{j\in J}\sigma_jd_j=\sigma(d+\mu). 
  $$  
  Then
  \begin{equation}
    \label{eq:lemmaDefCSFRConcl}
    \sum_{i\in I}\sigma_id_i^2\geq d^2+\frac{\mu^2\sigma}{1-\sigma}.
  \end{equation}
%   In particular, if $\sigma\geq\delta$ and $|\mu|\geq\delta$ for some
%   $\delta>0$, then
%   $$
%    \sum_{i\in I}\sigma_id_i^2\geq d^2+\delta^3.
%   $$
\end{lemma}
\begin{proof}
  Let $\bfu_J=\(\sqrt{\sigma_j}\)_{j\in J}$,
  $\bfv_J=\(\sqrt{\sigma_j}d_j\)_{j\in J}$,
  $\bfu_{I\setminus J}=\(\sqrt{\sigma_i}\)_{i\in I\setminus J}$, and
  $\bfv_{I\setminus J}=\(\sqrt{\sigma_i}d_i\)_{i\in I\setminus J}$.
  
  We use the Cauchy--Schwarz inequality in the form
  $|\<\bfx,\bfy\>|^2\leq\|\bfx\|^2\|\bfy\|^2$.  Taking~$\bfx=\bfu_J$
  and~$\bfy=\bfv_J$ and~$\bfx=\bfu_{I\setminus J}$ and~$\bfy=\bfv_{I\setminus
    J}$, respectively, we infer that
  $$ 
  \bigg(\sum_{j\in J}\sigma_jd_j\bigg)^2
   \leq\sum_{j\in J}\sigma_j\sum_{j\in J}\sigma_jd_j^2, 
  $$  
  and
  $$ 
  \bigg(\sum_{i\in I\setminus J}\sigma_id_i\bigg)^2
   \leq\sum_{i\in I\setminus J}\sigma_i\sum_{i\in I\setminus J}\sigma_id_i^2.
  $$
  Therefore
  \begin{multline*}
    \sum_{i\in I}\sigma_id_i^2\geq\frac1\sigma
      \bigg(\sum_{j\in J}\sigma_jd_j\bigg)^2
      +\frac1{1-\sigma}\bigg(\sum_{i\in I-J}\sigma_id_i\bigg)^2\\
      =\sigma(d+\mu)^2+(1-\sigma)\(d-\frac{\sigma\mu}{1-\sigma}\)^2 
      =d^2+\frac{\mu^2\sigma}{1-\sigma},
  \end{multline*}
  as required.  
\end{proof}

\begin{proof}[Proof of Lemma~\ref{lem:LemmaDefCS}]
  To prove Lemma~\ref{lem:LemmaDefCS}, simply take~$\sigma_i=1/v$
  and~$d_i=y_i$ ($1\leq i\leq v$) in Lemma~\ref{lem:LemmaDefCSFR}.
  Then~$d=v^{-1}\sum_{1\leq i\leq v}y_i$, $\sigma=\rho$,
  and~$\mu=(\alpha-1)d$.  Inequality~\eqref{eq:lemmaDefCSFRConcl} then reduces
  to~\eqref{eq:lemmaDefCSConcl}.
\end{proof}

\subsection{The index of a partition}
\label{sec:index}
Similarly to~\cite{szemeredi76}, we define the {\deffont index\/}~$\ind(R)$ of
an equitable partition~$R=(C_i)_0^r$ of~$V=V(G)$ to be
$$
\ind(R)={2\over r^2}\sum_{1\leq i<j\leq\ell}\dHG(C_i,C_j)^2.
$$
Note that trivially~$0\leq\ind(R)<1$.

\subsection{The index of subpartitions}
\label{sec:index_of_subpartitions}
Our aim now is to show that, for~$Q=Q(P)$ defined as above, we
have~$\ind(Q)\geq\ind(P)+\epsilon^5/100$.

\subsubsection{The draw case}
We start with the following lemma.

\begin{lemma}
  \label{lem:LemmaD}
  Suppose~$1\leq s<t\leq k$. Then
  $$
  {1\over q^2}\sum_{i,\,j=1}^q\dHG(C_s(i),C_t(j))^2
  \geq\dHG(C_s,C_t)^2-{\epsilon^5\over100}.
  $$
\end{lemma}
\begin{proof}
  By the $(P_0,\eta)$-uniformity of~$G$ and the fact that~$(C_s,C_t)\prec
  P_0$, we have
  \begin{equation*}
    \begin{split}
      {1\over q^2}\sum_{1\leq i\leq q}\sum_{1\leq j\leq q}&\dHG(C_s(i),C_t(j))
      ={1\over q^2}\sum_{i,\,j}{\eH(C_s(i),C_t(j))\over\eG(C_s(i),C_t(j))}\cr
      &\qquad\geq\sum_{i,\,j}{\eH(C_s(i),C_t(j))\over(1+\eta)q^2p|C_s(i)||C_t(j)|}
      ={\eH(C_s^*,C_t^*)\over(1+\eta)p|C_s^*||C_t^*|}\cr
      &\qquad\geq{1-\eta\over1+\eta}\dHG(C_s^*,C_t^*)
      \geq\dHG(C_s^*,C_t^*)-2\eta.
    \end{split}
  \end{equation*}
  Thus, by the Cauchy--Schwarz inequality, we have
  $$
  {1\over q^2}\sum_{1\leq i\leq q}\sum_{1\leq j\leq q}\dHG(C_s(i),C_t(j))^2
  \geq\dHG(C_s^*,C_t^*)^2-4\eta.
  $$
  Furthermore, by~\eqref{eq:SS}, we
  have~$\dHG(C_s^*,C_t^*)^2\geq\dHG(C_s,C_t)^2-9q^{-1}$.  Since we
  have~$9q^{-1}+4\eta\leq\epsilon^5/100$, the lemma follows.
\end{proof}

\subsubsection{The winning case}
The inequality in Lemma~\ref{lem:LemmaD} may be improved if~$(C_s,C_t)$ is an
$(\epsilon,H,G)$-irregular pair, as shows the following result.

\begin{lemma}
  \label{lem:LemmaE}
  Let~$1\leq s<t\leq k$ be such that~$(C_s,C_t)$ is not
  $(\epsilon,H,G)$-regular. Then
  $$
  {1\over q^2}\sum_{i,\,j=1}^q\dHG(C_s(i),C_t(j))^2
  \geq\dHG(C_s,C_t)^2+{\epsilon^4\over40}-{\epsilon^5\over100}.
  $$
\end{lemma}
\begin{proof}
  Let~$X=X(s,t)\subset C_s$, $Y=Y(s,t)\subset C_t$ be as in the definition
  of~$Q$. Let~$X^*\subset X$ be the maximal subset of~$X$ that is the union of
  blocks of~$Q$, and similarly for~$Y^*\subset Y$. Without loss of generality,
  we may assume that~$X^*=\bigcup_{1\leq i\leq q_s}C_s(i)$,
  and~$Y^*=\bigcup_{1\leq j\leq q_t}C_t(j)$. Note
  that~$|X^*|\geq|X|-2^{k-1}(m-1)\geq|X|(1-2^{k-1}m/|X|)
  \geq|X|(1-2^{k-1}/q\epsilon)=|X|(1-1/\epsilon2^{k+1})$, and
  similarly~$|Y^*|\geq|Y|(1-1/\epsilon2^{k+1})$. However, we
  have~$1/\epsilon2^{k+1}\leq10^{-2}$ and~$|X|/\epsilon2^{k+1}$,
  $|Y|/\epsilon2^{k+1}\geq\eta n$.  Thus, by Lemma~\ref{lem:LemmaB}, we
  have~$|\dHG(X^*,Y^*)-\dHG(X,Y)|\leq5/\epsilon2^{k+1}$. Moreover,
  by~\eqref{eq:S}, we have~$|\dHG(C_s^*,C_t^*)-\dHG(C_s,C_t)|\leq5q^{-1}$.
  Since~$|\dHG(X,Y)-\dHG(C_s,C_t)|\geq\epsilon$
  and~$5q^{-1}+5/\epsilon2^{k+1}\leq\epsilon/2$, we have
  \begin{equation}
    \label{eq:SSS}
    |\dHG(X^*,Y^*)-\dHG(C_s^*,C_t^*)|\geq\epsilon/2.     
  \end{equation}
  For later reference, let us note
  that~$q_sm=|X^*|\geq|X|-2^{k-1}m\geq\epsilon|C_s|-2^{k-1}m\geq\epsilon
  qm-2^{k-1}m$, and hence~$q_s\geq\epsilon q-2^{k-1}\geq\epsilon q/2$.
  Similarly, we have~$q_t\geq\epsilon q/2$. Let us now
  set~$y_{ij}=\dHG(C_s(i),C_t(j))$ for~$i$, $j=1,\ldots,q$. In the proof of
  Lemma~\ref{lem:LemmaD} we checked that
  $$
  \sum_{1\leq i\leq q}\sum_{1\leq j\leq q}y_{ij}
  \geq{1-\eta\over1+\eta}q^2\dHG(C_s^*,C_t^*)
  \geq(1-2\eta)q^2\dHG(C_s^*,C_t^*).
  $$
  Similarly, one has
  $$\sum_{1\leq i\leq q}\sum_{1\leq j\leq
    q}y_{ij}\leq(1+3\eta)q^2\dHG(C_s^*,C_t^*),
  $$
  $$\sum_{1\leq i\leq
    q_s}\sum_{1\leq j\leq q_t}y_{ij}\geq(1-2\eta)q_sq_t\dHG(X^*,Y^*),
  $$
  and
  $$\sum_{1\leq i\leq q_s}\sum_{1\leq j\leq q_t}y_{ij}\leq
  (1+3\eta)q_sq_t\dHG(X^*,Y^*).
  $$
  Let us set~$\rho=q_sq_t/q^2\geq\epsilon^2/4$,
  and~$\dstS=\dHG(C_s^*,C_t^*)$. We now note that by~\eqref{eq:SSS} we either
  have
  \begin{equation*}
    \begin{split}
      \sum_{1\leq i\leq q_s}\sum_{1\leq j\leq q_t}y_{ij}
    \geq{1-2\eta\over1+3\eta} \cdot{q_sq_t\over
      q^2}\(1+{\epsilon\over2(\dstS)^2}\) \sum_{1\leq i\leq q}\sum_{1\leq
      j\leq q}y_{ij}\qquad&\cr \qquad\geq\rho\(1+{\epsilon\over3(\dstS)^2}\)
    \sum_{1\leq i\leq q}\sum_{1\leq j\leq q}y_{ij}&,  
    \end{split}
  \end{equation*}
or else
\begin{equation*}
  \begin{split}
    \sum_{1\leq i\leq q_s}\sum_{1\leq j\leq q_t}y_{ij}
    \leq{1+3\eta\over1-2\eta} \cdot{q_sq_t\over
      q^2}\(1-{\epsilon\over2(\dstS)^2}\) \sum_{1\leq i\leq q}\sum_{1\leq
      j\leq q}y_{ij}\qquad&\cr \leq\rho\(1-{\epsilon\over3(\dstS)^2}\)
    \sum_{1\leq i\leq q}\sum_{1\leq j\leq q}y_{ij}&.
  \end{split}
\end{equation*}
We may now apply Lemma~\ref{lem:LemmaDefCS} to conclude that
\begin{equation*}
  \begin{split}
    \sum_{1\leq i\leq q}\sum_{1\leq j\leq q}y_{ij}^2 &\geq{1\over
      q^2}\(1+{\epsilon^2\over9(\dstS)^2}\cdot{\rho\over1-\rho}\)
    \bigg\{\sum_{1\leq i\leq q}\sum_{1\leq j\leq q}y_{ij}\bigg\}^2 \cr
    &\geq{1\over q^2}\(1+{\epsilon^2\rho\over9(\dstS)^2}\)
    \big\{q^2(1-2\eta)\dstS\big\}^2\cr &\quad\qquad\geq
    q^2(1-4\eta)\((\dstS)^2+{\epsilon^2\rho\over9}\) \geq
    q^2\((\dstS)^2+{\epsilon^2\rho\over10}-4\eta\).
  \end{split}
\end{equation*}
Therefore
\begin{equation*}
  \begin{split}
    {1\over q^2}\sum_{1\leq i\leq q}
    &\sum_{1\leq j\leq q}\dHG(C_s(i),C_t(j))^2
      \geq\dHG(C_s^*,C_t^*)^2+{\epsilon^2\rho\over10}-4\eta \cr
      &\geq\dHG(C_s,C_t)^2+{\epsilon^4\over40}-(9\eta^{-1}+4\eta) 
        \geq\dHG(C_s,C_t)^2+{\epsilon^4\over40}-{\epsilon^5\over100},
  \end{split}
\end{equation*}
as required.
\end{proof}

\subsection{Proof of Theorem~\ref{thm:SSz}}
\label{sec:pf_of_thm}
We are now ready to prove the main lemma needed in the proof of
Theorem~\ref{thm:SSz}.

\begin{lemma}
  \label{lem:LemmaF}
  Suppose~$k\geq1$ and~$0<\epsilon\leq1/2$ are such
  that~$4^k\geq1800\epsilon^{-5}$. Let~$G=G^n$ be a $(P_0,\eta)$-uniform graph
  of order~$n\geq n_0=n_0(k)=k4^{2k+1}$, where~$P_0=(V_i)_1^\ell$ is a
  partition of~$V=V(G)$, and assume
  that~$\eta\leq\eta_0=\eta_0(k)=1/k4^{k+1}$.  Let~$H\subset G$ be a spanning
  subgraph of~$G$. If~$P=(C_i)_0^k$ is an $(\epsilon,H,G)$-irregular
  $(\epsilon,k)$-equitable partition of~$V=V(G)$ refining~$P_0$, then there is
  a $k'$-equitable partition~$Q=(C'_i)_0^{k'}$ of~$V$ such that {\rm({\it
    i\/})}~$Q$~refines~$P$, {\rm({\it ii\/})}~$k'=k4^k$, {\rm({\it
    iii\/})}~$|C_0'|\leq|C_0|+n4^{-k}$, and {\rm({\it
    iv\/})}~$\ind(Q)\geq\ind(P)+\epsilon^5/100$.
\end{lemma}
\begin{proof}
  Let~$P$ be as in the lemma. We show that the $k'$-equitable
  partition~$Q=(C'_i)_0^{k'}$ defined from~$P$ as above satisfies~({\it
    i\/})--({\it iv\/}). In view of Lemma~\ref{lem:LemmaC}, it only remains to
  check~({\it iv\/}). By Lemmas~\ref{lem:LemmaD} and~\ref{lem:LemmaE}, we have
  \begin{equation*}
    \begin{split}
      \ind(Q)
      &={2\over(kq)^2}\sum_{1\leq i\leq q}\sum_{1\leq j\leq q}
      \dHG(C'_i,C'_j)^2 \cr
      &\geq{2\over k^2}\sum_{1\leq s<t\leq k}{1\over q^2}
         \sum_{1\leq i\leq q}\sum_{1\leq j\leq q}\dHG(C_s(i),C_t(j))^2\cr
      &\geq{2\over k^2}
        \Bigg\{\sum_{1\leq s<t\leq k}\(\dHG(C_s,C_t)^2-{\epsilon^5\over100}\)
          +\epsilon{k\choose2}{\epsilon^4\over40}
        \Bigg\}\cr
      &\qquad\geq\ind(P)-{\epsilon^5\over100}+{\epsilon^5\over50}
      \geq\ind(P)+{\epsilon^5\over100}.\cr
    \end{split}
  \end{equation*}
This completes the proof of the lemma.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:SSz}]
  Let~$\epsilon>0$, $k_0\geq1$, and~$\ell\geq1$ be given. We may assume
  that~$\epsilon\leq1/2$. Pick~$s\geq1$ such
  that~$4^{s/4\ell}\geq1800\epsilon^{-5}$, $s\geq\max\{2k_0,3\ell/\epsilon\}$,
  and~$\epsilon4^{s-1}\geq1$. Let~$f(0)=s$, and put
  inductively~$f(t)=f(t-1)4^{f(t-1)}$ ($t\geq1$).
  Let~$t_0=\lfloor100\epsilon^{-5}\rfloor$ and set~$N=\max\{n_0(f(t)):0\leq
  t\leq t_0\}=f(t_0)4^{2f(t_0)+1}$, $K_0=\max\{6\ell/\epsilon,N\}$,
  and~$\eta=\eta(\epsilon,k_0,\ell)=\min\{\eta_0(f(t)):0\leq t\leq
  t_0\}=1/4f(t_0+1)>0$.  Finally, we take~$N_0=N_0(\epsilon,k_0,\ell)=K_0$.
  We claim that~$\eta$, $K_0$, and~$N_0$ as defined above will do.
  
  To prove our claim, let~$G=G^n$ be a fixed $(P_0,\eta)$-uniform graph
  with~$n\geq N_0$, where~$P_0=(V_i)_1^\ell$ is a partition of~$V=V(G)$.
  Furthermore, let~$H\subset G$ be a spanning subgraph of~$G$.  We have~$n\geq
  N_0=K_0$.  Suppose~$t\geq0$. Let us say that an equitable
  partition~$P^{(t)}=(C_i)_0^k$ of~$V$ is {\deffont$t$-valid\/} if ({\it
    i\/})~$P^{(t)}$ refines~$P_0$, ({\it ii\/})~$s/4\ell\leq k\leq f(t)$,
  ({\it iii\/})~$\ind\{P^{(t)}\}\geq t\epsilon^5/100$, and ({\it
    iv\/})~$|C_0|\leq\epsilon n(1-2^{-(t+1)})$. We now verify that a $0$-valid
  partition~$P^{(0)}$ of~$V$ does exist. Let~$m=\lceil n/s\rceil$, and let~$Q$
  be a partition of~$V$ with all blocks of cardinality~$m$, except for
  possibly one, which has cardinality at most~$m-1$, and moreover such that
  each~$V_i$ ($1\leq i\leq\ell$) contains~$\lfloor|V_i|/m\rfloor$ blocks
  of~$Q$. Grouping at most~$\ell$ blocks of~$Q$ into a single block~$C_0$, we
  arrive at an equitable partition~$P^{(0)}=(C_i)_0^k$ of~$V$ that is
  $0$-valid. Indeed, ({\it i\/})~is clear, and to check~({\it ii\/}) note
  that~$k\leq n/m\leq s=f(0)$, and that there is~$1\leq i\leq\ell$ such
  that~$|V_i|\geq n/\ell$, and
  so~$k\geq\lfloor|V_i|/m\rfloor\geq\lfloor(n/\ell)/\lceil
  n/s\rceil\rfloor\geq(1/2)\{(n/\ell)/(2n/s)\}=s/4\ell$. Also, ({\it
    iii\/})~is trivial and~({\it iv\/}) does follow, since~$|C_0|<\ell
  m\leq\ell\lceil n\epsilon/3\ell\rceil\leq n\epsilon/2$ as~$n\geq
  K_0\geq6\ell/\epsilon$.
  
  Now note that if there is a $t$-valid partition~$P^{(t)}$ of~$V$,
  then~$t\leq t_0=\lfloor100\epsilon^{-5}\rfloor$,
  since~$\ind\{P^{(t)}\}\leq1$.  Suppose~$t$ is the maximal integer for which
  there is a $t$-valid partition~$P^{(t)}$ of~$V$. We claim that~$P^{(t)}$ is
  $(\epsilon,H,G)$-regular.  Suppose to the contrary that~$P^{(t)}$ is not
  $(\epsilon,H,G)$-regular.  Then simply note that Lemma~\ref{lem:LemmaF}
  gives a $(t+1)$-valid equitable partition~$P^{(t+1)}=Q=Q(P^{(t)})$,
  contradicting the maximality of~$t$.  This completes the proof of
  Theorem~\ref{thm:SSz}.
\end{proof}

\section{Local conditions for regularity}
\label{sec:local}

As briefly discussed in the introduction, our aim in this section is to
discuss a well-known `local' condition for regularity.  It should be stressed
that in Sections~\ref{sec:local} and~\ref{sec:checking}, we are concerned with
dense graphs, that is, we are in the context of the original regularity lemma.
(See Section~\ref{sec:sparse_local_condition} for a very brief discussion on
extensions of the results in Section~\ref{sec:local} to the sparse case.)

\subsection{The basic argument}
\label{sec:lindsey}
In this section, we give a result of Lindsey (see the proof of the upper bound
in Theorem~15.2 in~\cite{erd74:_probab}) because it contains one of the key
ideas used in developing local conditions for regularity.

Let~$H=(h_{ij})$ be an $n$~by~$n$ Hadamard matrix.  Thus~$H$ is a
$\{\pm1\}$-matrix whose rows are pairwise orthogonal.  Let
\begin{equation}
  \label{eq:dev_def}
  \disc(H;a,b)=\max_{I,J}\bigg|\sum_{i\in I,\,j\in J}h_{ij}\bigg|, 
\end{equation}
where the maximum is taken over all sets of rows~$I$ and all sets of
columns~$J$ with~$|I|=a$ and~$|J|=b$.  We also let the \textit{discrepancy}
of~$H$ be
\begin{equation}
  \label{eq:dev_def2}
  \disc(H)=\max_{a,b}\disc(H;a,b),
\end{equation}
where the maximum is taken over all~$1\leq a\leq n$ and~$1\leq b\leq n$.

\begin{theorem}
  \label{thm:lindsey}
  For any $n$~by~$n$ Hadamard matrix~$H$, and any~$1\leq a\leq n$ and~$1\leq
  b\leq n$, we have
  \begin{equation}
    \label{eq:lindsey_thm}
    \disc(H;a,b)\leq\sqrt{abn}.
  \end{equation}
\end{theorem}
\begin{proof}
  Let the rows of~$H$ be~$\bfv_1,\dots,\bfv_n$, and fix~$a$ and~$b$.  Suppose,
  without loss of generality, that~$I=\{1,\dots,a\}$ and~$J=\{1,\dots,b\}$.
  Let also~$\bfone_J=(1,\dots,1,0,\dots)^T\in\RR^n$ be the characteristic
  vector of~$J$.  By the Cauchy--Schwarz inequality, we have
  \begin{equation}
    \label{eq:lindsey1}
    \bigg|\sum_{I,J}h_{ij}\bigg|
    =\bigg|\bigg\langle\sum_{i\in I}\bfv_i,\bfone_J\bigg\rangle\bigg|
    \leq\bigg\|\sum_{i\in I}\bfv_i\bigg\|\sqrt{|J|}
    =\bigg\|\sum_{i\in I}\bfv_i\bigg\|\sqrt b.
  \end{equation}
  From the pairwise orthogonality of the vectors~$\bfv_i$, we have
  \begin{equation}
    \label{eq:lindsey_ortho}
    \bigg\|\sum_{i\in I}\bfv_i\bigg\|=\sqrt{\sum_{i\in I}\|\bfv_i\|^2}
    =\sqrt{n|I|}=\sqrt{na}.  
  \end{equation}
  Plugging~\eqref{eq:lindsey_ortho} into~\eqref{eq:lindsey1}, we have
  \begin{equation*}
    \bigg|\sum_{I,J}h_{ij}\bigg|
    \leq\sqrt{abn},
  \end{equation*}
  and the result follows. 
\end{proof}

\begin{corollary}
  \label{cor:lindsey}
  The discrepancy~$\disc(H)$ of an $n$~by~$n$ Hadamard matrix~$H$ satisfies
  $\disc(H)\leq n^{3/2}$.%\hfill\qed
%   \begin{equation*}
%     \label{eq:lindsey2}
%     \disc(H)\leq n^{3/2}.%\eqno\qed
%   \end{equation*}
\end{corollary}

An easy generalization of Theorem~\ref{thm:lindsey} above concerns the case in
which we weaken the condition that the rows of~$H$ should be precisely
orthogonal.  Let us say that two vectors~$u$, $v\in\RR^n$ are
\textit{$\epsilon$-quasi-orthogonal} if~$|\<u,v\>|\leq\epsilon n$.  Our next
result roughly states that if the rows of an $n$~by~$n$ matrix~$H$ are
$o(1)$-quasi-orthogonal, then the discrepancy of~$H$ is~$o(n^2)$.

\begin{theorem}
  \label{thm:lindsey2}
  Let~$\delta>0$ be fixed and let~$H$ be an $n$~by~$n$ matrix whose
  rows~$\bfv_i$ $(1\leq i\leq n)$ are $\delta$-quasi-orthogonal
  and~$\|\bfv_i\|\leq\sqrt n$ for all~$1\leq i\leq n$.  Then
  \begin{equation}
    \label{eq:lindsey_thm2}
    \disc(H;a,b)\leq n^2\sqrt{2\delta}
  \end{equation}
  for all~$a\geq1/\delta$ and all~$b\geq1$.
\end{theorem}
\begin{proof}
  We proceed exactly in the same manner as in the proof of
  Theorem~\ref{thm:lindsey}.  However, instead of~\eqref{eq:lindsey_ortho}, we
  observe that 
  \begin{equation}
    \label{eq:lindsey_quasi_ortho}
    \bigg\|\sum_{i\in I}\bfv_i\bigg\|^2
    =\bigg\langle\sum_{i\in I}\bfv_i,\sum_{i\in I}\bfv_i\bigg\rangle
    =\sum_{i\in I}\<\bfv_i,\bfv_i\>+\sum_{i\neq j}\<\bfv_i,\bfv_j\>,
  \end{equation}
  where the last sum is over all~$i\neq j$ with~$i$, $j\in I$.  The result now
  follows from the hypotheses on the~$\|\bfv_i\|$ and on
  the~$\<\bfv_i,\bfv_j\>$.  Indeed, the right-hand side
  of~\eqref{eq:lindsey_quasi_ortho} is at most
  \begin{equation}
    \label{eq:add_sketch}
    an+2{a\choose2}\delta n\leq a^2\delta n\(1+{1\over
    a\delta}\)\leq2a^2\delta n.
  \end{equation}
  Therefore, the right-hand side of~\eqref{eq:lindsey1} is at
  most~$\sqrt{2a^2b\delta n}\leq n^2\sqrt{2\delta}$.
  Theorem~\ref{thm:lindsey2} follows. 
\end{proof}

Before we proceed, let us observe that, in fact, the hypothesis of
$\delta$-quasi-ortho\-gon\-ality of the~$\bfv_i$ ($1\leq i\leq n$) in
Theorem~\ref{thm:lindsey2} may be further weakened to
\begin{equation}
  \label{eq:quasi_ortho_weakened}
  \<\bfv_i,\bfv_j\>\leq\delta n
  \text{ for all }i\neq j\text{ with }
  1\leq i,\,j\leq n.
\end{equation}
Indeed, hypothesis~\eqref{eq:quasi_ortho_weakened} above suffices for us to
estimate the last sum in~\eqref{eq:lindsey_quasi_ortho}.  The reader may also
observe that, in fact, it suffices to require that the inequality
in~\eqref{eq:quasi_ortho_weakened} should hold for \textit{most}
pairs~$\{i,j\}$ with~$i\neq j$, with little loss in the
conclusion~\eqref{eq:lindsey_thm2}.  We omit the details.

Finally, let us observe that Theorem~\ref{thm:lindsey} concerns matrices in
which the number of~$+1$s is about the same as the number of~$-1$s, and hence
the average entry is about~$0$.  In general, we shall be interested in the
case in which the rows of our matrix are pairwise quasi-orthogonal (or, more
generally, the rows satisfy~\eqref{eq:quasi_ortho_weakened}), the average
entry is about~$0$, but the entries are not necessarily~$\pm1$.  Adapting
carefully the argument in the proof of Theorem~\ref{thm:lindsey} to this more
general case gives Lemma~\ref{lem:prop2}, to be discussed in the
Section~\ref{sec:general}.

\subsection{The converse}
\label{sec:converse}
In the previous section, we proved that the pairwise orthogonality of the rows
of a $\{\pm1\}$-matrix has as a somewhat unexpected consequence the fact that
the matrix must have small discrepancy.  In this section, we prove
that~$o(n^2)$ discrepancy for an $n$~by~$n$ matrix implies the existence of
only~$o(n^2)$ pairs of rows that are `substantially' non-orthogonal (in fact,
we prove that the number of pairs~$\{i,j\}$ violating the condition
in~\eqref{eq:quasi_ortho_weakened} is~$o(n^2)$).  Thus, roughly speaking, we
shall prove the converse of the results in Section~\ref{sec:lindsey}.

\begin{theorem}
  \label{thm:lindsey_conv}
  Let~$\delta>0$ be a real number and let~$H=(h_{ij})$ be an $n$~by~$n$ matrix
  with entries in~$\{\pm1\}$.  Let the rows of~$H$ be~$\bfv_i$ $(1\leq i\leq
  n)$.  Let~$D$ be the graph on~$V=V(D)=[n]=\{1,\dots,n\}$ whose edges are the
  pairs~$\{i,j\}$ $(i\neq j)$ for which we have
  \begin{equation}
    \label{eq:lindsey_conv}
    \<\bfv_i,\bfv_j\>>\delta n.
  \end{equation}
  If~$D$ is such that~$e(D)=|E(D)|\geq\delta n^2$, then
  \begin{equation}
    \label{eq:lindsey_conv_conclusion}
    \disc(H)>{1\over2}\delta^2n^2.
  \end{equation}
\end{theorem}

Before we give the proof of Theorem~\ref{thm:lindsey_conv}, let us give the
underlying argument in its simplest form.  Let us suppose that we have the
following convenient set-up:
\begin{equation}
  \label{eq:simplifying_hypothesis}
  \bfv_1=\bfone=(1,\dots,1)\in\RR^n
\end{equation}
and
\begin{equation}
  \label{eq:eq:lindsey_conv}
  \<\bfv_1,\bfv_i\>=\Omega(n).  
\end{equation}
for all~$i\in I$, where~$|I|=\Omega(n)$.  Clearly, we may
restate~\eqref{eq:eq:lindsey_conv} by saying that all the vectors~$\bfv_i$
($i\in I$) have a `surplus' of~$+1$s of order~$\Omega(n)$.  Since we
have~$|I|=\Omega(n)$ such vectors~$\bfv_i$, if we sum all the entries of
these~$\bfv_i$ we obtain a discrepancy of~$\Omega(n^2)$.

To prove Theorem~\ref{thm:lindsey_conv}, we concentrate our attention on a
vertex of high degree in~$D$, and we consider a subset of the columns of~$H$
so that the simplifying hypothesis~\eqref{eq:simplifying_hypothesis} holds.

\begin{proof}[Proof of Theorem~\ref{thm:lindsey_conv}]
  We start by noticing that the average degree of~$D$ is~$\geq2\delta n$.
  Let~$i_0\in[n]=V(D)$ be a vertex of~$D$ with degree~$\geq2\delta n$.  We
  let~$I$ be the neighbourhood~$\Gamma(i_0)$ of~$i_0$ in~$D$.  Therefore, 
  \begin{equation}
    \label{eq:I_size_lwbd}
    |I|\geq2\delta n.
  \end{equation}
  For~$\alpha\in\{+,-\}$, let
  \begin{equation}
    \label{eq:J_alpha_def}
    J_\alpha=\{j\in[n]\:h_{i_0j}=\alpha\}.
  \end{equation}
  Clearly, we have~$\bfv_{i_0}=\bfone_{J_+}-\bfone_{J_-}$, where we
  write~$\bfone_S$ for the characteristic vector of a set~$S$.  For
  any~$i\in[n]$ and~$\alpha\in\{+,-\}$, let~$\bfv_i^\alpha$ be the restriction
  of~$\bfv_i=(h_{ij})_{1\leq j\leq n}$ to~$J_\alpha$, that is,
  \begin{equation}
    \label{eq:bfv_i_alpha_def}
    \bfv_i^\alpha=(h_{ij})_{j\in J_\alpha}.
  \end{equation}
  For any~$i\in I=\Gamma(i_0)$, we have
  \begin{equation*}
    \<\bfv_{i_0}^+,\bfv_i^+\>
    +\<\bfv_{i_0}^-,\bfv_i^-\>
    =\<\bfv_{i_0},\bfv_i\>
    >\delta n.
  \end{equation*}
  Therefore, either
  \begin{equation}
    \label{eq:lwbd1}
    \<\bfone_{J_+},\bfv_i^+\>=\<\bfv_{i_0}^+,\bfv_i^+\>>{1\over2}\delta n,
  \end{equation}
  or else
  \begin{equation}
    \label{eq:lwbd2}
    \<-\bfone_{J_-},\bfv_i^-\>=\<\bfv_{i_0}^-,\bfv_i^-\>>{1\over2}\delta n.
  \end{equation}
  Let
  \begin{equation*}
    \label{eq:I_+_def}
    I_+=\{i\in I=\Gamma(i_0)\:\text{\eqref{eq:lwbd1} holds}\},
  \end{equation*}
  and let
  \begin{equation*}
    \label{eq:I_-_def}
    I_-=\{i\in I=\Gamma(i_0)\:\text{\eqref{eq:lwbd2} holds}\}.
  \end{equation*}
  Clearly, $I=\Gamma(i_0)=I_+\cup I_-$ and
  hence
  \begin{equation}
    \label{eq:I_alpha_lwbd}
    \max\{|I_+|,|I_-|\}\geq{1\over2}|I|\geq\delta n,
  \end{equation}
  where we used~\eqref{eq:I_size_lwbd}.  Let us now put~$S_\alpha=\sum h_{ij}$
  for~$\alpha\in\{+,-\}$, where the sum runs over all~$i\in I_\alpha$
  and~$j\in J_\alpha$.  Observe that then
  \begin{equation*}
    \label{eq:poss1}
    S_+=\sum\Big\{h_{ij}\:i\in I_+\text{, }j\in J_+\Big\}
    =\bigg\langle\sum_{i\in I_+}\bfv_i^+,\bfone_{J_+}\bigg\rangle
    >{1\over2}\delta n|I_+|,
  \end{equation*}
  and
  \begin{equation*}
    \label{eq:poss2}
    S_-=\sum\Big\{h_{ij}\:i\in I_-\text{, }j\in J_-\Big\}
    =\bigg\langle\sum_{i\in I_-}\bfv_i^-,\bfone_{J_-}\bigg\rangle
    <-{1\over2}\delta n|I_-|,
  \end{equation*}
  where the inequalities follow from~\eqref{eq:lwbd1} and~\eqref{eq:lwbd2}.
  We now observe that~\eqref{eq:I_alpha_lwbd} gives that
  \begin{equation}
    \label{eq:final_lwbd}
    \disc(H)\geq\max\{|S_+|,|S_-|\}
    >\max\{|I_+|,|I_-|\}{1\over2}\delta n
    \geq{1\over2}\delta^2n^2,
  \end{equation}
  which completes the proof.
\end{proof}

We shall discuss the `full' version of Theorem~\ref{thm:lindsey_conv} above in
Section~\ref{sec:necessary}.

\subsection{The general results}
\label{sec:general}

We now state the `general versions' of the results in
Sections~\ref{sec:lindsey} and~\ref{sec:converse}.  We
follow~\cite{DukeLefmannRodlcount}.  The results in this section are stated
for graphs instead of matrices.

\subsubsection{The sufficiency of the condition}
Recall that we write~$\Gamma(x)=\Gamma_G(x)$ for the neighbourhood of a
vertex~$x$ in a graph~$G$.  Moreover, if~$B\subset V(G)$ is a subset of
vertices of our graph~$G$, we write~$\deg_B(x)$ for the degree~$|\Gamma(x)\cap
B|$ of~$x$ into~$B$, and, similarly, we write~$\deg_B(x,x')$ for the `joint
degree' $|\Gamma(x)\cap\Gamma(x')\cap B|$ of~$x$ and~$x'$ into~$B$.

We now state the `full' version of Theorem~\ref{thm:lindsey2} (see also the
comment concerning the weaker hypothesis~\eqref{eq:quasi_ortho_weakened}).

\begin{theorem}
  \label{lem:prop2}
  Let~$\epsilon$ be a constant with $0<\epsilon<1$.  Let $G=(V,E)$ be a graph
  with $(A,B)$ a pair of disjoint, nonempty subsets of~$V$ with
  $|A|\geq2/\epsilon$.  Set $\rho=d(A,B)=e(A,B)/|A||B|$.  Let~$D$ be the
  collection of all pairs $\{x,x'\}$ of vertices of~$A$ for which
  \begin{enumerate}
  \item[(\textit{i})]$\deg_B(x)$, $\deg_B(x')>(\rho-\epsilon)|B|$, 
  \item[(\textit{ii})]$\deg_B(x,x^\prime)<(\rho+\epsilon)^2|B|$.
  \end{enumerate}
  Then if $|D|>(1/2)(1-5\epsilon)|A|^2$, the pair $(A,B)$ is
  $(16\epsilon)^{1/5}$-regular.  %\qed
\end{theorem}

We only give a brief sketch for the proof of Theorem~\ref{lem:prop2} here.  The
first step is to construct an $A$~by~$B$ `adjacency' matrix~$M$, whose entries
are~$-1$ and~$\lambda=(1-\rho)/\rho$.  A~$-1$ entry indicates the absence of
the edge and the entry~$\lambda$ indicates the presence of the edge.  It is
not difficult to check that the discrepancy of this matrix~$M$ is tightly
connected with the regularity of the pair~$(A,B)$.  Indeed, we have
\begin{equation}
  \label{eq:con_disc_reg}
  \disc(M;a',b')={1\over\rho}\max_{A',\,B'}\big|e(A',B')-\rho|A'||B'|\big|, 
\end{equation}
where the maximum is taken over all~$A'\subset A$ and~$B'\subset B$
with~$|A'|=a'$ and~$|B'|=b'$.  On the other hand, by making use of the
hypothesis on~$D$, a careful application of Lindsey's argument gives that
\begin{equation}
  \label{eq:hyp_D+Lindsey_gives}
  \disc(M;a',b')\leq{1\over\rho}(16\epsilon)^{1/5}a'b'
\end{equation}
for all~$a'\geq\epsilon|A|$ and~$b'\geq\epsilon|B|$.  Theorem~\ref{lem:prop2}
follows from~\eqref{eq:con_disc_reg} and~\eqref{eq:hyp_D+Lindsey_gives}.
See~\cite{DukeLefmannRodlcount} for the details.


\subsubsection{The necessity of the condition}
\label{sec:necessary}
We now turn to the converse of Theorem~\ref{lem:prop2}.  The `full' version of
Theorem~\ref{thm:lindsey_conv} is as follows.

\begin{theorem}
  \label{lem:prop3}
  Let $G=(V,E)$ be a graph with $(A,B)$ an $\epsilon$-regular pair of
  disjoint, nonempty subsets of~$V$, having density
  $d(A,B)=e(A,B)/|A||B|=\rho$, where $\rho|B|\geq1$ and~$0<\epsilon<1$.  Then
  \begin{enumerate}
  \item[(\textit{i})] all but at most $2\epsilon|A|$ vertices $x\in A$
    satisfy
    $$
    (\rho-\epsilon)|B|<\deg_B(x),\;\deg_B(x')<(\rho+\epsilon)|B|,
    $$
  \item[(\textit{ii})] all but at most $2\epsilon|A|^2$ pairs
    $\{x,x'\}$ of vertices of~$A$ satisfy
    $$
    \deg_B(x,x^\prime)<(\rho+\epsilon)^2|B|.%\eqno\qed
    $$
  \end{enumerate}
\end{theorem}

Theorem~\ref{lem:prop3} may be proved by adapting the proof of
Theorem~\ref{thm:lindsey_conv}.  See~\cite{DukeLefmannRodlcount} for the
details. 

\subsection{Algorithmic versions}
\label{sec:algo}
Let us briefly discuss some algorithmic aspects.  The reader is referred
to~\cite{kohayakawa00:_algor} for a survey.

In algorithmic applications of regularity, once an $\epsilon$-regular
partition is obtained, one typically makes use of constructive versions of
results such as the embedding lemma, Lemma~\ref{lem:embedding}.  The reader
will have no difficulty in observing that an efficient algorithm is implied in
the proof of Lemma~\ref{lem:embedding}.

The question is, then, whether $\epsilon$-regular partitions may be
constructed efficiently.  It turns out that this is indeed the
case~\cite{AlonDLRY92,alon94}.  The main tool to prove this is the local
characterization of regularity that we have been discussing in this section.
In fact, Theorems~\ref{lem:prop2} and~\ref{lem:prop3} imply
Lemma~\ref{lem:resolve_coNP_problem} below
(see~\cite{AlonDLRY92,alon94,DukeLefmannRodlcount}), which is the key
ingredient of the constructive version of the regularity lemma given
in~\cite{AlonDLRY92,alon94}.

Recall that a bipartite graph $B=(U,W;E)$ with vertex classes~$U$ and~$W$ and
edge set~$E$ is said to be $\epsilon$-regular if $(U,W)$ is an
$\epsilon$-regular pair with respect to~$B$.  Thus, a witness to the
$\epsilon$-irregularity of~$B$ is a pair~$(U',W')$ with~$U'\subset U$,
$W'\subset W$, $|U'|$, $|W'|\geq\epsilon n$,
and~$|d_B(U',W')-d_B(U,W)|>\epsilon$.  Below, we write~$M(n)$ for the time
required to square an $n\times n$ matrix with entries in~$\{0,1\}$ over the
integers.  By a result of Coppersmith and
Winograd~\cite{coppersmith90:_matrix}, we have~$M(n)=O(n^{2.376})$.  (We leave
it as an easy exercise for the reader to see how matrix multiplication comes
into play here; without fast matrix multiplication, we would have an algorithm
with running time~$O(n^3)$ in Lemma~\ref{lem:resolve_coNP_problem} below.)

\begin{lemma}
  \label{lem:resolve_coNP_problem} 
  There exists an algorithm~$\cA$ for which the following holds.  When~$\cA$
  receives as input an~$\epsilon>0$ and a bipartite graph~$B=(U,W;E)$
  with~$|U|=|W|=n\geq(2/\epsilon)^5$, it either correctly asserts that~$B$ is
  $\epsilon$-regular, or else it returns a witness for the
  $\epsilon'$-irregularity of~$B$,
  where~$\epsilon'=\epsilon_{\cA}'(\epsilon)=\epsilon^5/16$.  The running time
  of~$\cA$ is~$O(M(n))$.
\end{lemma}

Note that Lemma~\ref{lem:resolve_coNP_problem} leaves open what the behaviour
of~$\cA$ should be when~$B$ is $\epsilon$-regular but is not
$\epsilon'$-regular.  Despite this fact, Lemma~\ref{lem:resolve_coNP_problem}
does indeed imply the existence of a polynomial-time algorithm for finding
$\epsilon$-regular partitions of graphs.  A moment's thought should make it
clear that what is required is an algorithmic version of
Lemma~\ref{lem:LemmaF}.  Lemma~\ref{lem:resolve_coNP_problem} readily provides
such a result.  We leave the proof of this assertion as an exercise for the
reader.  

Summing up the results discussed so far, we have the following theorem, which
is an algorithmic version of Szemer\'edi's regularity
lemma~\cite{AlonDLRY92,alon94}. 

\begin{theorem}
  \label{thm:constructive_regularity}
  There is a deterministic algorithm~$\cB$ and functions~$K_0(\epsilon,k_0)$
  and $N_0(\epsilon,k_0)$ for which the following holds.  On input~$G=G^n$,
  $0<\epsilon\leq1$, and~$k_0\geq1$, where~$n\geq N_0(\epsilon,k_0)$,
  algorithm~$\cB$ returns an $\epsilon$-regular, $(\epsilon,k)$-equitable
  partition for~$G$ in time~$O(M(n))$, where~$k_0\leq k\leq
  K_0(\epsilon,k_0)$.
\end{theorem}

Let us observe that the constant implied in the big~$O$ notation in
Theorem~\ref{thm:constructive_regularity} depends on~$\epsilon$ and~$k_0$.

In~\cite{kohayakawa00:_optimal_SzRL}, we shall show how to improve on the
running time given in Lemma~\ref{lem:resolve_coNP_problem} (at the cost of
decreasing the value of~$\epsilon'=\epsilon'(\epsilon)$ substantially).  The
key idea is to make use of the quasi-random property to be discussed in
Section~\ref{sec:checking}.  The algorithm for constructing $\epsilon$-regular
partitions given in~\cite{kohayakawa00:_optimal_SzRL} has running
time~$O(n^2)$ for graphs of order~$n$, where, again, the implicit constant
depends on~$\epsilon$ and~$k_0$.

The algorithms we have discussed so far are all deterministic.  If one allows
randomization, one may develop algorithms that run in~$O(n)$ time, as shown by
Frieze and Kannan~\cite{FriezeKannanRL,frieze99:_quick_approx_matric_applic}.

\subsubsection{A coNP-completeness result}
\label{sec:coNP-complete}
The reader may find it unsatisfactory that, strictly speaking, we did not
solve the problem of characterizing precisely the $\epsilon$-regular pairs.
Indeed, Lemma~\ref{lem:resolve_coNP_problem} can only tell the difference
between $\epsilon_\cA'(\epsilon)$-regular pairs and $\epsilon$-irregular
pairs, and~$\epsilon_\cA'(\epsilon)\ll\epsilon$.  This is, by no means, an
accident.  Consider the decision problem below.

\begin{problem}
  \label{prob:decide}
  Given a graph~$G$, a pair~$(U,W)$ of non-empty, pairwise disjoint sets of
  vertices of~$G$, and a positive~$\epsilon$, decide whether this pair is
  $\epsilon$-regular with respect to~$G$.
\end{problem}

It should be clear that, in the case in which the answer to
Problem~\ref{prob:decide} is negative for a given instance, we would like to
have a witness for the $\epsilon$-irregularity of the given pair.  Indeed, an
algorithm that is able to solve Problem~\ref{prob:decide} and is also able to
provide such a witness in the case in which the answer is negative would prove
Lemma~\ref{lem:resolve_coNP_problem} with~$\epsilon'=\epsilon$.
Unfortunately, such an algorithm does not exist, unless $\text{P}=\text{NP}$,
as shows the following result of Alon, Duke, Lefmann, R\"odl, and
Yuster~\cite{AlonDLRY92,alon94}.

\begin{theorem}
  \label{thm:hardness_thm}
  Problem~\ref{prob:decide} is coNP-complete.
\end{theorem}

Let us remark in passing that Theorem~\ref{thm:hardness_thm} is proved
in~\cite{AlonDLRY92,alon94} for the case in which~$\epsilon=1/2$; for
a proof for arbitrary~$0<\epsilon\leq1/2$, see
Taraz~\cite{Taraz95Diplom}.

\subsection{The sparse case}
\label{sec:sparse_local_condition}
As proved in~\cite{kohayakawa00:_regul_i}, Theorems~\ref{lem:prop2}
and~\ref{lem:prop3} do not generalize to graphs of vanishing density.
However, in view of the applicability of those results, it seems worth
pursuing the sparse case.  In~\cite{kohayakawa00:_regul_i}, we prove that
natural generalizations of Theorems~\ref{lem:prop2} and~\ref{lem:prop3}
\textit{do hold} for subgraphs of sparse random graphs.  Examples of
applications of these generalizations appear in~\cite{alon00:_univer}
(cf.~Theorem~1.5) and~\cite{KohayakawaRSz99sizeRamsey}.  We do not go into the
details here.

\section{A new quasi-random property}
\label{sec:checking}

In this section, we present a new quasi-random graph property, in the sense of
Chung, Graham, and Wilson~\cite{chung89}.  In the introduction and in
Section~\ref{sec:equivalence}, we very briefly discussed the basics of
quasi-randomness, and mentioned the close relationship between
quasi-randomness, $\epsilon$-regularity, and the regularity lemma as a strong
motivation for studying quasi-random graph properties.

In Section~\ref{sec:local}, we discussed `local' conditions for regularity,
and observed that these conditions were the key for developing a
$O(n^{2.376})$-time algorithm that checks whether a given bipartite graph is
regular (see Lemma~\ref{lem:resolve_coNP_problem}).  In turn, this led to a
$O(n^{2.376})$-time algorithm for finding regular partitions of graphs.  The
quasi-random property that we present in this section allows one to check
regularity, somewhat surprisingly, in time~$O(n^2)$.  Since we deal with dense
input graphs, this running time is proportional to the input size, and hence
we have a \textit{linear time algorithm}.  (The corresponding linear time
algorithm for finding regular partitions of graphs, which is based on some
additional ideas, will be presented in~\cite{kohayakawa00:_optimal_SzRL}.)

The proof of the fact that our property is indeed a quasi-random property will
make use of the sparse regularity lemma, Theorem~\ref{thm:SSzp}.  To simplify
the notation, we restrict our discussion to the case of graphs with
density~$\sim1/2$.  Moreover, we deal with quasi-randomness and arbitrary
graphs, instead of regularity and bipartite graphs.  We hope that the reader
finds the correspondence between these two contexts clear.

\subsection{Basic definitions}
\label{sec:defs}
We start with the definition of a standard quasi-random graph property.

\begin{definition}[$(1/2,\epsilon,\delta)$-quasi-randomness]
  \label{def:quasi-randomness}
  Let reals~$0<\epsilon\leq1$ and~$0<\delta\leq1$ be given.  We shall say that
  a graph~$G$ is \textit{$(1/2,\epsilon,\delta)$-quasi-random} if, for
  all~$U$, $W\subset V(G)$ with~$U\cap W=\emptyset$ and~$|U|$, $|W|\geq\delta
  n$, we have
  \begin{equation}
    \label{eq:basic-q.r.}
    \left|e_G(U,W)-\frac12|U||W|\right|\leq\frac12\epsilon|U||W|.
  \end{equation}
\end{definition}

Before we proceed, we need to introduce a technical definition concerning
graphs with uniformly distributed edges.  

\begin{definition}[$(\rho,A)$-uniformity]
  \label{def:uniformity}
  If~$0<\rho\leq1$ and~$A$ are reals, we say that an $n$-vertex graph~$J=J^n$
  is \textit{$(\rho,A)$-uniform} if, for all~$U$, $W\subset V(J)$ with~$U\cap
  W=\emptyset$, we have
  \begin{equation}
    \label{eq:basic-unif}
    \big|e_J(U,W)-\rho|U||W|\big|\leq A\sqrt{r|U||W|}, 
  \end{equation}
  where~$r=\rho n$.
\end{definition}

As it will become clear later, we shall be mainly concerned with
$(\rho,A)$-uniform graphs~$J$ with \textit{constant} average degree, that is,
graphs~$J=J^n$ with~$O(n)$ edges.  The construction of such $(\rho,A)$-uniform
graphs~$J=J^n$ with linearly many edges will be briefly discussed in
Section~\ref{sec:LPS}.

In the sequel, when dealing with a $(\rho,A)$-uniform graph~$J=J^n$, we
usually write~$r$ for~$\rho n$.  Let us remark for later reference that the
following fact, whose simple proof will be given in Section~\ref{sec:LPS},
holds.

\begin{fact}
  \label{fact:single_set_uniform}
  If~$J$ is a $(\rho,A)$-uniform graph, then, for any~$U\subset V(J)$, we have
  \begin{equation}
    \label{eq:unif-single-set}
    \left|e_J(U)-\rho\binom{|U|}2\right|\leq A\sqrt r|U|.
  \end{equation}
\end{fact}

We shall now define a property for $n$-vertex graphs~$G=G^n$, based on a fixed
$(\rho,A)$-uniform graph~$J=J^n$ with the same vertex set as~$G$.  Below, we
write~$ij\in J$ to mean that~$ij$ is an edge of the graph~$J$.  We recall that
we denote the neighbourhood of a vertex~$x$ in a graph~$G$
by~$\Gamma(x)=\Gamma_G(x)$, and we write~$X\symmdiff Y$ for the symmetric
difference of~$X$ and~$Y$.

\begin{definition}[Property~$\PJsdiff(\epsilon)$]
  \label{def:PropertyPJsdiff}
  Let~$G=G^n$ and~$J=J^n$ be $n$-vertex graphs on the same vertex set.
  Let~$0<\epsilon\leq1$ be a real number.  We say that~$G$ satisfies
  property~$\PJsdiff(\epsilon)$ if we have
  \begin{equation}
    \label{eq:PJsdiff}
    \sum_{ij\in J}
      \left||\Gamma_G(i)\symmdiff\Gamma_G(j)|-\frac12n\right|
       \leq\frac12\epsilon ne(J).
  \end{equation}
\end{definition}

Our new quasi-random property is~$\PJsdiff(\epsilon)$ above.  It should be now
clear why it is interesting for us to have $(\rho,A)$-uniform graphs~$J$ with
as few edges as possible: the number of terms in the sum in~\eqref{eq:PJsdiff}
is~$e(J)$.  Since each term of that sum may be computed in~$O(n)$ time if,
say, we have access to the adjacency matrix of~$G$, it follows that the time
required to verify property~$\PJsdiff(\epsilon)$ is~$O(ne(J))$, which
is~$O(n^2)$ if we have linear-sized $(\rho,A)$-uniform graphs~$J$.

For technical reasons, we need to introduce a variant of
property~$\PJsdiff(\epsilon)$.  

\begin{definition}[Property~$\PJsdiff'(\gamma,\epsilon)$]
  \label{def:PropertyPJsdiff'}
  Let~$G=G^n$ and~$J=J^n$ be $n$-vertex graphs on the same vertex set.
  Let~$0<\gamma\leq1$ and~$0<\epsilon\leq1$ be two real numbers.  We shall say
  that~$G$ satisfies property~$\PJsdiff'(\gamma,\epsilon)$ if the inequality
  \begin{equation}
    \label{eq:PJsdiff-local}
    \left||\Gamma_G(i)\symmdiff\Gamma_G(j)|-\frac12n\right|
     \leq\frac12\epsilon n   
  \end{equation}
  \textit{fails} for at most~$\gamma e(J)$ edges~$ij\in J$ of~$J$.
\end{definition}

As a quick argument will show, properties~$\PJsdiff(\epsilon)$
and~$\PJsdiff'(\gamma,\epsilon)$ are equivalent under suitable assumptions on
the parameters; see Lemma~\ref{lem:PJ-PJdash}.  

Our main result in Section~\ref{sec:checking} is that, roughly speaking,
properties~$\PJsdiff(o(1))$ and~$\PJsdiff'(o(1),o(1))$ are equivalent to
$(1/2,o(1),o(1))$-quasi-randomness.  We make the form of this equivalence
precise in the next section.

\subsection{The equivalence result}
\label{sec:main-results}
Theorems~\ref{thm:Main-1} and~\ref{thm:Main-2} below are the main results of
Section~\ref{sec:checking}.  Intuitively, Theorem~\ref{thm:Main-1} states that
property~$\PJsdiff(o(1))$ is a \textit{sufficient} condition for
$(1/2,o(1),o(1))$-quasi-randomness, whereas Theorem~\ref{thm:Main-2} states
that~$\PJsdiff'(o(1),o(1))$ is a \textit{necessary} condition.
Lemma~\ref{lem:PJ-PJdash} tells us that~$\PJsdiff(o(1))$
and~$\PJsdiff'(o(1),o(1))$ are equivalent.

\begin{theorem}
  \label{thm:Main-1}
  For any~$0<\epsilon\leq1$, $0<\delta\leq1$, and~$A\geq1$, there
  exist~$\epsilon_0=\epsilon_0(\epsilon,\delta,A)>0$
  and~$r_0=r_0(\epsilon,\delta,A)\geq1$ for which the following holds.
  Suppose~$G=G^n$ and~$J=J^n$ are two graphs on the same vertex set.  Suppose
  further that~$J=J^n$ is a $(\rho,A)$-uniform graph with~$r=\rho n\geq r_0$.
  Then, if~$G$ satisfies property~$\PJsdiff(\epsilon')$ for
  some~$0<\epsilon'\leq\epsilon_0$, then~$G$ is
  $(1/2,\epsilon,\delta)$-quasi-random.
\end{theorem}

\begin{theorem}
  \label{thm:Main-2}
  For any~$0<\gamma\leq1$, $0<\epsilon\leq1$, and~$A\geq1$, there
  exist~$\epsilon_0=\epsilon_0(\gamma,\epsilon,A)>0$,
  $\delta_0=\delta_0(\gamma,\epsilon,A)>0$, $r_1=r_1(\gamma,\epsilon,A)\geq1$,
  and~$N_1=N_1(\gamma,\epsilon,A)\geq1$ for which the following holds.
  Suppose~$G=G^n$ and~$J=J^n$ are two graphs on the same vertex set,
  with~$n\geq N_1$.  Suppose further that~$J=J^n$ is a $(\rho,A)$-uniform
  graph with~$r=\rho n\geq r_1$.  Then, if~$G$ is
  $(1/2,\epsilon',\delta')$-quasi-random for some~$0<\epsilon'\leq\epsilon_0$
  and~$0<\delta'\leq\delta_0$, then property~$\PJsdiff'(\gamma,\epsilon)$
  holds for~$G$.
\end{theorem}

\begin{Remark}
  \label{rem:small_r}
  As our previous discussion suggests, it is of special relevance to us that
  in Theorems~\ref{thm:Main-1} and~\ref{thm:Main-2} the quantity~$r=\rho n$ is
  not required to grow with~$n$.
\end{Remark}

\begin{Remark}
  \label{rem:J_complete_case}
  We remark that Theorems~\ref{thm:Main-1} and~\ref{thm:Main-2} basically
  reduce to the results in Sections~\ref{sec:lindsey}--\ref{sec:general} if we
  take~$J=J^n$ to be the complete graph~$K^n$.
\end{Remark}

\begin{lemma}
  \label{lem:PJ-PJdash}
  Let a $(\rho,A)$-uniform graph~$J=J^n$ be given, and suppose~$G=G^n$ is a
  graph on the same vertex set as~$J$.  Then the following assertions hold.
  \begin{enumerate}
  \item[(\textit{i})] If~$G$ satisfies property~$\PJsdiff'(\gamma,\epsilon)$,
    then~$G$ satisfies property~$\PJsdiff(\epsilon+\gamma)$.
  \item[(\textit{ii})] If~$G$ satisfies property~$\PJsdiff(\epsilon)$
    and~$0<\epsilon\leq\epsilon'\leq1$, then~$G$ satisfies
    property~$\PJsdiff'(\epsilon/\epsilon',\epsilon')$.
  \end{enumerate}
\end{lemma}

We shall prove Theorems~\ref{thm:Main-1} and~\ref{thm:Main-2} in two separate
sections below.  Here, we give the simple proof of Lemma~\ref{lem:PJ-PJdash}. 

\begin{proof}[Proof of Lemma~\ref{lem:PJ-PJdash}]
  Let~$J=J^n$ and~$G=G^n$ be as in the statement of
  Lemma~\ref{lem:PJ-PJdash}.  Suppose first that~$G$ has
  property~$\PJsdiff'(\gamma,\epsilon)$.  Then
  \begin{equation}
    \label{eq:triv_equivalence_i}
    \sum_{ij\in J}
      \left||\Gamma_G(i)\symmdiff\Gamma_G(j)|-\frac12n\right|
      \leq\frac12\epsilon ne(J)+\frac12n\gamma e(J)
      =\frac12(\epsilon+\gamma)ne(J).
  \end{equation}
  Therefore property~$\PJsdiff(\epsilon+\gamma)$ holds and~(\textit{i}) is
  proved.  To prove~(\textit{ii}), suppose that~$G$
  satisfies~$\PJsdiff(\epsilon)$ and~$0<\epsilon\leq\epsilon'\leq1$.
  If~$\PJsdiff'(\epsilon/\epsilon',\epsilon')$ were to fail, then we would
  have~$>(\epsilon/\epsilon')e(J)$ edges~$ij$ of~$J$ with
  \begin{equation}
    \label{eq:triv_equivalence_ii}
    \left||\Gamma_G(i)\symmdiff\Gamma_G(j)|-\frac12n\right|
    >\frac12\epsilon'n.
  \end{equation}
  But then
  \begin{equation}
    \label{eq:triv_equivalence_ii2}
    \sum_{ij\in J}
      \left||\Gamma_G(i)\symmdiff\Gamma_G(j)|-\frac12n\right|
      >\frac12\epsilon'n\times{\epsilon\over\epsilon'}e(J)
      =\frac12\epsilon ne(J),
    \end{equation}
    which contradicts~$\PJsdiff(\epsilon)$.
    Thus~$\PJsdiff'(\epsilon/\epsilon',\epsilon')$ must hold,
    and~(\textit{ii}) is proved.
\end{proof}

\subsection{The existence of $(\rho,A)$-uniform graphs}
\label{sec:LPS}

As promised before, in this section we discuss the construction of suitable
$(\rho,A)$-uniform graphs~$J=J^n$ with linearly many edges.  We state the
following result without proof.

\begin{lemma}
  \label{lem:existence_main}
  There exist absolute constant~$r_0$ and~$n_0$ for which the following holds.
  Let~$r\ge r_0$ be a constant and let~$n\ge n_0$ be given.  Then we may
  explicitly construct an adjacency list representation of a particular
  $(\rho,5)$-uniform graph~$J=J^n$ on~$V(J)=[n]$ with $r\leq\rho n\le 2r$ in
  time~$O(n(\log n)^{O(1)})$.
\end{lemma}

Lemma~\ref{lem:existence_main} may be deduced in a straightforward manner from
the celebrated construction of the Ramanujan graphs~$X^{p,q}$ of Lubotzky,
Phillips, and Sarnak~\cite{LPS} (see
also~\cite{lubotzky94:_discr,lubotzky86:_explic_raman,sarnak90:_some}).  We
mention in passing that, for proving the existence of suitable parameters~$p$
and~$q$ in the proof of Lemma~\ref{lem:existence_main}, it suffices to use
Dirichlet's theorem on the density of primes in arithmetic progressions.  We
omit the details (see~\cite{kohayakawa00:_optimal_SzRL}).

We also promised to prove Fact~\ref{fact:single_set_uniform} in this section.

\begin{proof}[Proof of Fact~\ref{fact:single_set_uniform}]
  We may clearly assume that~$u=|U|\geq2$.  Note that, for any~$1\leq s<u$, we
  have~$2e(U){u-2\choose s-1}=\sum_Se(S,U\setminus S)$, where the sum is
  extended over all~$S\subset U$ with~$|S|=s$.  Thus
  \begin{equation}
    \label{eq:averaging0}
    e(U)={1\over2}{u\choose s}{u-2\choose s-1}^{-1}\left\{\rho|S||U\setminus
      S|+O_1\(A\sqrt{rs(u-s)}\)\right\}
  \end{equation}
  for any~$1\leq s<u$.  We use~\eqref{eq:averaging0} with~$s=\lfloor
  u/2\rfloor$.  Note that
  \begin{equation}
    \label{eq:averaging1}
    {u\choose\lfloor u/2\rfloor}{u-2\choose\lfloor u/2\rfloor-1}^{-1}
    ={u(u-1)\over\lfloor u/2\rfloor\lceil u/2\rceil}\leq4,
  \end{equation}
  and so
  \begin{equation}
    \label{eq:averaging2}
    e(U)
    =\rho{u\choose2}+O_1\(2A\sqrt{r\lfloor u/2\rfloor\lceil u/2\rceil}\)
    =\rho{u\choose2}+O_1\(Au\sqrt r\),
  \end{equation}
  as required.
\end{proof}

In the next two sections, we prove Theorems~\ref{thm:Main-1}
and~\ref{thm:Main-2}.

\subsection{Proof of Theorem~\ref{thm:Main-1}}
\label{sec:proofofMain1}

Let constants~$0<\epsilon\leq1$, $0<\delta\leq1$, and~$A\geq1$ be given.  We
then put
\begin{equation}
  \label{eq:epsilon0_r0_def}
  \epsilon_0=\epsilon_0(\epsilon,\delta,A)={1\over4}\epsilon^2\delta^3
  \quad\text{and}\quad
  r_0=r_0(\epsilon,\delta,A)=2^6A^2\epsilon^{-4}\delta^{-4}.
\end{equation}
For later reference, let us observe that
\begin{equation}
  \label{eq:bore1}
  {A\over2\sqrt r_0}\leq{1\over16}<{1\over4},
\end{equation}
and that
\begin{equation}
  \label{eq:bore2}
  {A\over\sqrt r_0}=\frac18\epsilon^2\delta^2.
\end{equation}

Our aim is to show that the values of~$\epsilon_0$ and~$r_0$ given
in~$\eqref{eq:epsilon0_r0_def}$ will do in Theorem~\ref{thm:Main-1}.  Thus,
suppose we are given a graph~$G=G^n$ and a $(\rho,A)$-uniform graph~$J=J^n$ on
the same vertex set, say~$V$, and suppose further that~$G$ satisfies
property~$\PJsdiff(\epsilon')$, where~$0<\epsilon'\leq\epsilon_0$, and~$r=\rho
n\geq r_0$.  We have to show that~$G$ is $(1/2,\epsilon,\delta)$-quasi-random.

In what follows, we assume that two disjoint sets~$U$, $W\subset V$
with~$|U|$, $|W|\geq\delta n$ are given.  We wish to show that
inequality~\eqref{eq:basic-q.r.} holds.  The approach we take is similar in
spirit to the one used in the proof of Theorem~\ref{thm:lindsey}.

Let~$\bfA=(a_{ij})_{i,j\in V}$ be the adjacency matrix of~$G$ with entries
in~$\{\pm1\}$, with~$a_{ij}=1$ if~$ij\in G$ and~$a_{ij}=-1$ if~$ij\notin G$.
Let us write~$\bfv_i=(a_{ij})_{j\in V}$ ($i\in V$) for the $i$th row
of~$\bfA$.  We start by observing that property~$\PJsdiff(\epsilon')$ implies
that~$\sum_{ij\in J}|\<\bfv_i,\bfv_j\>|$ is small.

\begin{lemma}
  \label{lem:small-scalar-prod-sum} 
  We have
  \begin{equation}
    \label{eq:small-scalar-prod-sum}
    \sum_{ij\in J}\left|\<\bfv_i,\bfv_j\>\right|\leq\epsilon'ne(J).
  \end{equation}
\end{lemma}
\begin{proof}
  By the definition of the~$\bfv_i$, we have
  $$
  \<\bfv_i,\bfv_j\>=n-2|\Gamma_G(i)\symmdiff\Gamma_G(j)|,
  $$
  and the result follows from the definition of
  property~$\PJsdiff(\epsilon')$.
\end{proof}

Our aim now is to estimate the left-hand side
of~(\ref{eq:small-scalar-prod-sum}) from below.  It turns out that one may
give a good lower bound for this quantity in terms of the number of
$G$-edges~$e_G(U,W)$ between~$U$ and~$W\subset V$ for any pair~$(U,W)$ as long
as both~$U$ and~$W$ are large enough.  

Recall that sets~$U$, $W\subset V$ with~$u=|U|$, $w=|W|\geq\delta n$ are
fixed, and put~$\bfw_i=(a_{ij})_{j\in W}$ for all~$i\in U$.  Thus, $\bfw_i$~is
the restriction of~$\bfv_i$ to the coordinates in~$W$.  For convenience, we
shall write~$\sumijU$ to indicate sum over all edges~$ij\in J$ with both~$i$
and~$j$ in~$U$.

Let us compare~$\sumijU\<\bfv_i,\bfv_j\>$ and~$\sumijU\<\bfw_i,\bfw_j\>$.
Clearly,
\begin{equation}
  \label{eq:vs-vs-ws}
  \sumijU\<\bfv_i,\bfv_j\>
    =\sumijU\<\bfw_i,\bfw_j\>
     +\sum_{k\in V\setminus W}\sumijU a_{ik}a_{jk}.
\end{equation}
In the lemma below, we estimate~$\SkU=\sumijU a_{ik}a_{jk}$ for all~$k\in
V$.  Recall that we write~$O_1(x)$ for any term~$y$ satisfying~$|y|\leq x$.

\begin{lemma}
  \label{lem:S_k}
  Fix a vertex~$k\in V$, and let~$u=|U|$, $u^+=u_k^+=|\Gamma_G(k)\cap U|$,
  and~$u^-=u_k^-=|U\setminus\Gamma_G(k)|$.  Then
  \begin{equation}
    \label{eq:S_k}
    \SkU=\sumijU a_{ik}a_{jk}
       =\frac12\rho\((u^+-u^-)^2-u\)+O_1\(\frac32Au\sqrt r\).
  \end{equation}
  In particular, we have
  \begin{equation}
    \label{eq:S_klb}
    \SkU\geq\frac12\rho(u^+-u^-)^2-2Au\sqrt r\geq-2Au\sqrt r.
  \end{equation}
\end{lemma}
\begin{proof}
  Note that an edge~$ij\in J$ contributes~$+1$ to the sum in~\eqref{eq:S_k}
  if~$i$, $j\in\Gamma_G(k)\cap U$ or else~$i$, $j\in U\setminus\Gamma_G(k)$.
  Similarly, the edge~$ij\in J$ contributes~$-1$ to that sum if~$ij\in
  E\big(\Gamma_G(k)\cap U,U\setminus\Gamma_G(k)\big)$.
  
  By the $(\rho,A)$-uniformity of~$J$ (see also~\eqref{eq:unif-single-set} in
  Fact~\ref{fact:single_set_uniform}), we have
  \begin{equation*}
    \begin{split}
      \SkU&=\sumijU a_{ik}a_{jk}\\
      &=\rho{u^+\choose2}+O_1\(Au^+\sqrt r\)\\
      &\qquad+\rho{u^-\choose2}+O_1\(Au^-\sqrt r\)
      -\rho u^+u^-+O_1\(A\sqrt{ru^+u^-}\)\\
%      &\qquad\qquad\qquad\qquad-\rho u^+u^-+O_1\(A(ru^+u^-)^{1/2}\)\\
      &=\rho\({1\over2}(u^+)^2+{1\over2}(u^-)^2-u^+u^--{1\over2}(u^++u^-)\)\\
      &\qquad\qquad\qquad+O_1\(A\sqrt r(u^++u^-+\sqrt{u^+u^-})\),
    \end{split}
  \end{equation*}
  from which~\eqref{eq:S_k} follows.
  
  Since~$A\geq1$ and~$r<n$, we have~$\rho u/2\leq(1/2)Au\sqrt r$.  Therefore,
  the right-hand side of~\eqref{eq:S_k} is at least
  \begin{equation}
    \label{eq:final_63}
    \frac12\rho(u^+-u^-)^2-{1\over2}\rho u-\frac32Au\sqrt r
    >\frac12\rho(u^+-u^-)^2-2Au\sqrt r.
  \end{equation}
  Inequality~\eqref{eq:S_klb} follows from~\eqref{eq:final_63} and
  Lemma~\ref{lem:S_k} is proved.
\end{proof}

An immediate corollary to~(\ref{eq:vs-vs-ws}) and~(\ref{eq:S_klb}) is that  
\begin{equation}
  \label{eq:vs-vs-ws-2}
  \sumijU\<\bfv_i,\bfv_j\>
    \geq\sumijU\<\bfw_i,\bfw_j\>-2A(n-w)u\sqrt r, 
\end{equation}
where, as before, $w=|W|$.  We now estimate~$\sumijU\<\bfw_i,\bfw_j\>$
from below using Lemma~\ref{lem:S_k}.  Put 
\begin{equation}
  \label{eq:u*+}
  u_*^+=\Ave_{k\in W}u_k^+=\Ave_{k\in W}|\Gamma_G(k)\cap U|
       =\frac1we_G(U,W), 
\end{equation}
where~$\Ave_{k\in W}$ denotes average over all~$k\in W$.

\begin{lemma}
  \label{lem:sum-wiwj-lb}
  We have
  \begin{equation}
    \label{eq:sum-wiwj-lb}
    \sumijU\<\bfw_i,\bfw_j\>
     \geq\frac12\rho w(2u_*^+-u)^2-2Auw\sqrt r.
   \end{equation}
\end{lemma}
\begin{proof}
  We make use of Lemma~\ref{lem:S_k}.  We have~$u_k^+-u_k^-=2u_k^+-u$ for
  all~$k$.  Therefore, inequality~\eqref{eq:S_klb} in Lemma~\ref{lem:S_k}
  tells us that
  \begin{equation*}
    \begin{split}
      \sumijU\<\bfw_i,\bfw_j\>
      &=\sum_{k\in W}\sumijU a_{ik}a_{jk}\\
      &\geq{1\over2}\rho\sum_{k\in W}(u_k^+-u_k^-)^2-2Auw\sqrt r\\
      &={1\over2}\rho\sum_{k\in W}(2u_k^+-u)^2-2Auw\sqrt r,
    \end{split}
  \end{equation*}
  which, by convexity (or Cauchy--Schwarz), is at least as large as the
  right-hand side of~\eqref{eq:sum-wiwj-lb}.  The proof of this lemma is
  complete.
\end{proof}

We now put Lemmas~\ref{lem:small-scalar-prod-sum} and~\ref{lem:sum-wiwj-lb}
and inequality~(\ref{eq:vs-vs-ws-2}) together to obtain
\begin{multline}
  \label{eq:nerly-final}
  \frac12\rho w(2u_*^+-u)^2-2Aun\sqrt r
  \leq\sumijU\<\bfw_i,\bfw_j\>-2Au(n-w)\sqrt r\\
  \leq\sumijU\<\bfv_i,\bfv_j\>
  \leq\sumijU\left|\<\bfv_i,\bfv_j\>\right|
  \leq\sum_{ij\in J}\left|\<\bfv_i,\bfv_j\>\right|
  \leq\epsilon'ne(J).
\end{multline}
We now make use of~\eqref{eq:unif-single-set} in
Fact~\ref{fact:single_set_uniform} to deduce that
\begin{equation}
  \label{eq:no_edges_eJ}
  e(J)\leq\rho{n\choose2}+An\sqrt r
  \leq{1\over2}rn+An\sqrt r.
\end{equation}
Therefore
\begin{equation}
  \label{eq:nearly-nerly-final}
  \epsilon'ne(J)\leq{1\over2}\epsilon'rn^2+\epsilon'An^2\sqrt r,
\end{equation}
and hence~\eqref{eq:nerly-final} gives that
\begin{equation}
  \label{eq:nerly-final2}
  \frac12\rho w(2u_*^+-u)^2
  \leq{1\over2}\epsilon'rn^2+\epsilon'An^2\sqrt r+2Aun\sqrt r.
\end{equation}
However, we have
\begin{equation}
  \label{eq:expand}
  \frac12\rho w(2u_*^+-u)^2
  =\frac12\rho w\({2\over w}e_G(U,W)-u\)^2
  =2\frac\rho w\(e_G(U,W)-\frac12uw\)^2.
\end{equation}
From~\eqref{eq:nerly-final2} and~\eqref{eq:expand}, we obtain
\begin{equation}
  \label{eq:nearly-nearly-nearly-final}
  \begin{split}
    \left|e_G(U,W)-\frac12uw\right|^2
    &\leq\frac1{4\rho}\epsilon'rn^2w
    +{1\over2\rho}\epsilon'An^2w\sqrt r
    +{1\over\rho}Auwn\sqrt r\\
    &=\frac14\epsilon'n^3w+{1\over2\sqrt r}\epsilon'An^3w
    +{1\over\sqrt r}Auwn^2\\
    &=\epsilon'n^3w\(\frac14+\frac A{2\sqrt r}\)
    +{A\over\sqrt r}n^2uw.
  \end{split}
\end{equation}
Using~\eqref{eq:epsilon0_r0_def}, \eqref{eq:bore1}, and~\eqref{eq:bore2} and
the fact that~$\epsilon'\leq\epsilon_0$ and~$r\geq r_0$, we deduce that the
last expression in~\eqref{eq:nearly-nearly-nearly-final} is at most
\begin{multline}
  \label{eq:ffffinal}
  \frac12\epsilon'n^3w+\frac18\epsilon^2\delta^2n^2uw
  \leq\frac18\epsilon^2\delta^3n^3w+\frac18\epsilon^2\delta^2n^2uw\\
  \leq\frac18\epsilon^2u^2w^2+\frac18\epsilon^2u^2w^2
  =\(\frac12\epsilon uw\)^2.
\end{multline}
Putting together~\eqref{eq:nearly-nearly-nearly-final}
and~\eqref{eq:ffffinal}, we deduce inequality~\eqref{eq:basic-q.r.}.

The proof of Theorem~\ref{thm:Main-1} is complete.

\subsection{Proof of Theorem~\ref{thm:Main-2}}
\label{sec:proofofMain2}

Let constants~$0<\gamma\leq1$, $0<\epsilon\leq1$, and~$A\geq1$ be given.  Let
us define the constants~$\epsilon_0=\epsilon_0(\gamma,\epsilon,A)$,
$\delta_0=\delta_0(\gamma,\epsilon,A)$, $r_1=r_1(\gamma,\epsilon,A)$,
and~$N_1=N_1(\gamma,\epsilon,A)$ as follows.

We start by putting
\begin{equation}
  \label{eq:epsilon_0_def}
  \epsilon_0=\epsilon_0(\gamma,\epsilon,A)={1\over2^6}\gamma\epsilon.
\end{equation}
The definitions of~$\delta_0$ and~$r_1$ are a little more elaborate.  Let  
\begin{equation}
  \label{eq:epsilon_pp_def}
  \epsilon''={1\over2^6}\gamma\epsilon\leq{1\over2^6}
\end{equation}
and
\begin{equation}
  \label{eq:k_0_def}
  k_0=\left\lceil2^6\over\gamma\epsilon\right\rceil,
\end{equation}
and put~$D=2$.  Let
\begin{equation}
  \label{eq:eta0_K_0_def}
  \eta=\eta(\epsilon'',k_0,D)>0
  \quad\text{and}\quad
  K_0=K_0(\epsilon'',k_0,D)\geq k_0,  
\end{equation}
and~$N_0=N_0(\epsilon'',k_0,D)$ be the constants whose existence is guaranteed
by Theorem~\ref{thm:SSzp} for~$\epsilon''$, $k_0$, and~$D=2$.  We may clearly
assume that
\begin{equation}
  \label{eq:K0_triv_lwbd}
  K_0\geq{1\over2\epsilon''}.
\end{equation}
We now let
\begin{equation}
  \label{eq:delta_0_def}
  \delta_0=\delta_0(\gamma,\epsilon,A)
  =\min\left\{{1\over2^7}\gamma\epsilon,{1\over2K_0}\right\},
\end{equation}
and let
\begin{equation}
  \label{eq:r_def}
  r_1=r_1(\gamma,\epsilon,A)
  =\max\left\{(2AK_0)^2,\(A\over\eta\)^2\right\}
\end{equation}
and
\begin{equation}
  \label{eq:N_1_def}
  N_1=N_1(\gamma,\epsilon,A)=N_0(\epsilon'',k_0,D).
\end{equation}
We claim that these choices for~$\epsilon_0$, $\delta_0$, $r_1$, and~$N_1$
will do in Theorem~\ref{thm:Main-2}.  However, before we start the proof of
this claim, let us observe that the constants above obey the following
`hierarchy':
\begin{equation}
  \label{eq:hierarchy1}
  \delta_0\ll{1\over K_0}\leq{1\over k_0}\ll\gamma\epsilon
\end{equation}
and
\begin{equation}
  \label{eq:hierarchy2}
  \epsilon_0,\;\epsilon''\leq\gamma\epsilon.
\end{equation}
Moreover, 
\begin{equation}
  \label{eq:hierarchy3}
  r_1\gg A,\;K_0,\;{1\over\eta}
\end{equation}
so that, in a $(\rho,A)$-uniform graph~$J=J^n$, the number of edges between
two disjoint sets of vertices~$U$ and~$W\subset V(J)$ is roughly equal to the
expected quantity~$\rho|U||W|$, as long as
\begin{equation}
  \label{eq:UW_big}
  |U|,\; |W|\geq n\min\left\{{1\over2K_0},\eta\right\} 
\end{equation}
(see the proof of~\eqref{eq:eta0D-uu} below for details).  The reader may find
it useful to keep in mind the above relationship among our constants.

We now start with the proof that the above choices for~$\epsilon_0$,
$\delta_0$, $r_1$, and~$N_1$ work.  Let a $(\rho,A)$-uniform graph~$J=J^n$
with~$n\geq N_1$ vertices be fixed and let~$G$ be a
$(1/2,\epsilon',\delta')$-quasi-random graph on~$V=V(J)$,
where~$0<\epsilon'\leq\epsilon_0$, $0<\delta'\leq\delta_0$, and~$r\geq r_1$.
We shall prove that~$G$ has property~$\PJsdiff'(\gamma,\epsilon)$.

Assume for a contradiction that~$\PJsdiff'(\gamma,\epsilon)$ fails for~$G$.
Therefore we know that the number of edges~$ij\in J$ in~$J$ that violate
inequality~(\ref{eq:PJsdiff-local}) is greater than~$\gamma e(J)$.  Let us
assume that the number of edges~$ij\in J$ for which we have
\begin{equation}
  \label{eq:ij-violation}
  |\Gamma_G(i)\symmdiff\Gamma_G(j)|-\frac12n<-\frac12\epsilon n
\end{equation}
is larger than~$(\gamma/2)e(J)$.  The case in which 
\begin{equation}
  \label{eq:ij-violation-2}
  |\Gamma_G(i)\symmdiff\Gamma_G(j)|-\frac12n>\frac12\epsilon n
\end{equation}
occurs for more than~$(\gamma/2)e(J)$ edges~$ij$ of~$J$ is analogous.  We
let~$H$ be the graph on~$V=V(J)$ whose edges are the edges~$ij\in J$ that
satisfy~(\ref{eq:ij-violation}).

The regularity lemma for sparse graphs implies Lemma~\ref{lem:regular-pair}
below.  We shall use the second form of the lemma, Theorem~\ref{thm:SSzp},
although the first version, Theorem~\ref{thm:SSz}, would equally do (with the
first version the calculations involved would be slightly longer).

\begin{lemma}
  \label{lem:regular-pair}
  The graph~$H$ contains an $(\epsilon'',H,\rho)$-regular pair~$(U,W)$ of
  $\rho$-density $\dHr(U,W)$ at least~$\gamma/4$ and with~$|U|=|W|=m\geq
  n/2K_0$.
\end{lemma}
\begin{proof}
  Let~$\eta_0=\min\{1/2K_0,\eta\}$, where~$\eta$ and~$K_0$ are as defined
  in~\eqref{eq:eta0_K_0_def}.  We claim that~$H=H^n$ is an
  $(\eta_0,2)$-upper-uniform graph with respect to density~$\rho$, that is,
  if~$U$, $W\subset V=V(H)$ are disjoint and~$|U|$, $|W|\geq\eta_0 n$, then
  \begin{equation*}
    e_H(U,W)\le2\rho|U||W|.
  \end{equation*}
  Because of the $(\rho,A)$-uniformity of~$J\supset H$, it suffices to check
  that 
  \begin{equation}
    \label{eq:eta0D-uu}
    A\sqrt{r|U||W|}\leq\rho|U||W|
  \end{equation}
  (see~\eqref{eq:basic-unif}).  However, this follows easily
  from~\eqref{eq:r_def} and the fact that~$r=\rho n\geq r_1$.
  
  Having verified that~$H$ is $(\eta_0,2)$-upper-uniform with respect to
  density~$\rho$, we may invoke Theorem~\ref{thm:SSzp} to obtain an
  $(\epsilon'',H,\rho)$-regular $(\epsilon'',k)$-equitable
  partition~$(C_i)_0^k$ of the vertex set of~$H$ with $k_0\leq k\leq K_0$.
  Observe that
  \begin{equation}
    \label{eq:m_lwbd}
    |C_i|\geq{n\over 2K_0}\text{ for all~$1\leq i\leq k$,}
  \end{equation}
  since~$|C_0|\leq\epsilon'' n<n/2$ (see~\eqref{eq:epsilon_pp_def}).  We shall
  now apply a standard argument to show that we may take for~$(U,W)$ some
  pair~$(C_i,C_j)$.  We already know from~\eqref{eq:m_lwbd} that the~$C_i$
  ($1\leq i\leq k$) have large enough cardinality.  Put~$m=|C_i|$ ($1\leq
  i\leq k$) and observe that
  \begin{equation}
    \label{eq:m_bounds}
    {n\over 2K_0}\leq m\leq{n\over k}.
  \end{equation}
  It suffices to prove the following claim to complete the proof of
  Lemma~\ref{lem:regular-pair}. 
  
  \begin{claim}
    \label{claim:standard_arg}
    There exist~$1\leq i<j\leq k$ for which the pair~$(C_i,C_j)$ is
    $(\epsilon'',H,\rho)$-regular and~$\dHr(C_i,C_j)\geq\gamma/4$.  
  \end{claim}
  \begin{proof}
    Suppose for a contradiction that no pair~$(C_i,C_j)$ with~$1\leq i<j\leq
    k$ is good.  Working under this hypothesis, we shall deduce that the
    number of edges in~$H$ is at most~$(\gamma/2)e(J)$, which will contradict
    the definition of the graph~$H$.
    
    Let us turn to the estimation of~$e(H)$.  There are four types of edges
    in~$H$: (\textit{i})~edges that are induced by
    $(\epsilon'',H,\rho)$-regular pairs~$(C_i,C_j)$ with~$1\leq i<j\leq k$,
    (\textit{ii})~edges that are induced by $(\epsilon'',H,\rho)$-irregular
    pairs~$(C_i,C_j)$ with~$1\leq i<j\leq k$, (\textit{iii})~edges that are
    induced within the classes~$C_i$ ($1\leq i\leq k$), that is, edges
    in~$\bigcup_{1\leq i\leq k}H[C_i]$, and (\textit{iv})~edges that are
    incident to the exceptional class~$C_0$.  We now estimate the number of
    edges of each type in turn.

    Because of our assumption that no pair~$(C_i,C_j)$ will do for our claim,
    all the $(\epsilon'',H,\rho)$-regular pairs~$(C_i,C_j)$ with~$1\leq
    i<j\leq k$ are such that
    \begin{equation}
      \label{eq:recall_def_density}
      \dHr(U,W)={e_H(U,W)\over\rho|U||W|}<{\gamma\over4}.
    \end{equation}
    Thus, the number of edges of type~(\textit{i}) is
    \begin{equation}
      \label{eq:type_i}
      <{\gamma\over4}\rho m^2{k\choose2}
      \leq{\gamma\over4}\rho\(n\over k\)^2{k^2\over2}
      ={\gamma\over4}\(\rho{n^2\over2}\).
    \end{equation}
    We know that~$H$ is a $(\eta_0,2)$-upper-uniform graph with respect to
    density~$\rho$, and that the~$C_i$ ($1\leq i\leq k$) have
    cardinality~$m\geq(1/2K_0)n\geq\eta_0n$.  Therefore the number of edges
    induced by a pair~$(C_i,C_j)$ with~$1\leq i<j\leq k$ is at most~$2\rho
    m^2$.  We also know that the number of $(\epsilon'',H,\rho)$-irregular
    pairs is at most~$\epsilon''{k\choose2}$, and hence we deduce that the
    number of edges of type~(\textit{ii}) is, by~\eqref{eq:epsilon_pp_def},
    \begin{equation}
      \label{eq:type_ii}
      \leq2\rho m^2\epsilon''{k\choose2}
      \leq2\epsilon''\rho\(n\over k\)^2{k^2\over2}
      \leq{\gamma\over2^5}\({1\over2}\rho n^2\).
    \end{equation}
    Fact~\ref{fact:single_set_uniform} together with the fact that~$Am\sqrt
    r\leq\rho m^2$ (cf.~\eqref{eq:eta0D-uu}) imply
    that~$e(H[C_i])\leq(3/2)\rho m^2$.  Therefore, the number of edges of
    type~(\textit{iii}) is, by~\eqref{eq:k_0_def}, 
    \begin{equation}
      \label{eq:type_iii}
      \leq{3\over2}\rho m^2k\leq{3\over2}\rho\(n\over k\)^2k
      ={3\over k}\(\rho{n^2\over2}\)
      \leq{3\over2^6}\gamma\({1\over2}\rho n^2\).
    \end{equation}
    We now observe that, because of~\eqref{eq:K0_triv_lwbd}, we
    have~$\epsilon''\geq1/2K_0\geq\eta_0$.  Therefore, the number of edges of
    type~(\textit{iv}), that is, incident to~$C_0$, is,
    by~\eqref{eq:epsilon_pp_def}, 
    \begin{equation}
      \label{eq:type_iv}
      \leq{3\over2}\rho(\epsilon''n)^2+2\rho\epsilon''n^2
      =\(3(\epsilon'')^2+4\epsilon''\)\rho{n^2\over 2}
      \leq{5\over2^6}\gamma\({1\over2}\rho n^2\). 
    \end{equation}
    We conclude from~\eqref{eq:type_i}--\eqref{eq:type_iv} that the number of
    edges in~$H$ satisfies
    \begin{equation}
      \label{eq:eH_upbd}
      e(H)
      \leq\({1\over2^2}+{1\over2^5}+{1\over 2^3}\)\gamma\({1\over2}\rho n^2\) 
      <{7\over16}\gamma\({1\over2}\rho n^2\).
    \end{equation}

    We shall now estimate~$e(J)$ from below.
    Fact~\ref{fact:single_set_uniform} tells us that
    \begin{equation}
      \label{eq:eJ_lwbd}
      e(J)\geq\rho{n\choose2}-An\sqrt r
      ={1\over2}\rho n^2-{1\over2}\rho n-An\sqrt r
      ={1\over2}\rho n^2-{r\over2}-An\sqrt r.
    \end{equation}
    Using that~$n\geq N_1\geq16$, we obtain~$r/2\leq(1/16)\rho n^2/2$, and
    using that~$r\geq r_1\geq(2AK_0)^2\geq(2Ak_0)^2>(2^5A)^2$, we obtain
    that~$An\sqrt r\leq(1/16)\rho n^2/2$.  We therefore conclude
    from~\eqref{eq:eJ_lwbd} that
    \begin{equation}
      \label{eq:eJ_lwbd2}
      e(J)\geq{7\over8}\({1\over2}\rho n^2\).
    \end{equation}
    Finally, \eqref{eq:eH_upbd} and~\eqref{eq:eJ_lwbd2} imply
    that~$e(H)<(\gamma/2)e(J)$, which is a contradiction.  Therefore some
    pair~$(C_i,C_j)$ must be as required, and the proof of
    Claim~\ref{claim:standard_arg} is complete.
  \end{proof}
  
  We now fix a pair~$(C_i,C_j)$ as in Claim~\ref{claim:standard_arg}, and
  let~$U=C_i$ and~$W=C_j$.  Recalling~\eqref{eq:m_lwbd}, we see that the
  pair~$(U,W)$ is as required in Lemma~\ref{lem:regular-pair}, and hence we
  are done.
\end{proof}

We now restrict our attention to the pair~$(U,W)$ given by
Lemma~\ref{lem:regular-pair}.  We shall in fact obtain a contradiction by
estimating from above and from below the quantity
\begin{equation}
  \label{eq:def-sum-2}
  \left|\sumijUW\<\bfv_i,\bfv_j\>\right|,
\end{equation}
where~$\sum_{ij\in H}^{(U,W)}$ denotes sum over all edges~$ij\in H$ with~$i\in
U$ and~$j\in W$.  (The number of summands in~\eqref{eq:def-sum-2} is,
therefore, $e_H(U,W)$.)

We start by noticing that we have the following lower bound
for~(\ref{eq:def-sum-2}) from the definition of the edge set of~$H$ and the
fact that~$(U,W)$ is a `dense' pair for~$H$.

\begin{lemma}
  \label{lem:small-scalar-prod-sum-H}
  We have
  \begin{equation}
    \label{eq:small-scalar-prod-sum-H}
    \left|\sumijUW\<\bfv_i,\bfv_j\>\right|
     >\frac14\epsilon\gamma n\rho m^2.
  \end{equation}
\end{lemma}
\begin{proof}
  For any~$ij\in H$, by~\eqref{eq:ij-violation}, we have
  \begin{equation*}
    \<\bfv_i,\bfv_j\>=n-2|\Gamma_G(i)\symmdiff\Gamma_G(j)|
    >n-2\({1\over2}n-{1\over2}\epsilon n\)=\epsilon n.
  \end{equation*}
  Therefore, we have
  \begin{equation*}
    \sumijUW\<\bfv_i,\bfv_j\>>\epsilon ne_H(U,W)
    \geq{1\over4}\rho\epsilon\gamma nm^2,
  \end{equation*}
  since~$\dHr(U,W)\geq\gamma/4$ and hence~$e_H(U,W)\geq(1/4)\gamma\rho m^2$.  
  Inequality~\eqref{eq:small-scalar-prod-sum-H} is proved. 
\end{proof}

\begin{Remark}
  \label{rem:other_H_case}
  In the case in which~$H$ is the graph with edges~$ij$ for
  which~\eqref{eq:ij-violation-2} holds instead of~\eqref{eq:ij-violation}, we
  have
  \begin{equation*}
    \<\bfv_i,\bfv_j\>=n-2|\Gamma_G(i)\symmdiff\Gamma_G(j)|
    <n-2\({1\over2}n+{1\over2}\epsilon n\)=-\epsilon n.
  \end{equation*}
  Therefore, we would have
  \begin{equation*}
    \sumijUW\<\bfv_i,\bfv_j\><-\epsilon ne_H(U,W)
    \leq-{1\over4}\rho\epsilon\gamma nm^2,
  \end{equation*}
  and~\eqref{eq:small-scalar-prod-sum-H} would follow as well.  For the
  remainder of the proof, it will not matter whether the edges of~$H$
  satisfy~\eqref{eq:ij-violation} or~\eqref{eq:ij-violation-2}.  We shall only
  make use of~\eqref{eq:small-scalar-prod-sum-H}.
\end{Remark}

Our upper bound for~(\ref{eq:def-sum-2}) will come from the
$(1/2,\epsilon',\delta')$-quasi-randomness of~$G$ and the
$(\epsilon'',H,\rho)$-regularity of the pair~$(U,W)$.  More specifically, we
let
\begin{equation}
  \label{eq:defSkUW}
  \SkUW=\sumijUW a_{ik}a_{jk}
\end{equation}
for all~$k\in V$, and show that this sum is essentially always small, which
will tell us that~$\sumijUW\<\bfv_i,\bfv_j\>=\sum_{k\in V}\SkUW$ is quite
small. 

Let a vertex~$k\in V$ be given.  We then let
\begin{alignat}2
  U^+&=U_k^+=\Gamma_G(k)\cap U 
    &\qquad\quad U^-&=U_k^-=U\setminus\Gamma_G(k)  \\
  W^+&=W_k^+=\Gamma_G(k)\cap W
    &\qquad\quad W^-&=W_k^-=W\setminus\Gamma_G(k). 
\end{alignat}
Then, clearly, 
\begin{equation}
  \label{eq:SkUWis}
  \SkUW=e_H(U^+,W^+)+e_H(U^-,W^-)
        -e_H(U^+,W^-)-e_H(U^-,W^+).
\end{equation}
Moreover, for most~$k\in V$, we may estimate the four terms on the right-hand
side of~(\ref{eq:SkUWis}) by~$\sim\dHr(U,W)m^2/4$.

Indeed, let us say that a vertex~$k\in V\setminus(U\cup W)$ is
\textit{$(U,W)$-typical}, or simply \textit{typical}, if
\begin{equation}
  \label{eq:typical-cond}
  |U^+|,\ |U^-|,\ |W^+|,\ |W^-|
    =\frac12(1+O_1(\epsilon'))m\geq\epsilon''m. 
\end{equation}
Then, by the $(\epsilon'',H,\rho)$-regularity of the pair~$(U,W)$, we have
\begin{equation}
  \label{eq:approx_edge_nos}
  e_H(U^+,W^+),\,e_H(U^-,W^-),\,e_H(U^+,W^-),\,
  e_H(U^-,W^+)\sim{1\over4}\dHr(U,W)m^2
\end{equation}
for any typical~$k$.  Let us make this remark more precise. For simplicity,
let us write~$\sigma=\dHr(U,W)$, and $u^+=u_k^+=|U^+|$, $u^-=u_k^-=|U^-|$ and
similarly for~$w^+$ and~$w^-$.

Because~$r\geq r_1\geq(2AK_0)^2$, the graph~$H=H^n$ is a
$(1/2K_0,2)$-upper-uniform graph with respect to density~$\rho$ (cf.~the proof
of Lemma~\ref{lem:regular-pair}).  Therefore, we have
\begin{equation}
  \label{eq:sigma_at_most_2}
  \sigma=\dHr(U,W)\leq2,
\end{equation}
since~$|U|$, $|W|\geq(1/2K_0)n$.

From~(\ref{eq:typical-cond}) and the $(\epsilon'',H,\rho)$-regularity
of~$(U,W)$, we have
\begin{equation}
  \label{eq:eHU+W+}
  e_H(U^\alpha,W^\beta)=\(\sigma+O_1(\epsilon'')\)\rho u^\alpha w^\beta,
\end{equation}
for all~$\alpha$, $\beta\in\{+,-\}$.  In particular, if we know that~$k$ is
typical, we have 
\begin{equation}
  \label{eq:eHUW}
  e_H(U^+,W^+),\ e_H(U^-,W^-)
    \leq(\sigma+\epsilon'')\rho\left\{\frac12(1+\epsilon')m\right\}^2
\end{equation}
and
\begin{equation}
  \label{eq:eHUW2}
  e_H(U^+,W^-),\ e_H(U^-,W^+)
    \geq(\sigma-\epsilon'')\rho\left\{\frac12(1-\epsilon')m\right\}^2.
\end{equation}

A little computation now gives the first statement in the following lemma.
The second statement is immediate.

\begin{lemma}
  \label{lem:SkUWubd}
  \begin{enumerate}
  \item[(\textit{i})] For any $(U,W)$-typical vertex~$k\in V\setminus(U\cup
    W)$, we have  
    \begin{equation}
      \label{eq:SkUWupbd-typical-k}
      \left|\SkUW\right|=\left|\sumijUW a_{ik}a_{jk}\right|
             \leq2\rho m^2(\epsilon'\sigma+\epsilon'').
    \end{equation}
  \item[(\textit{ii})] For any vertex~$k\in V$, we have 
    \begin{equation}
      \label{eq:SkUWupbd-any-k}
      \left|\SkUW\right|=\left|\sumijUW a_{ik}a_{jk}\right|
             \leq\rho m^2+Am\sqrt r.
    \end{equation}
  \end{enumerate}
\end{lemma}
\begin{proof}
  Let us prove~(\textit{i}).  Let a $(U,W)$-typical vertex~$k$ be fixed.
  Using~\eqref{eq:SkUWis}, \eqref{eq:eHUW}, and~\eqref{eq:eHUW2}, we obtain
  \begin{equation*}
    \begin{split}
      \SkUW&=\sumijUW a_{ik}a_{jk}\\
      &\leq(\sigma+\epsilon'')\rho u^+w^++(\sigma+\epsilon'')\rho u^-w^-\\
      &\qquad\qquad\qquad
      -(\sigma-\epsilon'')\rho u^+w^--(\sigma-\epsilon'')\rho u^-w^+\\
      &\leq2(\sigma+\epsilon'')\rho\left\{{1\over2}(1+\epsilon')m\right\}^2
      -2(\sigma-\epsilon'')\rho\left\{{1\over2}(1-\epsilon')m\right\}^2\\
      &={1\over2}(\sigma+\epsilon'')\rho\(1+2\epsilon'+(\epsilon')^2\)m^2
      -{1\over2}(\sigma-\epsilon'')\rho\(1-2\epsilon'+(\epsilon')^2\)m^2\\
      &={1\over2}\sigma\rho m^2(4\epsilon')
      +{1\over2}\epsilon''\rho m^2(2+2(\epsilon')^2)\\
      &={1\over2}\rho m^2(4\epsilon'\sigma+\epsilon''(2+2(\epsilon')^2))\\
      &\leq2\rho m^2(\epsilon'\sigma+\epsilon''),
    \end{split}
  \end{equation*}
  and~(\textit{i}) is proved.  To prove~(\textit{ii}) it suffices to recall
  that~$H\subset J$ and that~$J$ is a $(\rho,A)$-uniform graph, and
  hence
  \begin{equation}
    \label{eq:ii_lemma69}
    \left|\SkUW\right|=\left|\sumijUW a_{ik}a_{jk}\right|
    \leq e_H(U,W)\leq e_J(U,W)\leq\rho m^2+Am\sqrt r, 
  \end{equation}
  as required.
\end{proof}

Our next lemma gives an upper bound for the quantity in~(\ref{eq:def-sum-2}).
The reader will immediately see that this upper bound is a consequence of
Lemma~\ref{lem:SkUWubd} and the fact that there are only very few atypical
vertices~$k$, because of the $(1/2,\epsilon',\delta')$-quasi-randomness
of~$G$. 

\begin{lemma}
  \label{lem:large-scalar-prod-sum-H}
  We have
  \begin{equation}
    \label{eq:large-scalar-prod-sum-H}
    \left|\sumijUW\<\bfv_i,\bfv_j\>\right|
     \leq2(2\delta'n+m)\(\rho m^2+Am\sqrt r\)
           +2\rho m^2n\(\epsilon'\sigma+\epsilon''\).
  \end{equation}
\end{lemma}
\begin{proof}
  We claim that the number of vertices~$k\in V\setminus(U\cup W)$ that are not
  $(U,W)$-typical is, by the $(1/2,\epsilon',\delta')$-quasi-randomness
  of~$G$, less than~$4\delta'n$.  Indeed, if we had~$\geq4\delta'n$ vertices
  that are not $(U,W)$-typical, then we would have~$\geq2\delta'n$ vertices
  that are not `typical' for either~$U$ alone or else for~$W$ alone.  In
  other words, we would have~$\geq2\delta'n$ vertices~$k\in V\setminus(U\cup
  W)$ for which, say,
  \begin{equation}
    \label{eq:U_wrong}
    |\Gamma_G(k)\cap U|=|U^+|>{1\over2}(1+\epsilon')m
  \end{equation}
  and hence~$|U\setminus\Gamma_G(k)|=|U^-|<(1/2)(1-\epsilon')m$, or else we
  would have~$\geq2\delta'n$ vertices~$k\in V\setminus(U\cup W)$ for which we
  have
  \begin{equation}
    \label{eq:U_wrong2}
    |\Gamma_G(k)\cap U|=|U^+|<{1\over2}(1-\epsilon')m
  \end{equation}
  and hence~$|U\setminus\Gamma_G(k)|=|U^-|>(1/2)(1+\epsilon')m$.  Therefore
  there would be~$\geq\delta'n$ vertices~$k\in V\setminus(U\cup W)$ for which,
  say, \eqref{eq:U_wrong}~holds.  Let~$T\subset V\setminus(U\cup W)$ be the
  set of such vertices~$k$.  Then
  \begin{equation}
    \label{eq:T_size_lwbd}
    |T|\geq\delta'n
  \end{equation}
  and
  \begin{equation}
    \label{eq:U_wrong_contra}
    e(T,U)>{1\over2}(1+\epsilon')|T|m={1\over2}(1+\epsilon')|T||U|.
  \end{equation}
  We also have
  \begin{equation}
    \label{eq:size_lwbd_for_contra}
    |U|=m\geq{n\over2K_0}\geq\delta_0n\geq\delta'n
  \end{equation}
  (see~\eqref{eq:delta_0_def}).
  Inequalities~\eqref{eq:T_size_lwbd}--\eqref{eq:size_lwbd_for_contra} say
  that the pair~$(T,U)$ is a witness against the
  $(1/2,\epsilon',\delta')$-quasi-randomness of~$G$.  This contradiction
  confirms that, indeed, the number of vertices~$k\in V\setminus(U\cup W)$
  that are not $(U,W)$-typical is less than~$4\delta'n$.
  
  Using~\eqref{eq:SkUWupbd-typical-k} for the $(U,W)$-typical vertices~$k\in
  V\setminus(U\cup W)$, and using~\eqref{eq:SkUWupbd-any-k} for the
  vertices~$k\in V\setminus(U\cup W)$ that are not $(U,W)$-typical and for all
  the vertices~$k\in U\cup W$, we have
  \begin{multline*}
    \left|\sumijUW\<\bfv_i,\bfv_j\>\right|
    =\left|\sum_{k\in V}\sumijUW a_{ik}a_{jk}\right|
    =\left|\sum_{k\in V}\SkUW\right|\\
    \leq(4\delta'n+2m)\(\rho m^2+Am\sqrt r\)
           +2\rho m^2n\(\epsilon'\sigma+\epsilon''\),
  \end{multline*}
  as required. 
\end{proof}

We finish the proof by deriving a contradiction comparing
Lemmas~\ref{lem:small-scalar-prod-sum-H}
and~\ref{lem:large-scalar-prod-sum-H}.  To that end, we first claim that 
\begin{equation}
  \label{eq:contra_bound}
  {1\over8}\gamma\epsilon
  >2\(2\delta_0+{1\over k_0}\)+\epsilon_0\sigma+\epsilon''
  \geq2\(2\delta'+{1\over k_0}\)+\epsilon'\sigma+\epsilon''.
\end{equation}
To prove our claim, we first observe that, because~$\delta'\leq\delta_0$
and~$\epsilon'\leq\epsilon_0$, the second inequality
in~\eqref{eq:contra_bound} is obvious.  As to the first inequality
in~\eqref{eq:contra_bound}, observe that, because of~\eqref{eq:delta_0_def},
we have
\begin{equation}
  \label{eq:p1}
  4\delta_0\leq{1\over2^5}\gamma\epsilon.
\end{equation}
Moreover, because of~\eqref{eq:k_0_def}, we have
\begin{equation}
  \label{eq:p2}
  {2\over k_0}\leq{1\over2^5}\gamma\epsilon.
\end{equation}
Since~$\sigma\leq2$ (see~\eqref{eq:sigma_at_most_2}), we have
from~\eqref{eq:epsilon_0_def} that
\begin{equation}
  \label{eq:p3}
  \epsilon_0\sigma\leq{1\over2^5}\gamma\epsilon.
\end{equation}
Inequalities~\eqref{eq:p1}--\eqref{eq:p3} and~\eqref{eq:epsilon_pp_def} imply
the first inequality in~\eqref{eq:contra_bound}.

We now recall inequalities~\eqref{eq:small-scalar-prod-sum-H}
and~\eqref{eq:large-scalar-prod-sum-H} to obtain that
\begin{multline}
  \label{eq:favour_bound}
  \frac14\epsilon\gamma n\rho m^2
  <\left|\sumijUW\<\bfv_i,\bfv_j\>\right|\\
  \leq2(2\delta'n+m)\(\rho m^2+Am\sqrt r\)
  +2\rho m^2n\(\epsilon'\sigma+\epsilon''\).
\end{multline}
Let us also recall that
\begin{equation}
  \label{eq:yet_again}
  Am\sqrt r\leq\rho m^2, 
\end{equation}
because~$r=\rho n\geq r_1\geq(2AK_0)^2$ and~$m\geq(1/2K_0)n$.  Moreover, the
fact that~$m\leq n/k$ gives us that
\begin{equation}
  \label{eq:m_lwbd2}
  2\delta'n+m\leq\(2\delta'+{1\over k}\)n\leq\(2\delta'+{1\over k_0}\)n.
\end{equation}
Inequalities~\eqref{eq:favour_bound}, \eqref{eq:yet_again},
and~\eqref{eq:m_lwbd} give that
\begin{multline}
  \label{eq:final_upbd0}
  \frac14\epsilon\gamma n\rho m^2
  \leq4(2\delta'n+m)\rho m^2+2\rho m^2n\(\epsilon'\sigma+\epsilon''\)\\
  \leq4\(2\delta'+{1\over k_0}\)\rho nm^2
  +2\rho m^2n\(\epsilon'\sigma+\epsilon''\).
\end{multline}
Dividing~\eqref{eq:final_upbd0} by~$2\rho m^2n$, we obtain
\begin{equation}
  \label{eq:contra_conclusion}
  \frac18\epsilon\gamma 
  \leq2\(2\delta'+{1\over k_0}\)+\epsilon'\sigma+\epsilon'',
\end{equation}
which contradicts~\eqref{eq:contra_bound}.

The proof of Theorem~\ref{thm:Main-2} is complete.

\bibliographystyle{amsplain}
\bibliography{/home/mac/yoshi/www/tem-fapesp-refs}


\end{document}
