%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% LaTeX2e file for the paper                                         %
%                                                                    %
% Algorithmic Aspects of Regularity                                  %
%                                                                    %
% by Y. Kohayakawa and V. R\"odl                                     %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Friday 07 Jan 2000 07:33:42pm EDT yoshi@jaca>   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass{llncs}
%\usepackage{amsmath,amsthm,amssymb}
\usepackage{amsmath,amssymb}
\newcommand{\BM}[1]{\mbox{\boldmath $#1$}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\ykcomm#1{\textsf{[#1]}}
\def\Triad{\mathop{\rm Triad}\nolimits}
\let\:=\colon
\let\rho=\varrho
\let\theta=\vartheta
\let\epsilon=\varepsilon
\def\veps{\vec{\epsilon}}
\def\vlambda{\vec{\lambda}}
\def\ycal#1{\mathcal{#1}}
\def\ind{\mathop{\rm ind}\nolimits}
\def\ex{\mathop{\rm ex}\nolimits}
\def\tildeex{\widetilde\ex}
\def\Exp{\mathop{\rm Exp}\nolimits}
\def\Prob{\mathop{\rm Prob}\nolimits}
\def\Vol{\mathop{\rm Vol}\nolimits}
\def\disc{\mathop{\rm disc}\nolimits}
\def\dev{\mathop{\rm dev}\nolimits}
\def\Aut{\mathop{\rm Aut}\nolimits}
\def\Forb{\mathop{\rm Forb}\nolimits}
\def\ind{{\rm ind}}
\def\Forbind{\Forb_\ind}
\def\({\left(}
\def\){\right)}
\def\|{|\!|}
\def\<{\langle}
\def\>{\rangle}
\def\cA{{\mathcal A}}
\def\cK{{\mathcal K}}
\def\cF{{\mathcal F}}
\def\cE{{\mathcal E}}
\def\bcE{\mbox{\boldmath $\mathcal E$}}
\def\scriptbcE{\kern.1em\lower.05ex\hbox{\scriptsize\boldmath$\mathcal E$}}
\def\cG{{\mathcal G}}
\def\cH{{\mathcal H}}
\def\cP{{\mathcal P}}
\def\cY{{\mathcal Y}}
\def\cS{{\mathcal S}}
\def\RR{{\mathbb R}}
\def\bfA{{\mathbf A}}
\def\bfW{{\mathbf W}}
\def\bfJ{{\mathbf J}}
\def\tU{{\widetilde U}}
\def\tW{{\widetilde W}}
%\def\tW{\hbox{
%    \llap{$\widetilde{\phantom U}$}
%    }
%  }
\def\tPi{{\widetilde\Pi}}
\def\MaxSNP{\textsc{MaxSNP}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newtheorem{_theorem}{Theorem}%[section]
\newtheorem{_lemma}[_theorem]{Lemma}
\newtheorem{_proposition}[_theorem]{Proposition}
\newtheorem{_corollary}[_theorem]{Corollary}
\newtheorem{_conjecture}[_theorem]{Conjecture}
\newtheorem{_claim}[_theorem]{Claim}
\newtheorem{_definition}[_theorem]{Definition}
\newtheorem{_problem}[_theorem]{Problem}
\newtheorem{fact}[_theorem]{Fact}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

\title{Algorithmic Aspects of Regularity}
\titlerunning{Algorithmic Aspects of Regularity}
\author{%
Y. Kohayakawa\inst{1}\thanks{Partially supported
    by FAPESP (Proc.~96/04505--2), by CNPq (Proc.~300334/93--1), and
    by MCT/FINEP (PRONEX project~107/97).}\and 
V. R\"odl\inst{2}
}
\institute{%
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}
\and  
Department of Mathematics and Computer Science,\\ 
Emory University, Atlanta, GA, 30322, USA\\
\email{rodl@mathcs.emory.edu}%
}
\authorrunning{Y. Kohayakawa and V. R\"odl}

\maketitle 

\begin{abstract}
  Szemer\'edi's celebrated regularity lemma proved to be a fundamental
  result in graph theory.  Roughly speaking, his lemma states that any
  graph may be approximated by a union of a bounded number of
  bipartite graphs, each of which is `pseudorandom'.  As later proved
  by Alon, Duke, Lefmann, R\"odl, and Yuster, there is a fast
  deterministic algorithm for finding such an approximation, and
  therefore many of the existential results based on the regularity
  lemma could be turned into constructive results.  In this survey, we
  discuss some recent developments concerning the algorithmic aspects
  of the regularity lemma.
\end{abstract}

\section{Introduction}
\label{sec:intro}
In the course of proving his well known density theorem for arithmetic
progressions~\cite{szemeredi75}, Szemer\'edi discovered a fundamental
result in graph theory.  This result became known as his
\textit{regularity lemma}~\cite{szemeredi76}.  For an excellent survey
on this lemma, see Koml\'os and Simonovits~\cite{KomlosSimonovits96}.
Roughly speaking, Szemer\'edi's lemma states that any graph may be
approximated by a union of a bounded number of bipartite
graphs, each of which is `pseudorandom'.

Szemer\'edi's proof did not provide an efficient algorithm for finding
such an approximation, but it was later proved by Alon, Duke, Lefmann,
R\"odl, and Yuster~\cite{AlonDLRY92,alon94} that such an algorithm
does exist.  Given the wide applicability of the regularity lemma, the
result of~\cite{AlonDLRY92,alon94} had many consequences.
The reader is referred
to~\cite{%
AlonDLRY92,alon94,%
DukeLefmannRodlcount,%
KomlosSimonovits96%,%
} for the first applications of the algorithmic version of the
regularity lemma.  For more recent applications, see~\cite{%
alon99:_refin_k,%
alon92:_yuster_GC,%
alon96:_yuster_JCTB,%
czygrinow99:_const_quasi_ramsey_number_tourn_rankin,%
%dor98:_greedy,%
fischer99:_cycle,%
haxell99:_integ,%
tiskin98:_bulk_boolean%,%
}.  

If the input graph~$G$ has~$n$ vertices, the algorithm
of~\cite{AlonDLRY92,alon94} runs in time $O(M(n))$,
where~$M(n)=O(n^{2.376})$ is the time needed to multiply two
$n$~by~$n$ matrices with $\{0,1\}$-entries over the integers.
In~\cite{kohayakawa00:_optimal_SzRL}, an improvement of this is given:
it is shown that there is an algorithm for the regularity lemma that
runs in time~$O(n^2)$ for graphs of order~$n$.

If one allows randomization, one may do a great deal better, as
demonstrated by Frieze and Kannan.  In fact, they show
in~\cite{FriezeKannanRL,frieze99:_quick_approx_matric_applic} that
there is a randomized algorithm for the regularity lemma that runs in
time~$O(n)$ for $n$-vertex graphs.  Quite surprisingly, they in fact
show that one may obtain an implicit description of the required
output in \textit{constant time}.  The key technique here is
\textit{sampling}. 

The regularity lemma has been generalized for hypergraphs in a few
different ways; see, \textit{e.g.}, \cite{%
chung91-regularity,%
frankl_rodl00:_extrem,%
frankl92,%
FriezeKannanRL,%
frieze99:_quick_approx_matric_applic,%
PSgen%,%
}.  One of these generalizations admits constructive versions, both
deterministic~\cite{%
czygrinow99:_algorithmic%,%
} and randomized~\cite{%
FriezeKannanRL,%
frieze99:_quick_approx_matric_applic%,%
}.  Again, the consequences of the existence of such algorithms are important.
For instance, Frieze and
Kannan~\cite{FriezeKannanRL,frieze99:_quick_approx_matric_applic} prove that
all `dense' {\MaxSNP}-hard problems admit PTAS, by making use of such
algorithms.  For other applications
of an algorithmic hypergraph regularity lemma, see Czygrinow~\cite{%
czygrinow99:_partit%,%
}.

Let us discuss the organization of this survey.  In
Section~\ref{sec:the_lemma}, we state the regularity lemma for graphs
and hypergraphs.  In Section~\ref{sec:conditions}, we discuss a few
independent lemmas, each of which allows one to produce algorithms for
the regularity lemma.  In Section~\ref{sec:Deterministic}, we state
the main result of~\cite{kohayakawa00:_optimal_SzRL}.  Some results of
Frieze and Kannan are discussed in Section~\ref{sec:Randomized}.  In
Section~\ref{sec:testing}, we discuss a recent result on property
testing on graphs, due to Alon, Fischer, Krivelevich, and
Szegedy~\cite{alon99:_effic_full,alon99:_effic}.  The main result
in~\cite{alon99:_effic_full,alon99:_effic} is based on a new variant
of the regularity lemma.  We close with some final remarks.

\section{The regularity lemma}
\label{sec:the_lemma}
In this section we state the regularity lemma and briefly discuss the original
proof of Szemer\'edi.  In order to be concise, we shall state a hypergraph
version that is a straightforward extension of the classical lemma.  We remark
that this extension was first considered and applied by Pr\"omel and
Steger~\cite{PSgen}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%In order to be concise, we shall state a hypergraph
%version of the lemma that specializes to the classical lemma in the case of
%graphs.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{The statement of the lemma}
\label{sec:state}
Given a set~$V$ and a non-negative integer~$r$, we write~$[V]^r$ for the
collection of subsets of~$V$ of cardinality~$r$.  An \textit{$r$-uniform
  hypergraph} or \textit{$r$-graph} on the \textit{vertex set}~$V$ is simply a
collection of $r$-sets $\cH\subset[V]^r$.  The elements of~$\cH$ are the
\textit{hyperedges} of~$\cH$

Let~$U_1,\dots,U_r\subset V$ be pairwise disjoint, non-empty subsets of vertices.  The
density~$d_\cH(U_1,\dots,U_r)$ of this $r$-tuple with respect~$\cH$ is
\begin{equation}
  \label{eq:def_density}
  d_\cH(U_1,\dots,U_r)={e(U_1,\dots,U_r)\over|U_1|\dots|U_r|},
\end{equation}
where~$e(U_1,\dots,U_r)$ is the number of hyperedges~$e\in\cH$ with~$|e\cap
U_i|=1$ for all~$1\leq i\leq r$.  We say that the $r$-tuple $(U_1,\dots,U_r)$
is \textit{$\epsilon$-regular} with respect to~$\cH$ if, for all choices of
subsets~$U_i'\subset U_i$ with $|U_i'|\geq\epsilon|U_i|$ for all~$1\leq i\leq
r$, we have
\begin{equation}
  \label{eq:def_regular}
  |d_\cH(U_1',\dots,U_r')-d_\cH(U_1,\dots,U_r)|\leq\epsilon.
\end{equation}
If for any such~$U_i'$ ($1\leq i\leq r$) we have
\begin{equation}
  \label{eq:def_alpha_delta_regular}
  |d_\cH(U_1',\dots,U_r')-\alpha|\leq\delta,
\end{equation}
we say that the $r$-tuple $(U_1,\dots,U_r)$ is
\textit{$(\alpha,\delta)$-regular}.  Finally, we say that a
partition~$V=V_0\cup\dots\cup V_k$ of the vertex set~$V$ of~$\cH$ is
\textit{$\epsilon$-regular} with respect to~$\cH$ if
\begin{enumerate}
\item[(\textit{i})]$|V_0|<\epsilon|V|$,
\item[(\textit{ii})]$|V_1|=\dots=|V_k|$,
\item[(\textit{iii})]at least~$(1-\epsilon){k\choose r}$ of the $r$-tuples
  $(V_{i_1},\dots,V_{i_r})$ with $1\leq i_1<\dots<i_r\leq k$ are
  $\epsilon$-regular with respect to~$\cH$.
\end{enumerate}
Often, $V_0$ is called the \textit{exceptional class} of the partition.  For
convenience, we say that a partition~$(V_i)_{i=0}^k$ is
\textit{$(\epsilon,k)$-equitable} if it satisfies~(\textit{i})
and~(\textit{ii}) above.  The hypergraph version of Szemer\'edi's lemma reads
as follows.

\begin{_theorem}
  \label{thm:Szem}
  For any integers~$r\geq2$ and~$k_0\geq1$ and real number~$\epsilon>0$, there
  are integers~$K=K(r,k_0,\epsilon)$ and~$N=N(r,k_0,\epsilon)$ such that any
  $r$-graph~$\cH$ on a vertex set of cardinality at least~$N$ admits an
  $(\epsilon,k)$-equitable $\epsilon$-regular partition with~$k_0\leq k\leq
  K$. 
\end{_theorem}

Szemer\'edi~\cite{szemeredi76} considered the case~$r=2$, that is, the case of
\textit{graphs}.  However, the proof in~\cite{szemeredi76} generalizes in a
straightforward manner to a proof of Theorem~\ref{thm:Szem} above; see
Pr\"omel and Steger~\cite{PSgen}, where the authors prove and apply
this result.

\subsection{Brief outline of proofs}
\label{sec:outline_proof}
Let~$\cH$ be an $r$-graph on the vertex set~$V$ with~$|V|=n$, and
let~$\Pi=(V_i)_{i=0}^k$ be an $(\epsilon,k)$-equitable partition of~$V$.  A
crucial definition in Szemer\'edi's proof of his lemma is the concept of the
\textit{index}~$\ind(\Pi)$ of~$\Pi$, given by
\begin{equation}
  \label{eq:def_index}
  \ind(\Pi)={k\choose r}^{-1}\sum d(V_{i_1},\dots,V_{i_r})^2,
\end{equation}
where the sum is taken over all $r$-tuples~$1\leq i_1<\dots<i_r\leq k$.
Clearly, we always have~$0\leq\ind(\Pi)\leq1$.  For convenience,
if~$\Pi'=(W_j)_{j=0}^\ell$ is an $(\epsilon',\ell)$-equitable partition
of~$V$, we say that~$\Pi'$ is a \textit{refinement} of~$\Pi$ if, for
any~$1\leq j\leq\ell$, there is~$1\leq i\leq k$ for which we have~$W_j\subset
V_i$.  In words, $\Pi'$ refines~$\Pi$ if any non-exceptional class of~$\Pi'$
is contained in some non-exceptional class of~$\Pi$.  Now, the key lemma in
the proof of Theorem~\ref{thm:Szem} is the following (see~\cite{PSgen}).

\begin{_lemma}
  \label{lem:main_lemma}
  For any integer~$r\geq2$ and real number~$\epsilon>0$, there exist integers
  $k_0=k_0(r,\epsilon)$ and $n_0=n_0(r,\epsilon)$ and a positive
  number~$\theta=\theta(r,\epsilon)>0$ for which the following holds.  Suppose
  we have an $r$-graph~$\cH$ on a vertex~$V$, with $n=|V|\geq n_0$,
  and~$\Pi=(V_i)_{i=0}^k$ is an $(\epsilon,k)$-equitable partition of~$V$.
  Then
  \begin{enumerate}
  \item[{\rm(\textit{i})}]either~$\Pi$ is $\epsilon$-regular with respect
    to~$\cH$,
  \item[{\rm(\textit{ii})}]or, else, there is a refinement
    $\Pi'=(W_j)_{j=0}^\ell$ of~$\Pi$ such that
    \begin{enumerate}
    \item[{\rm(\textit{a})}]$|W_0|\leq|V_0|+n/4^k$, 
    \item[{\rm(\textit{b})}]$|W_1|=\dots=|W_\ell|$,
    \item[{\rm(\textit{c})}]$\ell=k4^{k^{r-1}}$,
    \item[{\rm(\textit{d})}]$\ind(\Pi')\geq\ind(\Pi)+\theta$.
    \end{enumerate}
  \end{enumerate}
\end{_lemma}

Theorem~\ref{thm:Szem} follows easily from Lemma~\ref{lem:main_lemma}: it
suffices to recall that the index can never be larger than~$1$, and hence if
we successively apply Lemma~\ref{lem:main_lemma}, starting from an arbitrary
partition~$\Pi$, we must arrive at an $\epsilon$-regular partition after a
bounded number of steps, because~(\textit{d}) of alternative~(\textit{ii})
guarantees that the indices of the partitions that we generate always increase
by a fixed positive amount.

Ideally, to turn this proof into an efficient algorithm, given a
partition~$\Pi$, we would like to have (I)~an efficient procedure to check
whether~(\textit{i}) applies, and (II)~if (\textit{i})~fails, an efficient
procedure for finding~$\Pi'$ as specified in~(\textit{a})--(\textit{d}).  

It turns out that if we actually have, at hand, witnesses for the failure of
$\epsilon$-regularity of $>\epsilon{k\choose r}$ of the $r$-tuples
$(V_{i_1},\dots,V_{i_r})$, where~$1\leq i_1<\dots<i_r\leq k$, then~$\Pi'$ may
be found easily (see~\cite{PSgen} for details).  Here, by a \textit{witness}
for the $\epsilon$-irregularity of an $r$-tuple $(U_1,\dots,U_r)$ we mean an
$r$-tuple $(U_1',\dots,U_r')$ with~$U_i'\subset U_i$ and
$|U_i'|\geq\epsilon|U_i|$ for all~$1\leq i\leq r$ for
which~\eqref{eq:def_regular} fails.  We are therefore led to the following
decision problem:

\begin{_problem}
  \label{prob:decide}
  Given an $r$-graph~$\cH$, an $r$-tuple~$(U_1,\dots,U_r)$ of non-empty,
  pairwise disjoint sets of vertices of~$\cH$, and a real number~$\epsilon>0$,
  decide whether this $r$-tuple is $\epsilon$-regular with respect to~$\cH$.
\end{_problem}

In case 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 $r$-tuple.

\section{Conditions for regularity}
\label{sec:conditions}

\subsection{A hardness result}
\label{sec:hardness}
It turns out that Problem~\ref{prob:decide} is hard, as proved by Alon, Duke,
Lefmann, R\"odl, and Yuster~\cite{AlonDLRY92,alon94}.

\begin{_theorem}
  \label{thm:hardness_thm}
  Problem~\ref{prob:decide} is coNP-complete for~$r=2$.
\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}.

Theorem~\ref{thm:hardness_thm} is certainly discouraging.  Fortunately,
however, there is a way around.  We discuss the graph and hypergraph cases
separately.

\subsubsection{The graph case.}  In the case~$r=2$, that is, in the case of
graphs, one has the following lemma.  Below~$\RR_+$ denotes the set of
positive reals. Moreover, 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$ (see the paragraph before
Problem~\ref{prob:decide}).

\begin{_lemma}
  \label{lem:resolve_coNP_problem} 
  There is a polynomial-time algorithm~$\cA$ and a
  function~$\epsilon_\cA'\:\RR_+\to\RR_+$ such that the following holds.
  When~$\cA$ receives as input a bipartite graph~$B=(U,W;E)$ with~$|U|=|W|=n$
  and a real number~$\epsilon>0$, it either correctly asserts that~$B$ is
  $\epsilon$-regular, or else it returns a witness for the
  $\epsilon_\cA'(\epsilon)$-irregularity of~$B$.
\end{_lemma}

We remark that Lemma~\ref{lem:resolve_coNP_problem} implicitly says
that~$\epsilon'=\epsilon_\cA'(\epsilon)\leq\epsilon$, for otherwise~$\cA$
would not be able to handle an input graph~$B$ that is not $\epsilon$-regular
but is $\epsilon'$-regular.  In fact, one usually has~$\epsilon'\ll\epsilon$.

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.  We leave the proof of this assertion as an exercise for the reader. 

In Sections~\ref{sec:local}, \ref{sec:opt_local},
and~\ref{sec:singular} we state some independent results that imply
Lemma~\ref{lem:resolve_coNP_problem}, thus completing the general
description of a few distinct ways one may prove the algorithmic
version of the regularity lemma for graphs.

\subsubsection{The hypergraph case.}  In the case of $r$-graphs
($r\geq3$), we do not know a result similar to
Lemma~\ref{lem:resolve_coNP_problem}.  The algorithmic version of
Theorem~\ref{thm:Szem} for~$r\geq3$ is instead proved by introducing a
modified concept of index and then by proving a somewhat more
complicated version of Lemma~\ref{lem:resolve_coNP_problem}.  For lack
of space, we shall not go into details; the interested reader is
referred to Czygrinow and R\"odl~\cite{czygrinow99:_algorithmic}.  In
fact, in the remainder of this survey we shall mostly concentrate on
graphs.

Even though several applications are known for the
algorithmic version of Theorem~\ref{thm:Szem} for~$r\geq3$ (see,
\textit{e.g.}, \cite{czygrinow99:_partit,%
czygrinow99:_const_quasi_ramsey_number_tourn_rankin,%
czygrinow99:_algorithmic,%
FriezeKannanRL,frieze99:_quick_approx_matric_applic}), it should be
mentioned that the most powerful version of the regularity lemma for
hypergraphs is not the one presented above.  Indeed, the regularity
lemma for hypergraphs proved in~\cite{frankl_rodl00:_extrem} seems to
have deeper combinatorial consequences.

\subsection{The pair condition for regularity}
\label{sec:local}
As mentioned in Section~\ref{sec:hardness},
Lemma~\ref{lem:resolve_coNP_problem} may be proved in a few different
ways.  One technique is presented in this section.  The second, which
is in fact a generalization of the methods discussed here, is based on
Lemmas~\ref{lem:neu_L1} and~\ref{lem:neu_L2}.  Finally, the third
method, presented in Section~\ref{sec:singular}, is based on a
criterion for regularity given in Lemma~\ref{lem:FK_condition}.

Let us turn to the original approach of~\cite{AlonDLRY92,alon94}.  The
central idea here may be summarized in two lemmas,
Lemmas~\ref{lem:DLR_L1} and~\ref{lem:DLR_L2} below; we follow the
formulation given in~\cite{DukeLefmannRodlcount}
(see also~\cite{%
chung89,%
frankl88,%
thomason87,%
thomason87:_random%,%
} and the proof of the upper bound in Theorem~15.2 in~\cite{erd74:_probab},
due to J.$\,$H.~Lindsey).  Below, $d(x,x')$ denotes the \textit{joint degree}
or \textit{codegree} of~$x$ and~$x'$, that is, the number of common neighbours
of~$x$ and~$x'$.

\begin{_lemma}\label{lem:DLR_L1}
  Let a constant~$0<\epsilon<1$ be given and let $B=(U,W;E)$ be a bipartite
  graph with~$|U|\geq2/\epsilon$.  Let $\rho=d_B(U,W)$ and let~$D$ be the
  collection of all pairs $\{x,x'\}$ of vertices of $U$ for which
  \begin{enumerate}
  \item[{\rm(\textit{i})}] $d(x)$, $d(x')>(\rho-\epsilon)|W|$, 
  \item[{\rm(\textit{ii})}] $d(x,x')<(\rho+\epsilon)^2|W|$.
  \end{enumerate}
  Then if $|D|>(1/2)(1-5\epsilon)|W|^2$, the pair $(U,W)$ is
  $(\rho,(16\epsilon)^{1/5})$-regular.
\end{_lemma}

\begin{_lemma}\label{lem:DLR_L2}
  Let $B=(U,W;E)$ be a graph with $(U,W)$ a $(\rho,\epsilon)$-regular pair and
  with density $d(U,W)=\rho$.  Assume that~$\rho|W|\geq1$ and~$0<\epsilon<1$.
  Then
  \begin{enumerate}
  \item[{\rm(\textit{i})}] all but at most $2\epsilon|W|$ vertices $x\in W$
    satisfy
    $$
    (\rho-\epsilon)|W|<d(x),\;d(x')<(\rho+\epsilon)|W|,
    $$
  \item[{\rm(\textit{ii})}] all but at most $2\epsilon|U|^2$ pairs $\{x,x'\}$ of
    vertices of $A$ satisfy
    $$
    d(x,x')<(\rho+\epsilon)^2|W|.
    $$
  \end{enumerate}
\end{_lemma}

It is not difficult to see that Lemmas~\ref{lem:DLR_L1} and~\ref{lem:DLR_L2}
imply Lemma~\ref{lem:resolve_coNP_problem}.  Indeed, the main computational
task that algorithm~$\cA$ from Lemma~\ref{lem:resolve_coNP_problem} has to
perform is to compute the codegrees of all pairs of vertices $(x,x')\in
U\times U$.  Clearly, this may be done in time~$O(n^3)$.  Observing that this
task may be encoded as the squaring of a certain natural $\{0,1\}$-matrix over
the integers, one sees that there is an algorithm~$\cA$ as in
Lemma~\ref{lem:resolve_coNP_problem} with time complexity~$O(M(n))$,
where~$M(n)=O(n^{2.376})$ 
is the time required to carry out such a multiplication
(see~\cite{coppersmith90:_matrix}).

Before we proceed, let us observe that the pleasant fact here is the
following.  Although the definition of $\epsilon$-regularity for a
pair~$(U,W)$ involves a quantification over exponentially many
pairs~$(U',W')$, we may essentially check the validity of this
definition by examining all pairs~$(x,x')\in U\times U$, of which
there are only quadratically many.  We refer to the criterion for
regularity given by Lemmas~\ref{lem:DLR_L1} and~\ref{lem:DLR_L2} as
the \textit{pair condition for regularity}.

\subsection{An optimized pair condition for regularity}
\label{sec:opt_local}
Here we state an improved version of the pair condition of
Section~\ref{sec:local}.  The key idea is that it suffices to control
the codegrees of a small, suitably chosen set of pairs of vertices to
guarantee the regularity of a bipartite graph; that is, we need not
examine all pairs $(x,x')\in U\times U$.  As it turns out, it suffices
to consider the pairs that form the edge set of a linear-sized
expander, which reduces the number of pairs to examine
from~${n\choose2}$ to~$O(n)$.  This implies that there is an
algorithm~$\cA$ as in Lemma~\ref{lem:resolve_coNP_problem} with time
complexity~$O(n^2)$.  %[Lift from Lubo\v s]

We start with an auxiliary definition.

\begin{_definition}
  \label{def:uniformity}
  Let~$0<\rho\leq1$ and $A>0$ be given.  We say that a graph~$J$ on~$n$
  vertices is \textsl{$(\rho,A)$-uniform} if for any pair of disjoint
  sets~$U$, $W\subset V(J)$ such that $1\leq|U|\leq|W|\leq r|U|$,
  where~$r=\rho n$, we have 
  $$
  \big|e_J(U,W)-\rho|U||W|\big|\leq A\sqrt{r|U||W|}\;.
  $$
\end{_definition} 

Thus, a $(\rho,A)$-uniform graph is a graph with density $\sim\rho$ in
which the edges are distributed in a random-like manner.  One may
check that the usual binomial random graph~$G(n,p)$ is
$(p,20)$-uniform (see, \textit{e.g.}, \cite{HKL}).  More relevant to
us is the fact that there are efficiently constructible graphs~$J$
that are $(\rho,O(1))$-uniform, and have arbitrarily large but
constant average degree.  Here we have in mind the celebrated graphs
of Margulis~\cite{margulis88:_explic} and Lubotzky, Phillips, and
Sarnak~\cite{LPS} (see also~\cite{lubotzky94:_discr,sarnak90:_some}).
For these graphs, we have~$A=2$.

Let us now introduce the variant of the pair condition for regularity
that is of interest.  Let an $n$~by~$n$ bipartite graph~$B=(U,W;E)$ be
given, and suppose that~$J$ is a graph on~$U$.  Write~$e(J)$ for the
number of edges in~$J$ and let~$p=e(B)/n^2$ be the density of~$B$.  We
say that~$B$ satisfies property~$\cP(J,\delta)$ if
\begin{equation}
  \label{eq:def_cP}
  \sum_{\{x,y\}\in E(J)}|d(x,y)-p^2n|\leq\delta p^2ne(J).
\end{equation}
Below, we shall only be interested in the case in which~$J$
is $(\rho,A)$-uniform for some constant~$A$ and $\rho\asymp1/n$.  The results
analogous to Lemmas~\ref{lem:DLR_L1} and~\ref{lem:DLR_L2} involving
property~$\cP$ are as follows.

\begin{_lemma}
  \label{lem:neu_L1} 
  For every~$\epsilon>0$, there exist~$r_0=r_0(\epsilon)$,
  $n_0=n_0(\epsilon)\geq1$, and~$\delta=\delta(\epsilon)>0$ for which the
  following holds.  Suppose~$n\geq n_0$, the graph~$J$ is a $(\rho,A)$-uniform
  graph with~$\rho=r/n\geq r_0/n$, and~$B$ is a bipartite graph as above.
  Then, if~$B$ has property~$\cP(J,\delta)$, then $B$ is $\epsilon$-regular.
\end{_lemma} 

\begin{_lemma}
  \label{lem:neu_L2}
  For every~$\delta>0$, there exist~$r_1=r_1(\delta)$, $n_1=n_1(\delta)\geq1$,
  and~$\epsilon'=\epsilon'(\delta)>0$ for which the following holds.
  Suppose~$n\geq n_1$, the graph~$J$ is a $(\rho,A)$-uniform graph
  with~$\rho=r/n\geq r_1/n$, and~$B$ is a bipartite graph as above.  Then,
  if~$B$ does not satisfy property~$\cP(J,\delta)$, then~$B$ is not
  $\epsilon'$-regular.  Furthermore, in this case, we can find a pair of sets
  of vertices~$(U',W')$ witnessing the $\epsilon'$-irregularity of~$B$ in
  time~$O(n^2)$.
\end{_lemma} 

Lemmas~\ref{lem:neu_L1} and~\ref{lem:neu_L2} show that
Lemma~\ref{lem:resolve_coNP_problem} holds for an algorithm~$\cA$ with
time complexity~$O(n^2)$.  

The proof of Lemma~\ref{lem:neu_L1} is similar in spirit to the proof
of Lemma~\ref{lem:DLR_L1}, but of course one has to make heavy use of
the $(\rho,A)$-uniformity of~$J$.  The sparse version of the
regularity lemma (see, \textit{e.g.}, \cite{Kohayakawa97Szemeredi})
may be used to prove the $\epsilon'$-irregularity of the graph~$B$ in
Lemma~\ref{lem:neu_L2}.  However, proving that a suitable witness may
be found in quadratic time requires a different approach.  The reader
is referred to~\cite{kohayakawa00:_optimal_SzRL} for details.

%\bigskip\medskip\hrule

\subsection{Singular values and regularity}
\label{sec:singular}
We now present an approach due to Frieze and
Kannan~\cite{frieze99:_constructive_SzRL}.  Let an $m$~by~$n$ real
matrix~$\bfA$ be given.  The \textit{first singular
  value}~$\sigma_1(\bfA)$ of~$\bfA$ is
\begin{equation}
  \label{eq:def_singular}
  \sigma_1(\bfA)=\sup\{|x^\top\bfA y|\:\|x\|=\|y\|=1\}.
\end{equation}
Above, we use~$\|\hphantom x\|$ to denote the $2$-norm.  In what
follows, for a matrix~$\bfW=(w_{i,j})$, we
let~$\|\bfW\|_\infty=\max|w_{i,j}|$.  Moreover, if~$I$ and~$J$ are
subsets of the index sets of the rows and columns of~$\bfW$, we let
\begin{equation}
  \label{eq:def_W(I,J)}
  \bfW(I,J)=\sum_{i\in I,j\in J}w_{i,j}
  =\chi_I^\top\bfW\chi^{\vphantom\top}_J,
\end{equation}
where~$\chi_I$ and~$\chi_J$ are the $\{0,1\}$-characteristic vectors
for~$I$ and~$J$.  

Let~$B=(U,W;E)$ be a bipartite graph with density~$p=e(B)/|U||W|$, and
let~$\bfA=(a_{i,j})_{i\in U,j\in W}$ be the natural
$\{0,1\}$-adjacency matrix associated with~$B$.
Put~$\bfW=\bfA-p\bfJ$, where~$\bfJ$ is the $n\times n$ matrix with all
entries equal to~$1$.  It is immediate to check that the following
holds: 
\begin{enumerate}
\item[(*)]$B$ is $\epsilon$-regular if and only if
  $|\bfW(U',W')|\leq\epsilon|U'||W'|$ for all~$U'\subset U$
  and~$W'\subset W$ with~$|U'|\geq\epsilon|U|$
  and~$|W'|\geq\epsilon|W|$. 
\end{enumerate}
The regularity condition of Frieze and
Kannan~\cite{frieze99:_constructive_SzRL} is as follows.

\begin{_lemma}
  \label{lem:FK_condition}
  Let~$\bfW$ be a matrix whose entries are index by~$U\times W$,
  where~$|U|=|W|=n$, and suppose that~$\|\bfW\|_\infty\leq1$.
  Let~$\gamma>0$ be given.  Then the following assertions hold{\rm:}
  \begin{enumerate}
  \item[{\rm(\textit{i})}]If there exist $U'\subset U$ and $W'\subset
    W$ such that $|U'|$, $|W'|\geq\gamma n$ and
    $$
    |\bfW(U',W')|\geq\gamma|U'||W'|,
    $$
    then $\sigma_1(\bfW)\geq\gamma^3n$.
  \item[{\rm(\textit{ii})}]If $\sigma_1(\bfW)\geq\gamma n$, then there
    exist $U'\subset U$ and $W'\subset W$ such that $|U'|$,
    $|W'|\geq\gamma'n$ and 
    $
    |\bfW(U',W')|\geq\gamma'|U'||W'|,
    $
    where $\gamma'=\gamma^3/108$.  Furthermore, $U'$ and $W'$ may
    be constructed in polynomial time.
  \end{enumerate}
\end{_lemma}

Now, in view of~(*) and the fact that singular values may be computed
in polynomial time (see, \textit{e.g.},
\cite{golub89:_matrix_comput}), Lemma~\ref{lem:FK_condition} provides
a proof for Lemma~\ref{lem:resolve_coNP_problem}.

\section{The algorithmic versions of regularity}
\label{sec:algorithmic_versions}

In this section, we discuss the constructive versions of
Theorem~\ref{thm:Szem} for the graph case, that is~$r=2$.  We discuss
deterministic and randomized algorithms separately.

\subsection{Deterministic algorithms}
\label{sec:Deterministic}

Our deterministic result, Theorem~\ref{thm:Szem_in_quadratic_time} below,
asserts the existence of an algorithm for finding regular partitions that is
asymptotically faster than the algorithm due to Alon, Duke, Lefmann, R\"odl,
and Yuster~\cite{AlonDLRY92,alon94}.

\begin{_theorem}
  \label{thm:Szem_in_quadratic_time}
  There is an algorithm~$\cA$ that takes as input an
  integer~$k_0\geq1$, an~$\epsilon>0$, and a graph~$G$ on $n$~vertices
  and returns an $\epsilon$-regular $(\epsilon,k)$-equitable partition
  for~$G$ with~$k_0\leq k\leq K$, where~$K$ is as
  Theorem~\ref{thm:Szem}.  Algorithm~$\cA$ runs in time~$\leq Cn^2$,
  where~$C=C(\epsilon,k_0)$ depends only on~$\epsilon$ and~$k_0$.
\end{_theorem}

Theorem~\ref{thm:Szem_in_quadratic_time} follows from the considerations in
Sections~\ref{sec:hardness} and~\ref{sec:opt_local}
(see~\cite{kohayakawa00:_optimal_SzRL} for details).

It is easy to verify that there is a
constant~$\epsilon'=\epsilon'(\epsilon,k_0)$ such that
if~$e(G)<\epsilon'n^2$, then \textit{any} $(\epsilon,k_0)$-equitable
partition is $\epsilon$-regular.  Clearly, as the time required to
read the input is~$\Omega(e(G))$ and, as observed above, we may assume
that~$e(G)\geq\epsilon'n^2$, algorithm~$\cA$ in
Theorem~\ref{thm:Szem_in_quadratic_time} is optimal, apart from the
value of the constant~$C=C(\epsilon,k_0)$.

A typical application of the algorithmic regularity lemma
of~\cite{AlonDLRY92,alon94} asserts the existence of a fast algorithm
for a graph problem.  As it turns out, the running time of such an
algorithm is often dominated by the time required for finding a
regular partition for the input graph, and hence the algorithm has
time complexity~$O(M(n))$.  In view of
Theorem~\ref{thm:Szem_in_quadratic_time}, the existence of quadratic
algorithms for these problems may be asserted.  Some examples are
given in~\cite{kohayakawa00:_optimal_SzRL}.

\subsection{Randomized algorithms}
\label{sec:Randomized}
We have been discussing deterministic algorithms so far.  If we allow
randomization, as proved by Frieze and Kannan, a great deal more may
be achieved in terms of
efficiency~\cite{FriezeKannanRL,frieze99:_quick_approx_matric_applic}.
The model we adopt is as follows.  We assume that sampling a random
vertex from~$G$ as well as checking an entry of the adjacency matrix
of~$G$ both have unit cost.

\begin{_theorem}
  \label{thm:Szem_in_linear_time}
  There is a randomized algorithm~$\cA_{{\rm FK}}$ that takes as input
  an integer~$k_0\geq1$, an~$\epsilon>0$, a~$\delta>0$, and a
  graph~$G$ on $n$~vertices and returns, with
  probability~$\geq1-\delta$, an $\epsilon$-regular
  $(\epsilon,k)$-equitable partition for~$G$ with~$k_0\leq k\leq K$,
  where~$K$ is as Theorem~\ref{thm:Szem}.  Moreover, the following
  assertions hold{\rm:}
  \begin{enumerate}
  \item[{\rm(\textit{i})}]Algorithm~$\cA_{{\rm FK}}$ runs in
    time~$\leq Cn$, where~$C=C(\epsilon,\delta,k_0)$ depends only
    on~$\epsilon$, $\delta$, and~$k_0$.
  \item[{\rm(\textit{ii})}]In fact, $\cA_{{\rm FK}}$ first outputs
    a collection of vertices of~$G$ of cardinality~$\leq C'$,
    where~$C'=C'(\epsilon,\delta,k_0)$ depends only on~$\epsilon$,
    $\delta$, and~$k_0$, and the above $\epsilon$-regular partition
    for~$G$ may be constructed in linear time from this collection of
    vertices.
  \end{enumerate}
\end{_theorem}

The fact that one is able to construct a regular partition for a graph on~$n$
vertices in randomized time~$O(n)$ is quite remarkable; this is another
evidence of the power of randomization.  However, even more remarkable is
what~(\textit{ii}) implies: given~$\epsilon>0$, $\delta>0$, and~$k_0\geq1$,
there is a uniform bound~$C'=C'(\epsilon,\delta,k_0)$ on the number of
randomly chosen vertices
that will implicitly define for us a suitable $\epsilon$-regular
partition of the given graph, \textit{no matter how large this input graph is}.

Let us try to give a feel on how one may proceed to prove
Theorem~\ref{thm:Szem_in_linear_time}.  We shall discuss a lemma that is
central in the Frieze--Kannan approach.  The idea is that, if a bipartite
graph~$B=(U,W;E)$ is not $\epsilon$-regular, then this may be detected, with
high probability, by sampling a bounded number of vertices of~$B$.  The
effectiveness of sampling for detecting ``dense spots'' in graphs appears
already in
Goldreich, Goldwasser, and Ron~\cite{goldreich96:_proper,%
goldreich98:_proper%,%
}, where many \textit{constant time} algorithms are developed (we shall
discuss such matters in Section~\ref{sec:testing} below).

Let us state the key technical lemma in the proof of
Theorem~\ref{thm:Szem_in_linear_time}.  Let an $n$~by~$n$ bipartite
graph~$B=(U,W;E)$ be given.  Our aim is to check whether there
exist~$U'\subset U$ and~$W'\subset W$ such that $|U'|$, $|W'|\geq\epsilon n$
and 
$$
|d_B(U',W')-d_B(U,W)|>\epsilon.
$$
Note that this last inequality is equivalent
to~$\big|e(U',W')-p|U'||W'|\big|>\epsilon|U'||W'|$, where~$p=e(B)/n^2$ is the
density of~$B$.  In fact, if
$$
%  \label{eq:alternative_ineq}
  \big|e(U',W')-p|U'||W'|\big|>\gamma n^2
$$
holds and~$\gamma\geq\epsilon$, then~$(U',W')$ must be a witness for the
$\epsilon$-irregularity of~$B$.

We are now ready to state the result of Frieze and Kannan that allows one to
prove a randomized version of Lemma~\ref{lem:resolve_coNP_problem}.  The
reader may wish to compare this result with Lemmas~\ref{lem:DLR_L2}
and~\ref{lem:neu_L2}.

\begin{_lemma}
  \label{lem:witness_in_constant_time}
  There is a randomized algorithm~$\cA$ that behaves as follows.
  Let~$B=(U,W;E)$ be as above and let~$\gamma$ and~$\delta>0$ be positive
  reals.  Suppose there exist~$U'\subset U$ and~$W'\subset W$ for which
  $e(U',W')>p|U'||W'|+\gamma n^2$ holds.  Then, on input~$B$, $\gamma>0$,
  and~$\delta>0$, algorithm~$\cA$ determines, with probability~$\geq1-\delta$,
  implicitly defined sets~$U''\subset U$ and~$W''\subset W$ with
  $$
  e(U'',W'')>p|U''||W''|+{1\over16}\gamma n^2.
  $$
  The running time of~$\cA$ is bounded by some constant~$C=C(\gamma,\delta)$
  that depends only on~$\gamma$ and~$\delta$.
\end{_lemma}

A few comments concerning Lemma~\ref{lem:witness_in_constant_time} are in
order.  As before, the model here allows for the selection of random vertices
of~$B$ as well as checking whether two given vertices are adjacent in constant
time.  In order to define the sets~$U''$ and~$W''$, algorithm~$\cA$ returns
two sets~$Z_1\subset U$ and~$Z_2\subset W$, both of cardinality bounded by
some constant depending only on~$\gamma$ and~$\delta>0$.  Then, $U''$ is
simply the set of vertices~$u\in U$ for which
$
e(u,Z_2)\geq p|Z_2|.
$
The set~$W''$ is defined analogously.  

Algorithm~$\cA$ of Lemma~\ref{lem:witness_in_constant_time} is extremely
simple, and its elegant proof of correctness is based on the linearity of
expectation and on well known large deviation inequalities (see Frieze and
Kannan~\cite{FriezeKannanRL}).  

We close this section mentioning a result complementary to
Lemma~\ref{lem:witness_in_constant_time} (see \cite{RodlDuke} for a slightly
weaker statement).  Suppose~$B=(U,W;E)$ is $\epsilon$-regular.  Then
if~$U'\subset U$ and~$W'\subset W$ are randomly chosen sets of vertices
with~$|U'|=|W'|\geq M_0=M_0(\epsilon',\delta)$, then the bipartite
graph~$B'=(U',W';E')$ induced by~$B$ on~$(U',W')$ is $\epsilon'$-regular with
probability~$\geq1-\delta$, as long
as~$\epsilon\leq\epsilon_0(\epsilon',\delta)$.  Here again the striking fact
is that a bounded sample of vertices forms a good enough picture of the whole
graph.

\section{Property testing}
\label{sec:testing}
The topic of this section is in nature different from the topics
discussed so far.  We have been considering how to produce algorithms
for finding regular partitions of graphs.  In this section, we discuss
how non-constructive versions of the regularity lemma may be used to
prove the correctness of certain algorithms.  We shall discuss a
recent result 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.

\subsection{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 
$$
d(G,\cP)=\min_{H\in\cP}d(G,H)\geq\epsilon,
$$
that is, at least~$\epsilon{n\choose2}$ edges have to be added or
removed to~$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 
$$
\exists x_1,\dots,x_r\;\forall y_1,\dots,y_s\;
A(x_1,\dots,x_r,y_1,\dots,y_s),
$$
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
  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.

\subsection{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~$\Pi=(V_i)_{i=1}^k$ of a set~$V$ is an
\textit{equipartition} of~$V$ if all the sets~$V_i$ ($1\leq i\leq k$)
differ by at most~$1$ in size.  In this section, we shall not have
exceptional classes in our partitions.  Below, we shall have 
an equipartition of~$V$ 
$$
\Pi'=\{V_{i,j}\:1\leq i\leq k,\;1\leq j\leq\ell\}
$$
that is a refinement of a given partition~$\Pi=(V_i)_{i=1}^k$.  In
this notation, we understand that, for all~$i$, all the $V_{i,j}$
($1\leq j\leq\ell$) are contained in~$V_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~$\Pi=(V_i)_{1\leq i\leq k}$
  and~$\Pi'=(V_{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})}]$|\Pi|=k\geq k_0$ and~$|\Pi'|=k\ell\leq K$;
  \item[{\rm(\textit{ii})}]at least~$(1-\epsilon(0)){k\choose2}$ of
    the pairs~$(V_i,V_{i'})$ with~$1\leq i<i'\leq k$ are
    $\epsilon(0)$-regular;
  \item[{\rm(\textit{iii})}]for all~$1\leq i<i'\leq k$, we have that
    at least~$(1-\epsilon(k))\ell^2$ of the pairs~$(V_{i,j},V_{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(V_i,V_{i'})-d_G(V_{i,j},V_{i',j'})|\leq\epsilon(0).
    $$
  \end{enumerate}
\end{_theorem}

Suppose we have partitions~$\Pi$ and~$\Pi'$ 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~$\tPi=(V_{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~$(V_{i,j(i)},V_{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(V_i,V_{i'})-d_G(V_{i,j(i)},V_{i',j(i')})|\leq\epsilon(0).
  $$
\end{enumerate}
In a certain sense, this consequence of
Theorem~\ref{thm:alon_et_al_regularity} lets us ignore the irregular pairs in
the partition~$\Pi$, at the expense of dropping down from the~$V_i$ to smaller
sets~$V_{i,j(i)}$ (still all of cardinality~$\Omega(n)$), and having most but
not necessarily all densities~$d_G(V_{i,j(i)},V_{i',j(i')})$ under tight
control.  

Let us remark in passing that, naturally, one may ask whether
Theorem~\ref{thm:Szem} may be strengthened by requiring that there should be
\textit{no} irregular pairs altogether.  This question was already raised by
Szemer\'edi in~\cite{szemeredi76}.  As observed by Lov\'asz, Seymour,
Trotter, and the authors of~\cite{alon94} (see~p.~82 in~\cite{alon94}), such
an extension of Theorem~\ref{thm:Szem} does not exist.  As noted above,
Theorem~\ref{thm:alon_et_al_regularity} presents a way around this difficulty.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%It is in view of this that it is interesting that
%Theorem~\ref{thm:alon_et_al_regularity} allows one to get rid of the irregular
%pairs.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

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, 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{Concluding remarks}
\label{sec:concluding}

We have not discussed a few recent, important results that relate to the
regularity lemma.  We single out three topics that the reader may wish to
pursue.

\subsection{Constants}
\label{sec:constants}
The constants involved in Theorem~\ref{thm:Szem} are extremely large.  The
proof in~\cite{szemeredi76} gives that~$K$ in Theorem~\ref{thm:Szem} is
bounded from above by a tower of~$2$s of height~$\epsilon^{-5}$.  A recent
result of Gowers~\cite{gowers97:_lower} in fact shows that this cannot be
essentially improved.  Indeed, it is proved in~\cite{gowers97:_lower} that
there are graphs for which any $\epsilon$-regular partition must have at
least~$G(\epsilon^{-c})$ parts, where~$c>0$ is some absolute constant
and~$G(x)$ is a tower of~$2$s of height~$\lfloor x\rfloor$.

The size of~$K$ is very often not too relevant in applications, but in certain
cases essentially better results may be obtained if one is able to avoid the
appearance of such huge constants.  In view of Gowers's result, this can only
be accomplished by modifying the regularity lemma.  One early instance in
which this carried out appears in~\cite{DukeLefmannRodlcount}; a more recent
example is~\cite{FriezeKannanRL}.

\subsection{Approximation schemes for dense problems}
\label{sec:Frieze-Kannan_applications}
Frieze and Kannan have developed variants of the regularity lemma for
graphs and hypergraphs and discuss several applications
in~\cite{FriezeKannanRL,frieze99:_quick_approx_matric_applic}.  The
applications are mostly algorithmic and focus on `dense' problems,
such as the design of a PTAS for the max-cut problem for dense graphs.
The algorithmic versions of their variants of the regularity lemma
play a central r\^ole in this approach.

For more applications of algorithmic regularity to `dense' problems,
the reader is referred to~\cite{czygrinow99:_partit,%
czygrinow99:_const_quasi_ramsey_number_tourn_rankin,%
czygrinow99:_algorithmic,%
haxell99:_integ%,%
}

\subsection{The blow-up lemma}
\label{sec:blow-up}
We close with an important lemma due to Koml\'os, S\'ark\"ozy, and
Szemer\'edi~\cite{komlos97:_blow}, the so-called \textit{blow-up
  lemma}.  (For an alternative proof of this lemma,
see~\cite{rodl99:_perfec_blow_lemma}.)

In typical applications of the regularity lemma, once a suitably
regular partition of some given graph~$G$ is found, one proceeds by
embedding some `target graph'~$H$ of bounded degree into~$G$.  Until
recently, the embedding techniques could only handle graphs~$H$ with
many fewer vertices than~$G$.  The blow-up lemma is a novel tool that
allows one to embed target graphs~$H$ that even have the same number
of vertices as~$G$.  The combined use of the regularity lemma and the
blow-up lemma is a powerful new machinery in graph theory.  The reader
is referred to Koml\'os~\cite{komlos99} for a discussion on the
applications of the blow-up lemma.

On the algorithmic side, the situation is good: Koml\'os, S\'ark\"ozy,
and Szemer\'edi~\cite{komlos98} have also proved an algorithmic
version of the blow-up lemma (see R\"odl, Ruci\'nski, and
Wagner~\cite{roedl98:_algorithmic_blowup} for an alternative proof).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\bibliographystyle{amsplain}
%\bibliography{/home/mac/yoshi/www/tem-fapesp-refs}
%\bibliography{tem-fapesp-refs}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace}
\begin{thebibliography}{10}

\bibitem{AlonDLRY92}
N.~Alon, R.~A. Duke, H.~Lefmann, V.~R{\"o}dl, and R.~Yuster, \emph{The
  algorithmic aspects of the regularity lemma (extended abstract)}, 33rd Annual
  Symposium on Foundations of Computer Science (Pittsburgh, Pennsylvania), IEEE
  Comput. Soc. Press, 1992, pp.~473--481.

\bibitem{alon94}
\bysame, \emph{The algorithmic aspects of the regularity lemma}, Journal of
  Algorithms \textbf{16} (1994), no.~1, 80--109.

\bibitem{alon99:_effic_full}
N.~Alon, E.~Fischer, M.~Krivelevich, and M.~Szegedy, \emph{Efficient testing of
  large graphs}, submitted, 22pp., 1999.

\bibitem{alon99:_effic}
\bysame, \emph{Efficient testing of large graphs (extended abstract)}, 40th
  Annual Symposium on Foundations of Computer Science (New York City, NY), IEEE
  Comput. Soc. Press, 1999, pp.~656--666.

\bibitem{alon99:_refin_k}
N.~Alon and E.~Fischer, \emph{Refining the graph density condition for the
  existence of almost ${K}$-factors}, Ars Combinatoria \textbf{52} (1999),
  296--308.

\bibitem{alon92:_yuster_GC}
N.~Alon and R.~Yuster, \emph{Almost ${H}$-factors in dense graphs}, Graphs and
  Combinatorics \textbf{8} (1992), no.~2, 95--102.

\bibitem{alon96:_yuster_JCTB}
\bysame, \emph{${H}$-factors in dense graphs}, Journal of Combinatorial Theory,
  Series B \textbf{66} (1996), no.~2, 269--282.

\bibitem{chung91-regularity}
F.~R.~K. Chung, \emph{Regularity lemmas for hypergraphs and quasi-randomness},
  Random Structures and Algorithms \textbf{2} (1991), no.~1, 241--252.

\bibitem{chung89}
F.~R.~K. Chung, R.~L. Graham, and R.~M. Wilson, \emph{Quasi-random graphs},
  Combinatorica \textbf{9} (1989), no.~4, 345--362.

\bibitem{coppersmith90:_matrix}
D.~Coppersmith and S.~Winograd, \emph{{Matrix multiplication via arithmetic
  progressions.}}, Journal of Symbolic Computation \textbf{9} (1990), no.~3,
  251--280.

\bibitem{czygrinow99:_partit}
A.~Czygrinow, \emph{Partitioning problems in dense hypergraphs}, submitted,
  1999.

\bibitem{czygrinow99:_const_quasi_ramsey_number_tourn_rankin}
A.~Czygrinow, S.~Poljak, and V.~R\"odl, \emph{Constructive quasi-{R}amsey
  numbers and tournament ranking}, SIAM Journal on Discrete Mathematics
  \textbf{12} (1999), no.~1, 48--63.

\bibitem{czygrinow99:_algorithmic}
A.~Czygrinow and V.~R\"odl, \emph{An algorithmic regularity lemma for
  hypergraphs}, submitted, 1999.

\bibitem{DukeLefmannRodlcount}
R.~A. Duke, H.~Lefmann, and V.~R\"odl, \emph{A fast approximation algorithm for
  computing the frequencies of subgraphs in a given graph}, SIAM Journal on
  Computing \textbf{24} (1995), no.~3, 598--620.

\bibitem{RodlDuke}
R.~A. Duke and V.~R\"odl, \emph{On graphs with small subgraphs of large
  chromatic number}, Graphs and Combinatorics \textbf{1} (1985), no.~1, 91--96.

\bibitem{erd74:_probab}
P.~Erd{\H o}s and J.~Spencer, \emph{Probabilistic methods in combinatorics},
  Akademiai Kiado, Budapest, 1974, 106pp.

\bibitem{fischer99:_cycle}
E.~Fischer, \emph{Cycle factors in dense graphs}, Discrete Mathematics
  \textbf{197/198} (1999), 309--323, 16th {B}ritish {C}ombinatorial
  {C}onference ({L}ondon, 1997).

\bibitem{frankl_rodl00:_extrem}
P.~Frankl and V.~R{\"o}dl, \emph{Extremal problems on set systems}, Random
  Structures and Algorithms, to appear.

\bibitem{frankl92}
\bysame, \emph{The uniformity lemma for hypergraphs}, Graphs and Combinatorics
  \textbf{8} (1992), no.~4, 309--312.

\bibitem{frankl88}
P.~Frankl, V.~R{\"o}dl, and R.~M. Wilson, \emph{The number of submatrices of a
  given type in a {H}adamard matrix and related results}, Journal of
  Combinatorial Theory, Series B \textbf{44} (1988), no.~3, 317--328.

\bibitem{FriezeKannanRL}
A.~Frieze and R.~Kannan, \emph{The regularity lemma and approximation schemes
  for dense problems}, 37th Annual Symposium on Foundations of Computer Science
  (Burlington, VT, 1996), IEEE Comput. Soc. Press, Los Alamitos, CA, 1996,
  pp.~12--20.

\bibitem{frieze99:_quick_approx_matric_applic}
\bysame, \emph{Quick approximation to matrices and applications}, Combinatorica
  \textbf{19} (1999), no.~2, 175--220.

\bibitem{frieze99:_constructive_SzRL}
\bysame, \emph{A simple algorithm for constructing {S}zemer\'edi's regularity
  partition}, Electronic Journal of Combinatorics \textbf{6} (1999), no.~1,
  Research Paper 17, 7 pp.\ (electronic).

\bibitem{goldreich99:_combin}
O.~Goldreich, \emph{Combinatorial property testing (a survey)}, Randomization
  methods in algorithm design (Princeton, NJ, 1997), Amer. Math. Soc.,
  Providence, RI, 1999, pp.~45--59.

\bibitem{goldreich96:_proper}
O.~Goldreich, S.~Goldwasser, and D.~Ron, \emph{Property testing and its
  connection to learning and approximation}, 37th Annual Symposium on
  Foundations of Computer Science (Burlington, VT, 1996), IEEE Comput. Soc.
  Press, Los Alamitos, CA, 1996, pp.~339--348.

\bibitem{goldreich98:_proper}
\bysame, \emph{Property testing and its connection to learning and
  approximation}, Journal of the Association for Computing Machinery
  \textbf{45} (1998), no.~4, 653--750.

\bibitem{goldreich97:bound_degree}
O.~Goldreich and D.~Ron, \emph{Property testing in bounded degree graphs}, 29th
  ACM Symposium on Theory of Computing (El Paso, Texas), 1997, pp.~406--419.

\bibitem{oded99:_sublin_bipar_tester_bound_degree_graph}
\bysame, \emph{A sublinear bipartiteness tester for bounded degree graphs},
  Combinatorica \textbf{19} (1999), no.~3, 335--373.

\bibitem{golub89:_matrix_comput}
G.~H. Golub and C.~F. van Loan, \emph{Matrix computations}, Johns Hopkins
  University Press, London, 1989.

\bibitem{gowers97:_lower}
W.~T. Gowers, \emph{Lower bounds of tower type for {S}zemer\'edi's uniformity
  lemma}, Geometric and Functional Analysis \textbf{7} (1997), no.~2, 322--337.

\bibitem{HKL}
P.~E. Haxell, Y.~Kohayakawa, and T.~{\L}uczak, \emph{The induced size-{R}amsey
  number of cycles}, Combinatorics, Probability, and Computing \textbf{4}
  (1995), no.~3, 217--239.

\bibitem{haxell99:_integ}
P.~E. Haxell and V.~R\"odl, \emph{Integer and fractional packings in dense
  graphs}, submitted, 1999.

\bibitem{Kohayakawa97Szemeredi}
Y.~Kohayakawa, \emph{Szemer\'edi's regularity lemma for sparse graphs},
  Foundations of Computational Mathematics (Berlin, Heidelberg) (F.~Cucker and
  M.~Shub, eds.), Springer-Verlag, January 1997, pp.~216--230.

\bibitem{kohayakawa00:_optimal_SzRL}
Y.~Kohayakawa, V.~R\"odl, and L.~Thoma, \emph{An optimal deterministic
  algorithm for {S}zemer\'edi's regularity lemma}, submitted, 2000.

\bibitem{KomlosSimonovits96}
J.~Koml\'os and M.~Simonovits, \emph{Szemer\'edi's regularity lemma and its
  applications in graph theory}, Combinatorics---{P}aul {E}rd\H{o}s is eighty,
  {\rm vol.~2 (Keszthely, 1993)} (D.~Mikl{\'o}s, V.~T. S{\'o}s, and T.~Sz{\H
  o}nyi, eds.), Bolyai Society Mathematical Studies, vol.~2, J\'anos Bolyai
  Mathematical Society, Budapest, 1996, pp.~295--352.

\bibitem{komlos99}
J.~Koml{\'o}s, \emph{The blow-up lemma}, Combinatorics, Probability and
  Computing \textbf{8} (1999), no.~1-2, 161--176, {R}ecent trends in
  combinatorics ({M}\'atrah\'aza, 1995).

\bibitem{komlos97:_blow}
J.~Koml{\'o}s, G.~N. S{\'a}rk{\"o}zy, and E.~Szemer{\'e}di, \emph{Blow-up
  lemma}, Combinatorica \textbf{17} (1997), no.~1, 109--123.

\bibitem{komlos98}
\bysame, \emph{An algorithmic version of the blow-up lemma}, Random Structures
  and Algorithms \textbf{12} (1998), no.~3, 297--312.

\bibitem{LPS}
A.~Lubotzky, R.~Phillips, and P.~Sarnak, \emph{Ramanujan graphs}, Combinatorica
  \textbf{8} (1988), 261--277.

\bibitem{lubotzky94:_discr}
A.~Lubotzky, \emph{Discrete groups, expanding graphs and invariant measures},
  Birk\-h\"au\-ser Verlag, Basel, 1994, with an appendix by {J}onathan
  {D}.~{R}ogawski.

\bibitem{margulis88:_explic}
G.~A. Margulis, \emph{Explicit group-theoretic constructions of combinatorial
  schemes and their applications in the construction of expanders and
  concentrators}, Problemy Peredachi Informatsii \textbf{24} (1988), no.~1,
  51--60.

\bibitem{PSgen}
H.~J. Pr{\"o}mel and A.~Steger, \emph{Excluding induced subgraphs {III}. {A}
  general asymptotic}, Random Structures and Algorithms \textbf{3} (1992),
  no.~1, 19--31.

\bibitem{roedl98:_algorithmic_blowup}
V.~R{\"o}dl, A.~Ruci{\'n}ski, and M.~Wagner, \emph{An algorithmic embedding of
  graphs via perfect matchings}, Randomization and approximation techniques in
  computer science, Lecture Notes in Computer Science, vol. 1518, 1998,
  pp.~25--34.

\bibitem{rodl99:_perfec_blow_lemma}
V.~R\"odl and A.~Ruci{\'n}ski, \emph{Perfect matchings in $\epsilon$-regular
  graphs and the blow-up lemma}, Combinatorica \textbf{19} (1999), no.~3,
  437--452.

\bibitem{RubinfeldS1996}
R.~Rubinfeld and M.~Sudan, \emph{Robust characterizations of polynomials with
  applications to program testing}, SIAM Journal on Computing \textbf{25}
  (1996), no.~2, 252--271.

\bibitem{sarnak90:_some}
P.~Sarnak, \emph{Some applications of modular forms}, Cambridge University
  Press, Cambridge, 1990.

\bibitem{szemeredi75}
E.~Szemer\'edi, \emph{On sets of integers containing no $k$ elements in
  arithmetic progression}, Acta Arithmetica \textbf{27} (1975), 199--245,
  collection of articles in memory of {J}uri\u\i\ {V}ladimirovi\v c {L}innik.

\bibitem{szemeredi76}
\bysame, \emph{Regular partitions of graphs}, Probl\`emes Combinatoires et
  Th\'eorie des Graphes (Colloq.\ Internat.\ CNRS, Univ.\ Orsay, Orsay, 1976)
  (Paris), Colloques Internationaux CNRS n.~260, 1978, pp.~399--401.

\bibitem{Taraz95Diplom}
A.~R. Taraz, \emph{Szemer\'edis {R}egularit\"atslemma}, April 1995,
  {D}iplomarbeit, {U}niversit{\"a}t {B}onn, 83pp.

\bibitem{thomason87}
A.~G. Thomason, \emph{Pseudorandom graphs}, Random graphs '85 ({P}ozna\'n,
  1985), North-Holland Math. Stud., vol. 144, North-Holland, Amsterdam--New
  York, 1987, pp.~307--331.

\bibitem{thomason87:_random}
\bysame, \emph{Random graphs, strongly regular graphs and pseudorandom graphs},
  Surveys in Combinatorics~1987 (C.~Whitehead, ed.), London Mathematical
  Society Lecture Note Series, vol. 123, Cambridge University Press,
  Cambridge--New York, 1987, pp.~173--195.

\bibitem{tiskin98:_bulk_boolean}
A.~Tiskin, \emph{Bulk-synchronous parallel multiplication of {B}oolean
  matrices}, Automata, languages and programming, Lecture Notes in Computer
  Science, vol. 1443, 1998, pp.~494--506.

\end{thebibliography}

\end{document}
