%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% LaTeX2e file for 
%
% ``SZEMER\'EDI'S REGULARITY LEMMA FOR SPARSE GRAPHS''
%
% by Y. Kohayakawa 
%
% Last update: 15 August 1996
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentstyle{llncs}
\DeclareSymbolFont{AMSb}{U}{msb}{m}{n}
\DeclareSymbolFontAlphabet{\mathbb}{AMSb}
\catcode`@=11
\def\cases#1{\left\{\,\vcenter{\normalbaselines\m@th
    \ialign{$##\hfil$&\quad##\hfil\crcr#1\crcr}}\right.}

\def\openup{\afterassignment\@penup\dimen@=}
\def\@penup{\advance\lineskip\dimen@
  \advance\baselineskip\dimen@
  \advance\lineskiplimit\dimen@}
\def\eqalign#1{\null\,\vcenter{\openup\jot\m@th
  \ialign{\strut\hfil$\displaystyle{##}$&$\displaystyle{{}##}$\hfil
      \crcr#1\crcr}}\,}
\newif\ifdt@p
\def\displ@y{\global\dt@ptrue\openup\jot\m@th
  \everycr{\noalign{\ifdt@p \global\dt@pfalse \ifdim\prevdepth>-1000\p@
      \vskip-\lineskiplimit \vskip\normallineskiplimit \fi
      \else \penalty\interdisplaylinepenalty \fi}}}
\def\@lign{\tabskip\z@skip\everycr{}} % restore inside \displ@y
\def\displaylines#1{\displ@y \tabskip\z@skip
  \halign{\hbox to\displaywidth{$\@lign\hfil\displaystyle##\hfil$}\crcr
    #1\crcr}}
\def\eqalignno#1{\displ@y \tabskip\centering
  \halign to\displaywidth{\hfil$\@lign\displaystyle{##}$\tabskip\z@skip
    &$\@lign\displaystyle{{}##}$\hfil\tabskip\centering
    &\llap{$\@lign##$}\tabskip\z@skip\crcr
    #1\crcr}}
\def\leqalignno#1{\displ@y \tabskip\centering
  \halign to\displaywidth{\hfil$\@lign\displaystyle{##}$\tabskip\z@skip
    &$\@lign\displaystyle{{}##}$\hfil\tabskip\centering
    &\kern-\displaywidth\rlap{$\@lign##$}\tabskip\displaywidth\crcr
    #1\crcr}}
\catcode`@=12
\def\({\left(}
\def\){\right)}
\def\[{\left[}
\def\]{\right]}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newstytheorem{conjecture}{\bf}{\it}[theorem]{Conjecture}
\newstytheorem{remarks}{\it}{\rm}[*]{Remarks}
\newstytheorem{caveat}{\it}{\rm}[*]{Caveat}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\dHG{d_{H,G}}
\def\eG{e_G}
\def\eH{e_H}
\def\dstS{d^*_{s,t}}
\let\epsilon=\varepsilon
\let\rho=\varrho
\def\ind{\mathop{\rm ind}\nolimits}
\def\MAXSNP{\textbf{MAXSNP}}
\def\:{\colon}
\def\cF{{\cal F}}
\def\cB{{\cal B}}
\def\cR{{\cal R}}
\def\dGp{d_{G,p}}
\def\dHp{d_{H,p}}
\def\Bi{\mathop{\hbox{\rm Bi}}\nolimits}
\def\ex{\mathop{\hbox{\rm ex}}\nolimits}
\def\Forb{\mathop{\text{\rm Forb}}}
\let\symmdiff=\bigtriangleup
\let\sdiff=\symmdiff
\newcommand{\dHr}{d_{H,\rho}}
\newcommand{\PJsdiff}{P_{J,\symmdiff}}
\newcommand{\Ave}{\mathop\protect{\rm Ave}}
\newcommand{\SkUW}{S_k^{(U,W)}}
\newcommand{\sumijUW}{\sum\nolimits_{ij\in H}^{(U,W)}}
\def\bfV{{\bf V}}
\def\dFp{d_{F,p}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

\title{Szemer\'edi's Regularity Lemma for Sparse Graphs}

\author{Y.~Kohayakawa\footnote{Partially supported by FAPESP
    (Proc.~96/4505--2) and CNPq (Proc.~300334/93--1 and ProTeM-CC-II Project
    ProComb).}}

\institute{Instituto de Matem\'atica e Estat\'\i stica, Universidade de S\~ao
  Paulo\\ Rua do Mat\~ao~1010, 05508--900~S\~ao Paulo, SP\\Brazil}

\maketitle

\begin{abstract}
  A remarkable lemma of Szemer\'edi asserts that, very roughly speaking,
  \textit{any} dense graph can be decomposed into a bounded number of
  pseudorandom bipartite graphs.  This far-reaching result has proved to play
  a central r\^ole in many areas of combinatorics, both `pure' and
  `algorithmic.'  The quest for an equally powerful variant of this lemma for
  sparse graphs has not yet been successful, but some progress has been
  achieved recently.  The aim of this note is to report on the successes so
  far.
\end{abstract}

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

Szemer\'edi's celebrated proof~\cite{szemeredi75} of the conjecture of Erd\H
os and Tur\'an~\cite{ErdosTuran36} on arithmetic progressions in dense subsets
of integers is certainly a masterpiece of modern combinatorics.  An auxiliary
lemma in that work, which has become known in its full
generality~\cite{szemeredi76} as \textit{Szemer\'edi's regularity lemma}, has
turned out to be a powerful and widely applicable combinatorial tool.  For an
authoritative survey on this subject, the reader is referred to the recent
paper of Koml\'os and Simonovits~\cite{KomlosSimonovits96}.  For the
algorithmic aspects of this lemma, the reader is referred to the papers of
Alon, Duke, Lefmann, R\"odl, and Yuster~\cite{alon94} and Duke, Lefmann, and
R\"odl~\cite{DukeLefmannRodlcount}.

Very roughly speaking, the lemma of Szemer\'edi says that \textit{any} graph
can be decomposed into a bounded number of pseudorandom bipartite graphs.
Since pseudorandom graphs have a predictable structure, the regularity lemma
is a powerful tool for introducing `order' where none is visible at first.
The notion of pseudorandomness that appears in the lemma has to do with
distribution of edges.  In fact, the bipartite graphs that are used to
decompose a given graph are guaranteed to have its edges uniformly distributed
with an error term that is quadratic in the number of vertices of the graph,
but with an arbitrarily small multiplicative constant.  Therefore, we have a
handle on the edge distribution of the original graph as long as it has a
quadratic number of edges.  If the original graph has a subquadratic number of
edges, however, Szemer\'edi's lemma will tell us nothing.  In this note, we
focus our attention on certain closely related variants of the regularity
lemma that can handle this `sparse' case with some success.  An unpublished
manuscript of the present author~\cite{kohayakawa93} dealt with one such
variant.  As mentioned there, these variants were also independently
discovered by Professor~V.~R\"odl.

These sparse versions of the regularity lemma have already been used for
studying extremal properties of graphs~\cite{HKrotu,HKL}, of random
graphs~\cite{HKLeven,HKLodd,KKreuterCycles,KLRkfour}, and of random sets of
integers~\cite{KLRap3}, and also for developing an optimal algorithm for
checking pseudorandomness of graphs~\cite{KRo-fast-sparse}.  In the sequel, we
shall discuss these applications and we shall also state a few related
problems.

Before we close the introduction, let us mention that, since the paper of
Koml\'os and Simonovits~\cite{KomlosSimonovits96} went to press, another nice
application of the regularity lemma, together with a new variant, has
appeared.  Frieze and Kannan~\cite{FriezeKannanRL} have approached some
{\MAXSNP}-hard problems by means of the regularity lemma.  Their method gives
polynomial time approximation schemes for many graph partitioning problems if
the instances are restricted to dense ones.  Their paper thus provides yet
another motivation for investigating sparse versions of the fascinating lemma
of Szemer\'edi.

This note is organised as follows.  The statement of a version of the
regularity lemma for sparse graphs, Theorem~\ref{thm:SSz}, is given in
Section~\ref{sec:prelims} below.  A variant of Theorem~\ref{thm:SSz} is also
discussed in that section.  We then present in Section~\ref{sec:fast} an
application of Theorem~\ref{thm:SSz} to the study of pseudorandom graphs,
highlighting an algorithmic consequence.  In Section~\ref{sec:graphs} we
present applications of Theorem~\ref{thm:SSz} to graph theory and to
combinatorial number theory.  A proof of Theorem~\ref{thm:SSz} is outlined in
Section~\ref{sec:proof}.  We close this note with some remarks and open
problems.

\begin{caveat}
  The regularity lemma is a powerful tool, but, naturally, several of its
  applications involve many further additional ideas and techniques.  Although
  crucial in the applications we shall discuss below, the sparse version of
  this lemma is still far weaker than one would wish, and one has to fight
  quite hard to prove the results in question.  Therefore, in this note, we
  shall not be able to state precisely how this lemma comes in in the proofs
  of the theorems under discussion.  However, we shall try to hint what the
  r\^ole of the regularity lemma is in each case.
\end{caveat}

\section{Sparse Variants of the Regularity Lemma}
\label{sec:prelims}

\subsection{Preliminary Definitions}
\label{sec:prelim-prelim-defns}

Let a graph~$G=G^n$ of order~$|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)|$.  Now, let a
partition~$P_0=(V_i)_1^\ell$ ($\ell\geq1$) of~$V$ 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\leq\eta\leq1$. We say that~$G$ is \textit{$(P_0,\eta)$-uniform}
if, for some~$0\leq 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{Unif}
  \big|\eG(U,W)-p|U||W|\big|\leq\eta p|U||W|.
\end{equation}
We remark that 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}$.  Note that for~$\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$.  Here and in the
sequel, we use standard definitions and notation concerning random graphs.
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, \textit{e.g.}, Bollob\'as~\cite{BBf}.

\subsection{A Regularity Lemma for Sparse Graphs}
\label{sec:first-version}
We first introduce a few further definitions that will allow us to state a
version of Szemer\'edi's lemma for sparse graphs.  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.
$$ 
We say that a partition~$Q=(C_i)_0^k$ of~$V=V(G)$ is
\textit{$(\epsilon,k)$-equitable} if~$|C_0|\leq\epsilon n$,
and~$|C_1|=\ldots=|C_k|$. Also, we say that~$C_0$ is the \textit{exceptional}
class of~$Q$. 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$.  If~$P$ and~$Q$ are two equitable
partitions of~$V$, 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$
  and $K_0=K_0(\epsilon,k_0,\ell)\geq k_0$ satisfying the following. For any
  $(P_0,\eta)$-uniform graph $G=G^n$, 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$. \qed
\end{theorem}

\begin{remark}
  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~$|H|=n$ be fixed.  Suppose~$0<\eta\leq1$
and~$0<p\leq1$.  We say that~$H$ is \textit{$\eta$-upper-uniform} with
\textit{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(1+\eta)p|U||W|$.  In the
sequel, for any two disjoint non-empty sets~$U$, $W\subset V$,
let~$\dHp(U,W)=e_H(U,W)/2p|U||W|$.

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$-upper-uniform graphs.

\begin{theorem}\label{thm:SSzp}
  For any given $\epsilon>0$ and $k_0\geq1$, there are
  constants $\eta=\eta(\epsilon,k_0)>0$ and $K_0=K_0(\epsilon,k_0)\geq k_0$
  such that any $\eta$-upper-uniform graph $H$ with 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$.\qed
\end{theorem}

\begin{remarks}
  (\textit{i})\enspace A further variant of Theorem~\ref{thm:SSz} concerns the
  existence $\epsilon$-regular partitions with respect to a
  \textit{collection} of graphs on the same vertex set.  Such a variant is
  used~\cite{HKL}.

  (\textit{ii})\enspace Variants of Theorems~\ref{thm:SSz} and~\ref{thm:SSzp}
  for sparse hypergraphs may be proved easily.  However, we know of no
  applications of such results.  For hypergraph versions of the regularity
  lemma, see~\cite{chung91-regularity,frankl92}.
\end{remarks}

\section{Checking Pseudorandomness of Graphs}
\label{sec:fast}

The investigation of explicitly constructible graphs that are `random-like'
has proved to be very fruitful in providing examples for many extremal
problems in graph theory.  These graphs have also played a crucial r\^ole in
algorithmic problems: the use of expanders for amplifying the power of random
sources is but one example.

The study of pseudorandom graph properties, \textit{i.e.}, properties that
random graphs have and somehow capture their `random nature,' can be traced
back to Graham and Spencer~\cite{GrahamSpencer71}, R\"odl~\cite{rodl86}, and
Frankl, R\"odl, and Wilson~\cite{frankl88}.
Thomason~\cite{thomason87,thomason87:_random} and Chung, Graham, and
Wilson~\cite{chung89} present further developments that have given this
subject the status of a solid theory.  (We do not go into the details, but we
mention that similar theories for hypergraphs and subsets of~${\mathbb Z}_n$
are now available, see~Chung and Graham~\cite{chung91-set,chung92-Zn}.)

In this section, we shall be concerned with a new pseudorandom graph property
introduced by R\"odl.  This property characterises \textit{quasi-random}
graphs in the sense of Chung, Graham, and Wilson~\cite{chung89}. As a
consequence of this characterisation, we shall have an optimal algorithm for
checking quasi-randomness of graphs.  For the proofs of the results in this
section, the reader is referred to~\cite{KRo-fast-sparse}.

\subsection{Preliminary Definitions}
\label{sec:fast-defns}
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}

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|}, %\{r|U||W|\}^{1/2}, 
\end{equation}
where~$r=\rho n$.  In the sequel, we may take the graph~$J$ to be a
Lubotzky--Phillips--Sarnak Ramanujan graph~$X_{p,q}$ for some values of~$p$
and~$q$, see~\cite{LPS}.  If~$J=X_{p,q}$, we have~$r=p+1$ and the graph~$J$ is
$r$-regular.  Moreover, in this case, inequality~(\ref{eq:basic-unif}) holds
with~$A=2$, and in fact~$r$ on the right hand side of~(\ref{eq:basic-unif})
may be replaced by~$r-1$.

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$.
Let~$0<\epsilon\leq1$ be a real.  We say that~$G$ satisfies
property~$\PJsdiff(\epsilon)$ if we have
\begin{equation}
  \label{eq:PJsdiff}
  \sum_{ij\in E(J)}
    \left||\Gamma_G(i)\symmdiff\Gamma_G(j)|-\frac12n\right|
     \leq\frac12\epsilon ne(J), 
\end{equation}
where, as usual, we write~$\Gamma_G(x)$ for the $G$-neighbourhood of a
vertex~$x$ of~$G$, and we write~$A\symmdiff B$ for the symmetric
difference~$(A\setminus B)\cup(B\setminus A)$.  Moreover,
in~(\ref{eq:PJsdiff}) and in the sequel, $e(J)$~denotes the number of edges
in~$J$.  As we shall see in Section~\ref{sec:fast-result},
inequality~(\ref{eq:PJsdiff}), which may be checked in time~$O(n^2)$ if we
take~$J$ to be a graph with~$e(J)=O(n)$, turns out to be a quasi-random
property in the sense of~\cite{chung89}.

For technical reasons, we need to introduce a variant of
property~$\PJsdiff(\epsilon)$.  Suppose~$0<\gamma\leq1$ and~$0<\epsilon\leq1$
are two reals and~$G=G^n$ is an $n$-vertex graph.  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}
fails for at most~$\gamma e(J)$ edges~$ij\in E(J)$ of~$J$.  As a quick
argument shows, properties~$\PJsdiff(\epsilon)$ and~$\PJsdiff(\gamma,\epsilon)$ are
equivalent under suitable assumptions on the parameters, see
Lemma~\ref{lem:PJ-PJdash}.

\subsection{The Equivalence Results}
\label{sec:fast-result}

The following three results express the equivalence between quasi-randomness,
in the technical sense of Chung, Graham, and Wilson~\cite{chung89}, and
property~$\PJsdiff$.  Loosely speaking, quasi-randomness in the sense
of~\cite{chung89} is equivalent to the property of being
$(1/2,o(1),o(1))$-quasi-random, which, as the results below show, is
equivalent to property~$\PJsdiff(o(1))$.

\begin{theorem}
  \label{thm:Main-1}
  Let an $r$-regular $(\rho,A)$-uniform graph $J=J^n$ be fixed,
  where $0<\rho=r/n\leq1$ and $A$ is an absolute constant.  Let
  constants $0<\epsilon\leq1$ and $0<\delta\leq1$ be given.  Then
  if $0<\epsilon'\leq\epsilon^2\delta^3/8$
  and $r\geq2^{10}A^2\epsilon^{-2}\delta^{-2}$, we have that any graph $G=G^n$
  on the same vertex set as $J$ satisfying property $\PJsdiff(\epsilon')$ is
  $(1/2,\epsilon,\delta)$-quasi-uniform. \qed
\end{theorem}

\begin{theorem}
  \label{thm:Main-2}
  Let an $r$-regular $(\rho,A)$-uniform graph $J=J^n$ be fixed,
  where $0<\rho=r/n\leq1$ and $A$ is an absolute constant.  Let
  constants $0<\gamma\leq1$ and $0<\epsilon\leq1$ be given.  Then there exist
  constants $0<\epsilon_0=\epsilon_0(\gamma,\epsilon)\leq1$,
  $0<\delta_0=\delta_0(\gamma,\epsilon)\leq1$,
  and $r_0=r_0(\gamma,\epsilon)\geq1$, which depend only on $\gamma$
  and $\epsilon$, such that any $(1/2,\epsilon',\delta')$-quasi-uniform
  graph $G$ on the same vertex set as $J$ satisfies
  property $\PJsdiff'(\gamma,\epsilon)$ as long
  as $\epsilon'\leq\epsilon_0(\gamma,\epsilon)$,
  $\delta'\leq\delta_0(\gamma,\epsilon)$, and $r\geq r_0(\gamma,\epsilon)$.
  \qed
\end{theorem}

\begin{lemma}
  \label{lem:PJ-PJdash}
  Let a $(\rho,A)$-uniform graph $J=J^n$ be given, where $0<\rho\leq1$ and $A$
  is an absolute constant.  The following assertions hold.
  \begin{enumerate}
  \item[{\rm(\textit{i})}] Let $G=G^n$ be a graph on $V(J)$ satisfying
    property $\PJsdiff'(\gamma,\epsilon)$, where $0<\gamma\leq1$
    and $0<\epsilon\leq1$ satisfy $\gamma+\epsilon\leq1$.  Then $G$ has
    property $\PJsdiff(\epsilon+\gamma)$.
  \item[{\rm(\textit{ii})}] Let $G=G^n$ be a graph on $V(J)$ satisfying
    property $\PJsdiff(\epsilon)$ and suppose $\epsilon\leq\epsilon'\leq1$.
    Then $G$ satisfies property $\PJsdiff'(\epsilon/\epsilon',\epsilon')$.
    \qed
  \end{enumerate}
\end{lemma}

An immediate corollary to the above results is as follows.

\begin{corollary}\label{fast-cor}
  Given an $n$-vertex graph $G$, we can decide in time $O(n^2)$ whether or
  not $G$ is a quasi-random graph. \qed
\end{corollary}

Previously, the fastest known method for checking quasi-randomness was based
on the quasi-random property~$\PJsdiff$ with~$J$ the complete graph~$K^n$
on~$n$ vertices.  This gave an algorithm of time complexity~$O(M(n))$,
where~$M(n)=O(n^{2.376})$ is the time needed for multiplying two $n$~by~$n$
matrices with $0$--$1$~entries over the integers.

\subsubsection{The R\^ole of the Regularity Lemma.}
Theorem~\ref{thm:SSz} is used in the proof of Theorem~\ref{thm:Main-2}.
Roughly speaking, one takes a graph~$G$ as in the statement of
Theorem~\ref{thm:Main-2}, and assumes that it does not
satisfy~$\PJsdiff'(\gamma,\epsilon)$.  One then takes the spanning
subgraph~$H$ of~$J$ whose edges are the `violating edges'~$ij\in E(J)$, where
we call an edge~$ij$ \textit{violating} if~(\ref{eq:PJsdiff-local}) fails
for~$ij$.  Note that a violating edge may be of two types, corresponding to
the two inequalities expressed in~(\ref{eq:PJsdiff-local}).  Thus, we may
naturally split the edges of~$H$ into two groups; say~$H=H_-\cup H_+$.  Assume
that, say, $e(H_+)\geq(1/2)e(H)\geq(\gamma/2)e(J)$.  We may then apply
Theorem~\ref{thm:SSz} to the pair~$H_+\subset J$.  Once an $H_+$-dense regular
pair~$(V_i,V_j)$ is shown to exist, one may prove that there is a pair~$(U,W)$
of suitably large sets that violate~(\ref{eq:basic-q.r.}).  Details are given
in~\cite{KRo-fast-sparse}.

\section{Further Applications }
\label{sec:graphs}

\subsection{Applications in Graph Theory}
\label{sec:graphs-sub}

A classical area of extremal graph theory investigates numerical and
structural problems concerning \textit{$H$-free graphs}, namely graphs that do
not contain a copy of a given fixed graph~$H$ as a subgraph. Let~$\ex(n,H)$ be
the maximal number of edges that an $H$-free graph on $n$~vertices may have. A
basic question is then to determine or estimate~$\ex(n,H)$ for any given~$H$
and large~$n$.  A solution to this problem is given by the celebrated Erd\H
os--Stone--Simonovits theorem, which states that, as~$n\to\infty$, we have
\begin{equation}
  \label{eq:ESS}
  \ex(n,H)=\(1-{1\over\chi(H)-1}+o(1)\){n\choose2}, 
\end{equation}
where as usual~$\chi(H)$ is the chromatic number of~$H$.  Furthermore, as
proved independently by Erd\H os and Simonovits, every $H$-free graph~$G=G^n$
that has as many edges as in~(\ref{eq:ESS}) is in fact `very close' (in a
certain precise sense) to the densest $n$-vertex $(\chi(H)-1)$-partite graph.
For these and related results, see, for instance, Bollob\'as~\cite{BBegt}.

Here we are interested in a variant of the function~$\ex(n,H)$.  Let~$G$
and~$H$ be graphs, and write~$\ex(G,H)$ for the maximal number of edges that
an $H$-free subgraph of~$G$ may have.  Formally,
$\ex(G,H)=\max\{e(J)\:H\not\subset J\subset G\}$, where~$e(J)$ stands for the
size~$|E(J)|$ of~$J$ as before.  Clearly~$\ex(n,H)=\ex(K^n,H)$. 

One problem is, then, to study~$\ex(G,H)$ when~$G$ is a `typical' graph, by
which we mean a \textit{random graph}.  In other words, we wish to investigate
the random variable~$\ex(G_{n,p},H)$. % and~$\ex(G_{n,M},H)$.

Let~$H$ be a graph of order~$|H|=|V(H)|\geq3$ and size~$e(H)>0$.  Let us
write~$d_2(H)$ for the \textit{$2$-density\/} of~$H$, that is,
$$
d_2(H)=\max\left\{{e(J)-1\over|J|-2}\:J\subset H\hbox{,
  }|J|\geq3\right\}. 
$$
Given a real~$0\leq\epsilon\leq1$ and an integer~$r\geq2$, let us say that a
graph~$J$ is \textit{$\epsilon$-quasi $r$-partite} if~$J$ may be made
$r$-partite by the deletion of at most~$\epsilon e(J)$ of its edges.  A
general conjecture concerning~$\ex(G_{n,p},H)$ is as follows
(cf.~\cite{KLRkfour}).  As is usual in the theory of random graphs, we say
that a property~$P$ holds \textit{almost surely} or that \textit{almost every}
random graph~$G_{n,p}$ satisfies~$P$ if~$P$ holds with probability tending
to~$1$ as~$n\to\infty$.

\begin{conjecture}\label{conj:MainConj}
  Let~$H$ be a non-empty graph of order at least~$3$, and let~$0<p=p(n)\leq1$
  be such that~$pn^{1/d_2(H)}\to\infty$ as~$n\to\infty$. Then the following
  assertions hold.  
  \begin{enumerate}
  \item[{\rm(\textit{i})}] Almost every~$G_{n,p}$ satisfies
    \begin{equation}
      \label{eq:Conj}
      \ex(G_{n,p},H)=\(1-{1\over\chi(H)-1}+o(1)\)e(G_{n,p}).
    \end{equation}
  \item[{\rm(\textit{ii})}] Suppose~$\chi(H)\geq3$. Then for any~$\epsilon>0$
    there is a constant~$\delta=\delta(\epsilon)>0$ such that almost
    every~$G_{n,p}$ has the property that any $H$-free subgraph~$J\subset
    G_{n,p}$ of~$G_{n,p}$ with~$e(J)\geq(1-\delta)\ex(G_{n,p},H)$ is
    $\epsilon$-quasi $(\chi(H)-1)$-partite. \qed
  \end{enumerate}
\end{conjecture}

Recall that any graph~$G$ contains an $r$-partite subgraph~$J\subset G$
with~$e(J)\geq(1-1/r)e(G)$. Thus the content of
Conjecture~\ref{conj:MainConj}(\textit{i}) is that~$\ex(G_{n,p},H)$ is at most
as large as the right-hand side of~(\ref{eq:Conj}).  There are a few results
in support of Conjecture~\ref{conj:MainConj}(\textit{i}).

Any result concerning the tree-universality of expanding graphs, or else a
simple application of Theorem~\ref{thm:SSzp}, gives
Conjecture~\ref{conj:MainConj}(\textit{i}) for forests.  The cases in
which~$H=K^3$ and~$H=C^4$ are essentially proved in Frankl and
R\"odl~\cite{frankl86} and F\"uredi~\cite{Fu}, respectively, in connection
with problems concerning the existence of some graphs with certain extremal
properties.  The case in which~$H$ is a general cycle was settled by Haxell,
Kohayakawa, and \L uczak~\cite{HKLeven,HKLodd} (see also Kohayakawa, Kreuter,
and Steger~\cite{KKS}), and the case in which~$H=K^4$ was settled by
Kohayakawa, \L uczak, and R\"odl~\cite{KLRkfour}.
Conjecture~\ref{conj:MainConj}(\textit{ii}) in the case in which~$0<p\leq1$ is
a constant follows easily from Szemer\'edi's original regularity lemma.
Theorem~\ref{thm:SSzp} and a lemma from Kohayakawa, \L uczak, and
R\"odl~\cite{KLRap3} concerning induced subgraphs of bipartite graphs may be
used to verify Conjecture~\ref{conj:MainConj} for~$H=K^3$ in full, and, more
generally, Conjecture~\ref{conj:MainConj} may be proved for the case in
which~$H$ is a cycle by making use of a lemma in Kohayakawa and
Kreuter~\cite{KKreuterCycles}.

We must at this point mention that beautiful and very general results
concerning \textit{Ramsey} properties of random graphs in the spirit of
Conjecture~\ref{conj:MainConj} were proved by R\"odl and
Ruci\'nski~\cite{RodlRucinski93,RodlRucinski95}.  These authors used the
original lemma of Szemer\'edi.  A related result, of a much more restricted
scope but apparently not accessible through the techniques
in~\cite{RodlRucinski93,RodlRucinski95}, is proved in Kohayakawa and
Kreuter~\cite{KKreuterCycles}.  Theorem~\ref{thm:SSzp} is crucial
in~\cite{KKreuterCycles}.


\subsubsection{The R\^ole of the Regularity Lemma.}
A moment's thought reveals that Theorem~\ref{thm:SSz} is immediately
applicable to the situation given in Conjecture~\ref{conj:MainConj}.  Indeed,
we have a subgraph~$J$ of a random and hence $\eta$-uniform graph~$G_{n,p}$ at
hand and therefore we may invoke Theorem~\ref{thm:SSz} to obtain an
$(\epsilon,J,G_{n,p})$-regular partition~$P$ of~$V=V(G_{n,p})$, for any
constants~$\epsilon>0$ and~$k_0$.  If we further know that
$$
e(J)\geq\(1-{1\over\chi(H)-1}+\delta\)e(G_{n,p}), 
$$
where~$\delta>0$ is some constant, it is a simple matter to find a set
of~$h=|H|$ classes~$V_i$ in the partition~$P$ that `form a copy of~$H$' (here
we need to have~$\epsilon$ suitably small and~$k_0$ suitably large with
respect to~$\delta$).  If we are dealing with~$0<p\leq1$ that is a constant,
independent of~$n$, then we are finished, since these~$h$ classes may be shown
to span a copy of~$H$.  If~$p=p(n)\to0$ as~$n\to\infty$, however, we are
stuck, since this last statement does not necessarily hold.
In~\cite{HKLeven,HKLodd,KKreuterCycles,KLRkfour}, we are forced to take
different approaches, all of them based on more involved applications of our
sparse variants of the regularity lemma.  We shall not go into the details.
We shall, however, discuss a conjecture (cf.~\cite{KLRkfour}) from which, if
true, one may deduce Conjecture~\ref{conj:MainConj} through the standard
approach described above.

Suppose~$H$ has vertices~$v_1,\dots,v_h$ ($h\geq3$) and let~$0<p=p(m)\leq1$ be
given.  Let also~$\bfV=(V_i)_{i=1}^h$ be a family of~$h$ pairwise disjoint
sets, each of cardinality~$m$. Suppose reals~$0<\epsilon\leq1$
and~$0<\gamma\leq1$ and an integer~$T$ are given. We say that an $h$-partite
graph~$F$ with $h$-partition~$V(F)=V_1\cup\cdots\cup V_h$ and
size~$e(F)=|F|=T$ is an \textit{$(\epsilon,\gamma,H;\bfV,T)$-graph} if the
pair~$(V_i,V_j)$ is $(\epsilon,F,p)$-regular and has
$p$-density~$\gamma\leq\dFp(V_i,V_j)\leq1$ whenever~$v_iv_j\in E(H)$.

\begin{conjecture}\label{conj:TechConj}
  Let constants~$0<\alpha\leq1$ and~$0<\gamma\leq1$ be given. Then there exist
  constants~$\epsilon=\epsilon(\alpha,\gamma)>0$ and~$C=C(\alpha,\gamma)$ such
  that, if~$p=p(m)\geq Cm^{-1/d_2(H)}$, the number of $H$-free
  $(\epsilon,\gamma,H;\bfV,T)$-graphs is at most
  $$
  \alpha^T{{h\choose2}m^2\choose T}
  $$ 
  for all~$T$ and all sufficiently large~$m$. \qed
\end{conjecture}

If~$H$ above is a forest, Conjecture~\ref{conj:TechConj} holds trivially,
since, in this case, all $(\epsilon,\gamma,H;\bfV,T)$-graphs contain a copy
of~$H$.  A lemma in Kohayakawa, \L uczak, and R\"odl~\cite{KLRap3} may be used
to show that Conjecture~\ref{conj:TechConj} holds for the case in
which~$H=K^3$.  The general case of cycles is established in Kohayakawa and
Kreuter~\cite{KKreuterCycles}.

\begin{remark}
  Other graph theoretical applications of the regularity lemma for sparse
  graphs are given in Haxell and Kohayakawa~\cite{HKrotu} and Haxell,
  Kohayakawa, and \L uczak~\cite{HKL}.  These applications concern Ramsey and
  anti-Ramsey properties of random and pseudorandom graphs.
\end{remark}

\subsection{An Application in Combinatorial Number Theory}
\label{sec:number}

We now turn to a problem concerning arithmetic progressions of integers.  Here
we are interested in the existence of a `small' and `sparse' set~$R\subset
[n]=\{1,\ldots,n\}$ with the property that every subset~$A\subset R$ that
contains a fixed positive fraction of the elements of~$R$ contains also a
$3$-term arithmetic progression.  The measure of sparseness here should
reflect the fact that~$R$ is locally poor in $3$-term arithmetic progressions.
Clearly, a natural candidate for such a set~$R$ is an $M$-element set~$R_M$
uniformly selected from all the $M$-element subsets of~$[n]$, where~$1\leq
M=M(n)\leq n$ is to be chosen suitably. The main result of Kohayakawa, \L
uczak, and R\"odl~\cite{KLRap3} confirms this appealing and intuitive idea.

For integers~$1\leq M\leq n$, let~$\cR(n,M)$ be the probability space of all
the $M$-element subsets of~$[n]$ equipped with the uniform measure.  In the
sequel, given~$0<\alpha\leq1$ and a set~$R\subset[n]$, write~$R\to_\alpha3$ if
any~$A\subset R$ with~$|A|\geq\alpha|R|$ contains a $3$-term arithmetic
progression.  The main result of~\cite{KLRap3} may then be stated as follows.

\begin{theorem}\label{thm:MainThmRM}
  For every constant $0<\alpha\leq1$, there exists a constant $C=C(\alpha)$
  such that if $C\sqrt n\leq M=M(n)\leq n$ then the probability
  that $R_M\in\cR(n,M)$ satisfies $R_M\to_\alpha3$ tends to $1$
  as $n\to\infty$. \qed
\end{theorem}

Note that Theorem~\ref{thm:MainThmRM} is, in a way, close to being best
possible: if~$M=M(n)=\lfloor\epsilon\sqrt n\rfloor$ for some
fixed~$\epsilon>0$ then the number of $3$-term arithmetic progressions
in~$R_M\in\cR(n,M)$ is, with large probability, smaller than
$2\epsilon^2|R_M|$, and hence all of them may be destroyed by deleting at
most~$2\epsilon^2|R_M|$ elements from~$R_M$; in other words, with large
probability the relation~$R_M\to_\alpha3$ does \textit{not} hold
for~$\alpha=1-2\epsilon^2$.

Theorem~\ref{thm:MainThmRM} immediately implies the existence of `sparse'
sets~$S=S_\alpha$ such that~$S\to_\alpha3$ for any fixed~$0<\alpha\leq1$. The
following result makes this assertion precise.

\begin{corollary}\label{cor:SparseCor}
  Suppose that~$s=s(n)=o(n^{1/8})$ and $g=g(n)=o(\log n)$ as~$n\to\infty$.
  Then, for every fixed~$\alpha>0$, there exist constants~$C$ and~$N$ such
  that for every~$n\ge N$ there exists~$S\subset[n]$ satisfying~$S\to_\alpha3$
  for which the following three conditions hold.
  \begin{enumerate}
  \item[{\rm(\textit{i})}] For every~$k\geq0$ and~$\ell\ge1$ the
    set~$\{k,k+\ell,\dots,k+s\ell\}$ contains at most three elements of~$S$.
  \item[{\rm(\textit{ii})}] Every set~$\{k,k+\ell,\dots,k+m\ell\}$ with~$k\ge
    0$, $\ell\ge 1$, and $m\ge\sqrt n\log n$ contains at most~$Cm/\sqrt n$
    elements of~$S$.
  \item[{\rm(\textit{iii})}] If~$\cF=\cF(S)$ is the $3$-uniform hypergraph on
    the vertex set~$S$ whose hyperedges are the $3$-term arithmetic
    progressions contained in~$S$, then~$\cF$ has no cycle of length smaller
    than~$g$. \qed
  \end{enumerate}
\end{corollary}

In words, conditions~(\textit{i}) and~(\textit{ii}) above say that the set~$S$
intersects any arithmetic progression in a small number of elements.  In
particular, $S$ contains no $4$-term arithmetic progressions.
Condition~(\textit{iii}) is more combinatorial in nature, and says that the
$3$-term arithmetic progressions contained in~$S$ form, locally, a tree-like
structure, which makes the property~$S\to_\alpha3$ somewhat surprising.

Let us remark that the following extension of Szemer\'edi's theorem related to
Corollary~\ref{cor:SparseCor} was proved by R\"odl~\cite{RodlAP90}, thereby
settling a problem raised by Spencer~\cite{Spencer75Restricted}.  Let~$k$,
$g\geq3$ be fixed integers and~$0<\alpha\leq1$ a fixed real.  Theorem~4.3
in~\cite{RodlAP90} asserts that then, for any large enough~$n$, there exists a
$k$-uniform hypergraph~$\cF$ on~$[n]$, all of whose hyperedges are $k$-term
arithmetic progressions, such that~$\cF$ contains no cycle of length smaller
than~$g$ but each subset~$A\subset[n]$ with~$|A|\geq\alpha n$ contains a
hyperedge of~$\cF$.  For other problems and results in this direction, see
Graham and Ne\v set\v ril~\cite{GrahamNesetril86}, Ne\v set\v ril and
R\"odl~\cite{NesetrilRodl87Partite}, and Pr\"omel and
Voigt~\cite{ProemelVoigt88}.  Note that Corollary~\ref{cor:SparseCor}
strengthens the above result of~\cite{RodlAP90} in the case in which~$k=3$.

\subsubsection{The R\^ole of the Regularity Lemma.}  A weak version of Roth's
theorem~\cite{Roth53}, namely, a version stating that any sequence of integers
with \textit{positive} upper density contains a $3$-term arithmetic
progression, may be proved by means of a more-or-less direct application of
the regularity lemma, see, \textit{e.g.}, Erd\H os, Frankl, and
R\"odl~\cite{ErdosFranklRodl86} and Graham and R\"odl~\cite{GRo}.  Since
Theorem~\ref{thm:MainThmRM} above deals with sparse sets of integers, a
similar approach makes results such as Theorem~\ref{thm:SSzp} come into play.
The difficulties that arise are, however, quite substantial.  We close by
mentioning that an application of a variant of Theorem~\ref{thm:SSzp} and the
proof of Conjecture~\ref{conj:TechConj} for~$H=K^3$ are at the heart of the
proof of Theorem~\ref{thm:MainThmRM}.

\section{Proof of Theorem~\ref{thm:SSz}}
\label{sec:proof}

We now proceed to outline the proof Theorem~\ref{thm:SSz}, but, before we
proceed, we stress that the argument below follows the one of
Szemer\'edi~\cite{szemeredi76} very closely.  In particular, as
in~\cite{szemeredi76}, the following `defect' form of the Cauchy--Schwarz
inequality will be important.

\begin{lemma}\label{lem:LemmaDefCS}
  Let reals $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
$$
\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.\eqno{\squareforqed}
$$
\end{lemma}

We now fix~$G=G^n$ and put~$V=V(G)$. Also, we 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\leq\eta\leq1$. Moreover, we let~$p=p(G)$ be as in~(\ref{Unif}).  The
following `continuity' results for~$\dHG$ and~$\dHG^2$ may be proved in a
straightforward manner.  

\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[{\rm(\textit{i})}] $|\dHG(U^*,W^*)-\dHG(U,W)|\leq5\delta$, 
\item[{\rm(\textit{ii})}] $|\dHG(U^*,W^*)^2-\dHG(U,W)^2|\leq9\delta$. \qed 
\end{enumerate}
\end{lemma}

In the sequel, 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 \textit{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)_0^{k'}$.  The following lemma is easy to
check.

\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}$. \qed
\end{lemma}

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}
As in~\cite{szemeredi76}, we define the \textit{index}~$\ind(R)$ of an
equitable partition~$R=(V_i)_0^r$ of~$V=V(G)$ to be
$$
\ind(R)={2\over r^2}\sum_{1\leq i<j\leq\ell}\dHG(V_i,V_j)^2.
$$ 
Note that trivially~$0\leq\ind(R)<1$. The next two lemmas show that,
for~$Q=Q(P)$ defined as above, we have~$\ind(Q)\geq\ind(P)+\epsilon^5/100$.
The proof of the first lemma is based on the Cauchy--Schwarz inequality.

\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}. \eqno{\squareforqed}
$$
\end{lemma}

The inequality in Lemma~\ref{lem:LemmaD} may be improved if~$(C_s,C_t)$ is an
$(\epsilon,H,G)$-irregular pair.  The following lemma, which is proved by
invoking the defect form of the Cauchy--Schwarz inequality,
Lemma~\ref{lem:LemmaDefCS}, makes this precise.

\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}.
                  \eqno{\squareforqed}
$$
\end{lemma}

The following result, which is the main lemma in the proof of
Theorem~\ref{thm:SSz}, follows from Lemmas~\ref{lem:LemmaD}
and~\ref{lem:LemmaE}.

\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(\textit{i})}~$Q$ refines~$P$, 
  {\rm(\textit{ii})}~$k'=k4^k$, 
  {\rm(\textit{iii})}~$|C_0'|\leq|C_0|+n4^{-k}$, and 
  {\rm(\textit{iv})}~$\ind(Q)\geq\ind(P)+\epsilon^5/100$. \qed
\end{lemma}

\begin{proof}[of Theorem~\ref{thm:SSz}] (Outline)\enspace
  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$.  It is now straightforward to check that~$\eta$
  and~$K_0$ as defined above will do.  As in~\cite{szemeredi76}, the proof is
  simply based on the fact that the index of any partition is bounded,
  whereas, as stated in Lemma~\ref{lem:LemmaF}(\textit{iv}), the index
  increases by a fixed amount every time we suitably refine an irregular
  partition.  We omit the details. \qed
\end{proof}


\section{Final Remarks and Open Problems}
\label{sec:final}

It would be of interest to elucidate the algorithmic aspects of
Theorem~\ref{thm:SSz}.  For instance, can one find the partition guaranteed to
exist in that result in time, say, $O(n^2)$, if we are concerned with
subgraphs~$H$ of $r$-regular $\eta$-uniform graphs~$G=G^n$, where~$r$ is a
constant independent of~$n$?  If this turns out to be the case, many
algorithms developed in~\cite{alon94,DukeLefmannRodlcount} may be improved to
optimal algorithms.

We hope that the above applications of the regularity lemma for sparse graphs
reveal the potential of such variants of Szemer\'edi's lemma.  The
applications also illustrate that the `right' variant has not yet been found,
since the successes are somewhat modest when compared with what the original
lemma can achieve in the dense case.  The problem of finding the `right'
variant of Szemer\'edi's lemma for the sparse case is certainly of great
interest.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\bibliographystyle{plain}
%\bibliography{/home/mac/yoshi/repts/FAPESP/proj-tematico/proj/refs/refs}
%\input{sparse.bbl}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{thebibliography}{10}

\bibitem{alon94}
N.~Alon, R.A. Duke, H.~Lefmann, V.~R{\"o}dl, and R.~Yuster.
\newblock The algorithmic aspects of the regularity lemma.
\newblock {\em Journal of Algorithms}, 16(1):80--109, 1994.

\bibitem{BBegt}
B.~Bollob\'as.
\newblock {\em Extremal Graph Theory}.
\newblock Academic Press, London, 1978.

\bibitem{BBf}
B.~Bollob\'as.
\newblock {\em Random Graphs}.
\newblock Academic Press, London, 1985.

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

\bibitem{chung91-set}
F.R.K. Chung and R.L. Graham.
\newblock Quasi-random set systems.
\newblock {\em Journal of the American Mathematical Society}, 4(1):151--196,
  1991.

\bibitem{chung92-Zn}
F.R.K. Chung and R.L. Graham.
\newblock Quasi-random subsets of {${\mathbb Z}\sb n$}.
\newblock {\em Journal of Combinatorial Theory, Series A}, 61(1):64--86, 1992.

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

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

\bibitem{ErdosFranklRodl86}
P.~Erd{\H o}s, P.~Frankl, and V.~R{\"o}dl.
\newblock The asymptotic number of graphs not containing a fixed subgraph and a
  problem for hypergraphs having no exponent.
\newblock {\em Graphs and Combinatorics}, 2(2):113--121, 1986.

\bibitem{ErdosTuran36}
P.~Erd{\H o}s and P.~Tur\'an.
\newblock On some sequences of integers.
\newblock {\em Journal of the London Mathematical Society}, 11(2):261--264,
  1936.

\bibitem{frankl86}
P.~Frankl and V.~R{\"o}dl.
\newblock Large triangle-free subgraphs in graphs without ${K}\sb 4$.
\newblock {\em Graphs and Combinatorics}, 2(2):135--144, 1986.

\bibitem{frankl92}
P.~Frankl and V.~R{\"o}dl.
\newblock The uniformity lemma for hypergraphs.
\newblock {\em Graphs and Combinatorics}, 8(4):309--312, 1992.

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

\bibitem{FriezeKannanRL}
A.~Frieze and R.~Kannan.
\newblock The regularity lemma and approximation schemes for dense problems.
\newblock In {\em Proc. 37th Ann. IEEE Symp. on Foundations of Computer
  Science}. IEEE, October 1996.

\bibitem{Fu}
Z.~F{\"u}redi.
\newblock Random {R}amsey graphs for the four-cycle.
\newblock {\em Discrete Mathematics}, 126:407--410, 1994.

\bibitem{GrahamNesetril86}
R.L. Graham and J.~Ne\v{s}et\v{r}il.
\newblock Large minimal sets which force long arithmetic progressions.
\newblock {\em Journal of Combinatorial Theory, Series A}, 42(2):270--276,
  1986.

\bibitem{GRo}
R.L. Graham and V.~R{\"o}dl.
\newblock Numbers in {R}amsey theory.
\newblock In C.~Whitehead, editor, {\em Surveys in Combinatorics~1987}, volume
  123 of {\em London Mathematical Society Lecture Note Series}, pages 112--153.
  Cambridge University Press, Cambridge--New York, 1987.

\bibitem{GrahamSpencer71}
R.L. Graham and J.~Spencer.
\newblock A constructive solution to a tournament problem.
\newblock {\em Canadian Mathematics Bulletin}, 14:45--48, 1971.

\bibitem{HKrotu}
P.E. Haxell and Y.~Kohayakawa.
\newblock On an anti-{R}amsey property of {Ramanujan} graphs.
\newblock {\em Random Structures and Algorithms}, 6(4):417--431, 1995.

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

\bibitem{HKLeven}
P.E. Haxell, Y.~Kohayakawa, and T.~{\L}uczak.
\newblock Tur\'an's extremal problem in random graphs: forbidding even cycles.
\newblock {\em Journal of Combinatorial Theory, Series B}, 64:273--287, 1995.

\bibitem{HKLodd}
P.E. Haxell, Y.~Kohayakawa, and T.~{\L}uczak.
\newblock Tur\'an's extremal problem in random graphs: forbidding odd cycles.
\newblock {\em Combinatorica}, 16(1):107--122, 1996.

\bibitem{kohayakawa93}
Y.~Kohayakawa.
\newblock The regularity lemma of {S}zemer\'edi for sparse graphs, 
manuscript, August 1993, 10~pp.

\bibitem{KKreuterCycles}
Y.~Kohayakawa and B.~Kreuter.
\newblock Threshold functions for asymmetric {R}amsey properties involving
  cycles.
\newblock {\em Random Structures and Algorithms}.
\newblock Submitted, 1996, 34~pp.

\bibitem{KKS}
Y.~Kohayakawa, B.~Kreuter, and A.~Steger.
\newblock An extremal problem for random graphs and the number of graphs with
  large even-girth.
\newblock {\em Combinatorica}.
\newblock Submitted, 1995, 18~pp.

\bibitem{KLRkfour}
Y.~Kohayakawa, T.~{\L}uczak, and V.~R{\"o}dl.
\newblock On {$K^4$}-free subgraphs of random graphs.
\newblock {\em Combinatorica}.
\newblock Submitted, 1995, 35~pp.

\bibitem{KLRap3}
Y.~Kohayakawa, T.~{\L}uczak, and V.~R{\"o}dl.
\newblock Arithmetic progressions of length three in subsets of a random set.
\newblock {\em Acta Arithmetica}, LXXV(2):133--163, 1996.

\bibitem{KRo-fast-sparse}
Y.~Kohayakawa and V.~R{\"o}dl.
\newblock Checking pseudorandomness of graphs fast {\rm({t}entative title)}.
\newblock In preparation, 1996.

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

\bibitem{LPS}
A.~Lubotzky, R.~Phillips, and P.~Sarnak.
\newblock Ramanujan graphs.
\newblock {\em Combinatorica}, 8:261--277, 1988.

\bibitem{NesetrilRodl87Partite}
J.~Ne\v{s}et\v{r}il and V.~R{\"o}dl.
\newblock Partite construction and {R}amseyan theorems for sets, numbers and
  spaces.
\newblock {\em Commentationes Mathematicae Universitatis Carolinae},
  28(3):569--580, 1987.

\bibitem{ProemelVoigt88}
H.-J. Pr{\"o}mel and B.~Voigt.
\newblock A sparse {G}raham--{R}othschild theorem.
\newblock {\em Transactions of the American Mathematical Society},
  309(1):113--137, 1988.

\bibitem{rodl86}
V.~R{\"o}dl.
\newblock On universality of graphs with uniformly distributed edges.
\newblock {\em Discrete Mathematics}, 59(1-2):125--134, 1986.

\bibitem{RodlAP90}
V.~R{\"o}dl.
\newblock On {R}amsey families of sets.
\newblock {\em Graphs and Combinatorics}, 16(2):187--195, 1990.

\bibitem{RodlRucinski93}
V.~R{\"o}dl and A.~Ruci\'nski.
\newblock Lower bounds on probability thresholds for {R}amsey properties.
\newblock In D.~Mikl{\'o}s, V.T. S{\'o}s, and T.~Sz{\H o}nyi, editors, {\em
  Combinatorics---{P}aul {E}rd\H{o}s is eighty, {\rm vol.~1}}, Bolyai Society
  Mathematical Studies, pages 317--346. J\'anos Bolyai Mathematical Society,
  Budapest, 1993.

\bibitem{RodlRucinski95}
V.~R{\"o}dl and A.~Ruci\'nski.
\newblock Threshold functions for {R}amsey properties.
\newblock {\em Journal of the American Mathematical Society}, 8(4):917--942,
  1995.

\bibitem{Roth53}
K.F. Roth.
\newblock On certain sets of integers.
\newblock {\em Journal of the London Mathematical Society}, 28:104--109, 1953.

\bibitem{Spencer75Restricted}
J.~Spencer.
\newblock Restricted {R}amsey configurations.
\newblock {\em Journal of Combinatorial Theory, Series A}, 19(3):278--286,
  1975.

\bibitem{szemeredi75}
E.~Szemer\'edi.
\newblock On sets of integer sets containing no $k$ elements in arithmetic
  progression.
\newblock {\em Acta Arithmetica}, 27:199--245, 1975.

\bibitem{szemeredi76}
E.~Szemer\'edi.
\newblock Regular partitions of graphs.
\newblock In {\em Probl\`emes Combinatoires et Th\'eorie des Graphes}, pages
  399--401, Orsay, 1976. Colloques Internationaux CNRS n.~260.

\bibitem{thomason87}
A.G. Thomason.
\newblock Pseudorandom graphs.
\newblock In {\em Random graphs '85 ({P}ozn\'an, 1985)}, volume 144 of {\em
  North-Holland Math. Stud.}, pages 307--331. North-Holland, Amsterdam-New
  York, 1987.

\bibitem{thomason87:_random}
A.G. Thomason.
\newblock Random graphs, strongly regular graphs pseudorandom graphs.
\newblock In C.~Whitehead, editor, {\em Surveys in Combinatorics~1987}, volume
  123 of {\em London Mathematical Society Lecture Note Series}, pages 173--195.
  Cambridge University Press, Cambridge--New York, 1987.

\end{thebibliography}
\end{document}
