%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%  TeX source file for 
%
%        THE REGULARITY LEMMA OF SZEMER\'EDI FOR SPARSE GRAPHS
%
%                          by Y. Kohayakawa
%
%                             August 1993
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\magnification=\magstep1
\newcount\spcounter
\def\setupspacing{\afterassignment\setupsp\spcounter}
\def\setupsp{\ifcase\spcounter
\baselineskip=\normalbaselineskip
\smallskipamount=\smallskipamount
\medskipamount=\medskipamount
\bigskipamount=\bigskipamount
\or
\baselineskip=1.38\normalbaselineskip
\smallskipamount=1.38\smallskipamount
\medskipamount=1.38\medskipamount
\bigskipamount=1.38\bigskipamount
\or
\baselineskip=1.53\normalbaselineskip     % Use these for
\smallskipamount=1.53\smallskipamount     % spacy output. Good for
\medskipamount=1.53\medskipamount         % Good for EJC
\bigskipamount=1.53\bigskipamount
\or
\baselineskip=1.67\normalbaselineskip     % Use these for very
\smallskipamount=1.67\smallskipamount     % spacy output. Good for
\medskipamount=1.67\medskipamount         % Good for Combinatorica
\bigskipamount=1.67\bigskipamount
\fi}
\setupspacing1
\input mssymb
\font\ninerm=cmr9   \font\eightrm=cmr8       \font\sixrm=cmr6
\font\ninei=cmmi9   \font\eighti=cmmi8       \font\sixi=cmmi6
\font\ninesy=cmsy9  \font\eightsy=cmsy8      \font\sixsy=cmsy6
\font\ninebf=cmbx9   \font\eightbf=cmbx8     \font\sixbf=cmbx6
\font\ninett=cmtt9   \font\eighttt=cmtt8
\font\nineit=cmti9   \font\eightit=cmti8
\font\ninesl=cmsl9   \font\eightsl=cmsl8
\font\ninemsa=msam9  \font\eightmsa=msam8 \font\sixmsa=msam6
\font\ninemsb=msbm9  \font\eightmsb=msbm8 \font\sixmsb=msbm6
\let\deffont=\it
%\font\deffont=cmssi10
% the following \ninepoint and \eightpoint come from the TeXbook
\def\ninepoint{\def\rm{\fam0\ninerm}%
\textfont0=\ninerm \scriptfont0=\sixrm \scriptscriptfont0=\fiverm
\textfont1=\ninei  \scriptfont1=\sixi  \scriptscriptfont1=\fivei
\textfont2=\ninesy \scriptfont2=\sixsy \scriptscriptfont2=\fivesy
\textfont3=\tenex  \scriptfont3=\tenex  \scriptscriptfont3=\tenex
\textfont\itfam=\nineit \def\it{\fam\itfam\nineit}%
\textfont\slfam=\ninesl \def\sl{\fam\slfam\ninesl}%
\textfont\ttfam=\ninett \def\tt{\fam\ttfam\ninett}%
\textfont\bffam=\ninebf \scriptfont\bffam=\sixbf
 \scriptscriptfont\bffam=\fivebf \def\bf{\fam\bffam\ninebf}%
\textfont\msafam=\ninemsa  \scriptfont\msafam=\sixmsa
  \scriptscriptfont\msafam=\fivemsa
\textfont\msbfam=\ninemsb  \scriptfont\msbfam=\sixmsb
  \scriptscriptfont\msbfam=\fivemsb
%\tt\ttglue=.5em plus.25em minus.15em
\normalbaselineskip=11.7pt
\setbox\strutbox=\hbox{\vrule height8pt depth3pt width0pt}%
\let\sc=\sevenrm%\let\big=\ninebig
\normalbaselines\rm}
\def\eightpoint{\def\rm{\fam0\eightrm}%
\textfont0=\eightrm \scriptfont0=\sixrm \scriptscriptfont0=\fiverm
\textfont1=\eighti  \scriptfont1=\sixi  \scriptscriptfont1=\fivei
\textfont2=\eightsy \scriptfont2=\sixsy \scriptscriptfont2=\fivesy
\textfont3=\tenex  \scriptfont3=\tenex  \scriptscriptfont3=\tenex
\textfont\itfam=\eightit \def\it{\fam\itfam\eightit}%
\textfont\slfam=\eightsl \def\sl{\fam\slfam\eightsl}%
\textfont\ttfam=\eighttt \def\tt{\fam\ttfam\eighttt}%
\textfont\bffam=\eightbf \scriptfont\bffam=\sixbf
 \scriptscriptfont\bffam=\fivebf \def\bf{\fam\bffam\eightbf}%
\textfont\msafam=\eightmsa  \scriptfont\msafam=\sixmsa
  \scriptscriptfont\msafam=\fivemsa
\textfont\msbfam=\eightmsb  \scriptfont\msbfam=\sixmsb
  \scriptscriptfont\msbfam=\fivemsb
%\tt\ttglue=.5em plus.25em minus.15em
\normalbaselineskip=10pt
\setbox\strutbox=\hbox{\vrule height7pt depth2pt width0pt}%
\let\sc=\sixrm%\let\big=\eightbig
\normalbaselines\rm}
\font\twelverm=cmr12
\font\twelvebf=cmbx12
\font\twelveit=cmti12
\font\twelvesl=cmsl12
\let\centreline=\centerline
\def\enddiscard{}
\long\def\discard#1\enddiscard{}
\def\date{\number\day\space
  \ifcase\month\or January\or February\or March\or April\or May\or June
               \or July\or August\or September\or November\or December\fi,
  \number\year}
%
% further maths macros
%
\def\N{{\Bbb N}}
\def\Z{{\Bbb Z}}
\def\R{{\Bbb R}}
\def\E{{\Bbb E}}
\def\P{{\Bbb P}}
\def\e{{\rm e}}
\def\Bi{\mathop{\rm Bi}\nolimits}
\def\symmdiff{\bigtriangleup}
\def\im{\mathop{\rm im}\nolimits}
\def\mod{\mathop{\rm mod}}
\def\({\left(}
\def\){\right)}
\def\[{\left[}
\def\]{\right]}
\def\<{\left\langle}
\xdef\:{\>}
\def\>{\right\rangle}  % This is different from TeX  :( 
\def\lbr{\left\{}
\def\rbr{\right\}}
\def\setof#1{\left\{#1\right\}}
\def\sizeof#1{\left|#1\right|}
\def\comp{^{\rm c}}
\def\superset{\supset}
%
\newcount\eqnocounter
\eqnocounter=0
\def\slabel#1{\global\advance\eqnocounter by1%
  \global\expandafter\edef\csname eqno#1\endcsname{(\number\eqnocounter)}%
  \eqno({\number\eqnocounter})}
\def\alabel#1{\global\advance\eqnocounter by1%
  \global\expandafter\edef\csname eqno#1\endcsname{(\number\eqnocounter)}%
  ({\number\eqnocounter})}
%
\font\titlefont=cmbx10 scaled \magstep1
\def\authorfont{\rm}
\def\addressfont{\rm}
\def\title#1{\null\vglue5truecm{\parindent=0pt\titlefont#1}}
\def\titlecont#1{\vskip.3pt{\parindent=0pt\titlefont#1}}
\def\author#1{{\authorfont\vglue1.7truecm\noindent#1}}
\def\Fapesp{${}^*$\footnote\null{{\eightpoint${^*}$ Research supported by
                                    FAPESP, Brazil, Proc.\ MAP 86/0904--8}}}
\def\NSF{\footnote{${}^{\hbox{\dag}}$}{{\eightpoint Partially
                             supported by NSF grant DMS-8806097}}}
\def\endaddress{\par\endgroup}
\def\address#1\endaddress{\medskip\begingroup
               \eightpoint\baselineskip=9pt
               \noindent\raggedright\addressfont#1\endaddress}
\newif\ifemailwanted
\emailwantedfalse
\def\DPMMS{Department of Pure Mathematics
           and Mathematical Statistics, \hfill\break
           University of Cambridge, 16 Mill Lane, Cambridge
           CB2~1SB, England\ifemailwanted\hfill\break\vskip1\jot
           \noindent{\tt e-mail: yk101@phx.cam.ac.uk}\hfill\fi}
\def\LSU{\noindent Department of Mathematics, \hfill\break
         Louisiana State University, Baton Rouge, LA 70803, USA}
\def\IMEUSP{\noindent Instituto de Matem\'atica e Estat\'\i stica, Universidade
            de S\~ao Paulo, \hfill\break
            Caixa Postal~20570, 01452--990~S\~ao Paulo, SP, Brazil}
\def\draftdate{\vglue1truecm\noindent{\eightpoint\rm Draft of \date}}
\newif\ifdraft
\newif\ifexplicitdate
\def\draftof#1{\drafttrue\explicitdatetrue\def\givendate{#1}}
\explicitdatefalse
\draftfalse
\headline={\ifdraft\hfil{\eightpoint{\sl draft of %
\ifexplicitdate\givendate\else\date\fi}}\else\hfil\fi}
\def\endabstract{\par\endgroup}
\def\abstract{\vglue1.3truecm\begingroup
  \ninepoint\noindent{\bf Abstract.\enspace}\ignorespaces}
\def\endfinalnotes{\par\endgroup}
\def\finalnotes#1.{\bigbreak\begingroup
  \eightpoint\noindent{\bf #1.\enspace}\ignorespaces}
\outer\def\proclaim #1. {\message{#1 }\medbreak
  \noindent{\bf#1.\enspace}\bgroup\sl\ignorespaces}
\def\endproclaim{\par\egroup\ifdim\lastskip<\medskipamount\removelastskip
                                \penalty1000\medskip\fi}
\outer\def\endproclaimsquare{{\unskip\nobreak\hfil\penalty50
         \hskip2em\hbox{}\nobreak\hfil\square
         \parfillskip0pt\finalhyphendemerits=0\par}% TeXbook, p 106.
 \egroup\ifdim\lastskip<\bigskipamount\removelastskip\penalty-10\bigskip\fi}
\def\endclaim{\egroup\par\ifdim\lastskip<\smallskipamount
                \removelastskip\penalty20\smallskip\fi}
\long\def\claim{\smallbreak
\noindent  
{\it Claim.\enspace}\ignorespaces\bgroup\sl}
\def\endassertion{\egroup\par\ifdim\lastskip<\smallskipamount
                \removelastskip\penalty20\smallskip\fi}
\def\endassertionsquare{{\unskip\nobreak\hfil\penalty50
         \hskip2em\hbox{}\nobreak\hfil\square
         \parfillskip0pt\finalhyphendemerits=0\par}
 \egroup\par\ifdim\lastskip<\smallskipamount\removelastskip\penalty20\smallskip\fi}
\long\def\assertion(#1){\smallbreak
\noindent 
{\rm(}{#1}{\rm)}\enspace\ignorespaces\bgroup\sl}
\def\endcase{\par\ifdim\lastskip<\smallskipamount
                \removelastskip\penalty3000\smallskip\fi}
\def\case#1.{\smallbreak
\noindent 
{\sl Case\/} #1.\enspace\ignorespaces}
\def\casenodot#1 {\smallbreak
\noindent 
{\sl Case\/} #1\enspace\ignorespaces}
\def\endcasebody{\par\ifdim\lastskip<\smallskipamount
                \removelastskip\penalty-20\smallskip\fi}
\outer\def\endcasebodysquare{{\unskip\nobreak\hfil\penalty50
         \hskip2em\hbox{}\nobreak\hfil\square
         \parfillskip0pt\finalhyphendemerits=0\par}% TeXbook, p 106.
    {\ifdim\lastskip<\bigskipamount\removelastskip\penalty-10\bigskip\fi}}
\def\casebody{\noindent\ignorespaces}
\let\proofofassertion=\casebody
\let\endproofofassertion=\endcasebody
\let\endproofofassertionsquare=\endcasebodysquare
\def\proofoftheclaim{\proofofassertion{\it Proof of the Claim\/}.\enspace}
\let\endproofoftheclaim=\endproofofassertion
\def\square{\ifmmode\sqr\else{$\sqr$}\fi}
\def\sqr{\vcenter{
         \hrule height.1mm
         \hbox{\vrule width.1mm height2.2mm\kern2.18mm\vrule width.1mm}
         \hrule height.1mm}}                  % This is a slimmer sqr.
\outer\def\endproofnoskip{{\unskip\nobreak\hfil\penalty50
         \hskip2em\hbox{}\nobreak\hfil\square
         \parfillskip0pt\finalhyphendemerits=0\par}}% TeXbook, p 106.
\outer\def\endproofsmallskip{{\unskip\nobreak\hfil\penalty50
         \hskip2em\hbox{}\nobreak\hfil\square
         \parfillskip0pt\finalhyphendemerits=0\par}% TeXbook, p 106.
    {\ifdim\lastskip<\smallskipamount\removelastskip\penalty-10\smallskip\fi}}
\outer\def\endproof{{\unskip\nobreak\hfil\penalty50
         \hskip2em\hbox{}\nobreak\hfil\square
         \parfillskip0pt\finalhyphendemerits=0\par}% TeXbook, p 106.
    {\ifdim\lastskip<\bigskipamount\removelastskip\penalty-10\bigskip\fi}}
\outer\def\endproofnosquare{\removelastskip\penalty-10\bigskip}
\let\endproofoftheclaimsquare=\endproof
\outer\def\proof{%
   \ifdim\lastskip<\medskipamount\removelastskip\penalty1000\medskip\fi
   \noindent{\it Proof.\enspace}\ignorespaces}
\outer\def\proofof#1.{%
   \ifdim\lastskip<\medskipamount\removelastskip\penalty60\medskip\fi
   \noindent{\it Proof of} {#1}.\enspace\ignorespaces}
\outer\def\proofofnodot#1 {%
   \ifdim\lastskip<\medskipamount\removelastskip\penalty60\medskip\fi
   \noindent{\it Proof of\/} {#1}\enspace\ignorespaces}
\newif\iflargesectiontitles
\largesectiontitlesfalse
\def\beginsection#1\par{\vskip0pt plus.08\vsize\penalty-250
    \vskip0pt plus-.08\vsize\bigskip\vskip\parskip
    \message{#1}\leftline{\iflargesectiontitles\twelvebf\else\bf\fi#1}%
    \nobreak\smallskip\noindent}
\def\ititem(#1){\item{({\it#1})}}
\def\ititemnohangindent(#1){\par\textindent{({\it#1\/})}}
\def\itemnohang#1{\par\textindent{#1}}
\let\TeXiff=\iff
\def\iff{\ifmmode\TeXiff\else if{}f\fi}
%
% Macros for references
%
\newif\ifPortuguese
\newif\iffirstgo
\Portuguesefalse
\def\scanreferences{\firstgotrue\refno=0\beginreferences%
                       \input refs\endreferences}%
\def\shipoutreferences{\firstgofalse\refno=0
                       \beginreferences\input refs\endreferences}
\def\endreferences{\par\endgroup}
\outer\def\beginreferences
   {\begingroup\iffirstgo\else\pretolerance=1000\tolerance=3000
    \raggedright\frenchspacing
    %\vskip0pt plus.3\vsize\penalty-150\vskip0pt plus-.3\vsize
    %\bigskip\vskip\parskip
    \vskip0pt plus.1\vsize\penalty-250
    \vskip0pt plus-.08\vsize\bigskip\vskip\parskip
    \message{References}
    \ifPortuguese\leftline{\iflargesectiontitles
                             \twelvebf\else\bf\fi Refer\^encias}%
             \else\leftline{\iflargesectiontitles
                              \twelvebf\else\bf\fi References}\fi
    \nobreak\smallskip\ninepoint\fi\obeylines}
% Journals
\def\BLMS{Bull. London Math. Soc.}
\def\JAMS{J. Amer. Math. Soc.}
\def\JLMS{J. London Math. Soc.}
\def\JCT{J. Combinatorial Theory}
\def\JCTA{J. Combinatorial Theory~(A)}
\def\JCTB{J. Combinatorial Theory~(B)}
\def\JGT{J. Graph Theory}
\def\Comb{Combinatorica}
\def\AMASH{Acta Math. Acad. Sci. Hungar.}
\def\SSMH{Studia Sci. Math. Hung.}
\def\EJC{Europ. J. Combinatorics}
\def\GC{Graphs and Combinatorics}
\def\IJM{Israel J. Math.}
\def\DM{Discrete Math.}
\def\ADM{Ann. Discrete Math.}
\def\TAMS{Trans. Amer. Math. Soc.}
\def\PAMS{Proc. Amer. Math. Soc.}
\def\PMH{Periodica Math. Hungar.}
\def\PCPS{Proc. Cambridge Phil. Soc.}
\def\MPCPS{Math. Proc. Cambridge Phil. Soc.}
\def\RSA{Random Structures and Algorithms}
% Authors
\def\Aj{Ajtai, M.}
\def\Al{Alon, N.}
\def\Be{Beck, J.}
\def\BB{Bollob\'as, B.}
\def\Chung{Chung, F.R.K.}
\def\Er{Erd\H os, P.}
\def\Fr{Frankl, P.}
\def\Fu{F\"uredi, Z.}
\def\Gra{Graham, R.L.}
\def\Ka{Katona, G.O.H.}
\def\Kl{Kleitman, D.J.}
\def\Ko{Koml\'os, J.}
\def\Lo{Lov\'asz, L.}
\def\Ne{Ne\v set\v ril, J.}
\def\Po{P\'osa, L.}
\def\Ro{R\"odl, V.}
\def\Sey{Seymour, P.}
\def\Sh{Shearer, J.B.}
\def\Si{Simonovits, M.}
\def\So{S\'os, V.T.}
\def\Sp{Spencer, J.H.}
\def\Sz{Szemer\'edi, E.}
\def\Tur{Tur\'an, P.}
\def\Tutte{Tutte, W.T.}
\def\Tu{Tuza, Zs.}
%
\newcount\refno
\def\vol{}
\begingroup
\obeylines
\long\global\def\paper[#1] #2
#3
#4\vol#5
#6, #7
{\global\advance\refno by1%
 \iffirstgo\global\expandafter\edef\csname ref#1\endcsname{[\number\refno]}%
           \global\expandafter\edef\csname refnb#1\endcsname{\number\refno}%  
  \else\smallskip\item{[\number\refno]} %
#2, #3, {\it#4}~{\bf#5} (#7), \hbox{#6}.\fi}%
\global\def\proceedings[#1] #2
#3
#4
#5
#6
#7
{\global\advance\refno by1%
\iffirstgo\global\expandafter\edef\csname ref#1\endcsname{[\number\refno]}%
           \global\expandafter\edef\csname refnb#1\endcsname{\number\refno}%  
\else\smallskip\item{[\number\refno]} #2, #3, {\it in} {``#4''}, #5 (#6 eds), %
\hbox{#7}.\fi}%
\global\def\book[#1] #2
#3
#4
{\global\advance\refno by1%
\iffirstgo\global\expandafter\edef\csname ref#1\endcsname{[\number\refno]}%
          \global\expandafter\edef\csname refnb#1\endcsname{\number\refno}%
 \else\smallskip\item{[\number\refno]} #2, {\it #3\/}, #4.\fi}%
\global\def\preprint[#1] #2
#3
#4
{\global\advance\refno by1%
\iffirstgo\global\expandafter\edef\csname ref#1\endcsname{[\number\refno]}%
           \global\expandafter\edef\csname refnb#1\endcsname{\number\refno}%  
\else\smallskip\item{[\number\refno]} #2, #3, #4.\fi}%
\global\def\privatecomm[#1] #2
{\global\advance \refno by1%
\iffirstgo\global\expandafter\edef\csname ref#1\endcsname{[\number\refno]}%
           \global\expandafter\edef\csname refnb#1\endcsname{\number\refno}%  
\else\smallskip\item{[\number\refno]} #2, private communication.\fi}%
\global\def\unpublished[#1] #2
{\global\advance \refno by1%
\iffirstgo\global\expandafter\edef\csname ref#1\endcsname{[\number\refno]}%
           \global\expandafter\edef\csname refnb#1\endcsname{\number\refno}%  
\else\smallskip\item{[\number\refno]} #2, unpublished.\fi}%
\global\def\dammit[#1] #2
#3
{\global\advance \refno by1%
\iffirstgo\global\expandafter\edef\csname ref#1\endcsname{[\number\refno]}%
           \global\expandafter\edef\csname refnb#1\endcsname{\number\refno}%  
\else\smallskip\item{[\number\refno]} #2, #3.\fi}%
\endgroup
%
%\draftof{21 January, 1993}
%
% statems.tex
%
\newif\ifchapters
\chapterstrue
\newcount\chapterno\chapterno=0
\newcount\statemno\statemno=1
\def\yeschapters{\def\statementlabel{%\number\chapterno.
                                      \number\statemno}
              \def\newchapter{\statemno=1\advance\chapterno by1}}
\def\nochapters{\def\statementlabel{\number\statemno}
                \def\newchapter{\relax}}
\ifchapters\yeschapters\else\nochapters\fi
\def\newstatemno{\advance\statemno by1}
%
\edef\SSz
{\statementlabel}\newstatemno
\edef\LemmaDefCS
{\statementlabel}\newstatemno
\edef\LemmaB
{\statementlabel}\newstatemno
\edef\LemmaC
{\statementlabel}\newstatemno
\edef\LemmaD
{\statementlabel}\newstatemno
\edef\LemmaE
{\statementlabel}\newstatemno
\edef\LemmaF
{\statementlabel}\newstatemno
%
% macros.tex
%
\def\dHG{d_{H,G}}
\def\eG{e_G}
\def\eH{e_H}
\def\dstS{d^*_{s,t}}
\let\epsilon=\varepsilon
\def\ind{\mathop{\rm ind}\nolimits}
\def\G{{\cal G}}
%
% \scanreferences
%
\firstgotrue\refno=0\beginreferences
\paper[AYu] \Al, Yuster, R.
            Almost $H$-factors in dense graphs
            \GC\vol8
            95--102, 1992
\dammit[BESiSz] \BB, \Er, \Si, \Sz
            Extremal graphs without large forbidden subgraphs, in %
            {\it Advances in Graph Theory\/} (\BB, ed.), %
            Annals of Discrete Mathematics~3, North--Holland, %
            Amsterdam~1978, pp.~29--41
\paper[Chung] \Chung
            Regularity lemmas for hypergraphs and quasi-randomness
            \RSA\vol2
            241--252, 1991
\paper[ChRoSzTr] Chv\'atal, V., \Ro, \Sz, Trotter, W.T.
            The Ramsey number of a graph with bounded degree 
            \JCTB\vol34
            239--243, 1983          
\paper[CSz] Chv\'atal, V., \Sz
            On the Erd\H os--Stone theorem
            \JLMS\vol23
            207--214, 1981
\paper[EFR] \Er, \Fr, \Ro
            The asymptotic number of graphs not containing a fixed %
            subgraph and a problem for hypergraphs having no exponent
            \GC\vol2
            113--121, 1986
\paper[FrRoRL] \Fr, \Ro
            The uniformity lemma for hypergraphs
            \GC\vol8
            309--312, 1992
\paper[FuDiam] \Fu
            The maximum number of edges in a %
            minimal graph of diamter~$2$
            \JGT\vol16
            81--98, 1992
\dammit[HKb] Haxell, P.E., Kohayakawa, Y.
            On an anti-Ramsey property of Ramanujan graphs, in preparation 
\dammit[HKc] Haxell, P.E., Kohayakawa, Y.
            Ramsey and Tur\'an type results for cycles in %
            pseudo-random graphs, in preparation
\paper[PrSte] Pr\"omel, H.-J., Steger, A.
            Excluding induced subgraphs~III: a general asymptotic
            \RSA\vol3
            19--31, 1992
\paper[Ro]  \Ro
            On universality of graphs with uniformly distributed edges 
            \DM\vol59
            125--143, 1986
\dammit[RoPC] \Ro
            Personal communication, August, 1993
\paper[RoDu] \Ro, Duke, R.A.
            On graphs with small subgraphs %
            of large chromatic number
            \GC\vol1
            91--96, 1985
\paper[RuSz] Ruzsa, I.Z., \Sz
            Triple systems with no six points carrying three triangles
            Coll. Math. Soc. J\'anos Bolyai\vol18
            939--945, 1978
\paper[SzAP] \Sz
            On a set containing no $k$~elements %
            in arithmetic progression 
            Acta Arithmetica\vol{XXVII}
            199--245, 1975
\dammit[Sz] \Sz
            Regular partitions of graphs, %
            in {\it Probl\`emes Combinatoires et Th\'eorie des Graphes\/}, %
            Proc. Colloque Inter. CNRS %
            (Bermond, J.-C., Fournier, J.-C., Las Vergnas, M., %
            Sotteau, D., eds), CNRS, Paris~1978, pp.~399--401
\endreferences
%
% fstpg.tex
%
\title{The Regularity Lemma of Szemer\'edi for Sparse Graphs}

\author{Y.~Kohayakawa}
\address
\DPMMS\medskip
\noindent\IMEUSP
\endaddress
\abstract
In this note we present a new version of the well-known lemma of
Szemer\'edi~{\refSz} concerning regular partitions of graphs.  Our result
deals with subgraphs of pseudo-random graphs, and hence may be used to
partition sparse graphs that do no contain dense subgraphs.
\endabstract
%
% intro.tex
%
\beginsection 1. Introduction

Our aim in this note is to give a simple extension of the beautiful regularity
lemma of Szemer\'edi~{\refSz}. As is well known, a version of this lemma for
bipartite graphs was one of the ingredients in Szemer\'edi's celebrated
proof~{\refSzAP} of the Erd\H os--Tur\'an conjecture on arithmetic
progressions in dense subsets of integers. Furthermore, this bipartite version
was also used by Ruzsa and Szemer\'edi~{\refRuSz} to solve an extremal problem
concerning set systems.

The regularity lemma for generic graphs given in Szemer\'edi~{\refSz} has been
used by many authors, and it has proved to play a crucial r\^ole in extremal
graph theory. A few papers in which this lemma is important are Alon and
Yuster~{\refAYu}, Bollob\'as, Erd\H os, Simonovits, and
Szemer\'edi~{\refBESiSz}, Chv\'atal, R\"odl, Szemer\'edi, and
Trotter~{\refChRoSzTr}, Chv\'atal and Szemer\'edi~{\refCSz}, 
Erd\H os, Frankl, and R\"odl~{\refEFR}, F\"uredi~{\refFuDiam},
R\"odl~{\refRo}, and R\"odl and Duke~{\refRoDu}. (We do not attempt to compile
an exhaustive list here.)

More recently, generalisations of Szemer\'edi's lemma have been found and used
by several authors. We mention Chung~{\refChung}, Frankl and
R\"odl~{\refFrRoRL}, and Pr\"omel and Steger~{\refPrSte}. The novelty in these
generalisations resides in that Szemer\'edi's result is extended to
hypergraphs.  Our aim here is to present a generalisation of this lemma to
sparse graphs.  Roughly speaking, we are concerned here in finding regular
partitions of subgraphs of pseudo-random graphs. We remark that this new
version of the regularity lemma is used in~{\refHKb} and~{\refHKc}. Moreover, 
we have been kindly informed that Professor R\"odl~{\refRoPC} has also
observed that this version of the regularity lemma holds. 

The necessary definitions and the statement of our result, Theorem~{\SSz}, is
given in Section~2 below. We stress that our proof of Theorem~{\SSz}, which we
give in Section~3, is simply an adaptation of Szemer\'edi's original
proof~{\refSz} to our context. Finally, we note that suitable generalisations
of Theorem~{\SSz} to subhypergraphs of pseudo-random hypergraphs can be
readily proved. Here, however, we restrict ourselves to the simplest case. 
%
% main.tex
%
\beginsection 2. The regularity lemma for pseudo-random graphs

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$. We may now define the pseudo-random
property that we shall be interested in.

Suppose~$0\leq\eta\leq1$. We say that~$G$ is {\deffont$(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
$$
\big|\eG(U,W)-p|U||W|\big|\leq\eta p|U||W|.     \slabel{Unif}
$$
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
{\deffont$\eta$-uniform\/}.

The prime example of an $\eta$-uniform graph is of course a random
graph~$G_p$.  Note that for~$\eta>0$ a random graph~$G_p\in\G(n,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$.

Now let us go back to some definitions. Recall a graph~$G=G^n$ is fixed.
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 {\deffont$(\epsilon,H,G)$-regular\/}, or
simply {\deffont$\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
{\deffont$(\epsilon,k)$-equitable\/} if~$|C_0|\leq\epsilon n$,
and~$|C_1|=\ldots=|C_k|$. Also, we say that~$C_0$ is the {\deffont
exceptional\/} class of~$Q$. When the value of~$\epsilon$ is not relevant, we
refer to an $(\epsilon,k)$-equitable partition as a {\deffont$k$-equitable\/}
partition. Similarly, $Q$~is an {\deffont 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$ {\deffont 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$ {\deffont
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 {\deffont$(\epsilon,H,G)$-regular\/}, or
simply {\deffont$\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 can
now state the extension of Szemer\'edi's lemma to subgraphs of
$(P_0,\eta)$-uniform graphs.

\proclaim Theorem {\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$.
\endproclaim

\beginsection 3. The proof of Theorem~{\SSz}

We now proceed to give the proof Theorem~{\SSz}. As in~{\refSz}, the following
`defect' form of the Cauchy--Schwarz inequality is used in the proof.

\proclaim Lemma {\LemmaDefCS}. Let~$y_1,\ldots,y_v\geq0$ be given.
Suppose~$0\leq\rho=u/v<1$, and~$\sum_{1\leq i\leq u}y_i=\alpha\rho\sum_{1\leq
i\leq v}y_i$. Then
$$
\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\sqr
$$
\endproclaim

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~{\eqnoUnif}. 

\proclaim Lemma {\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
\item{({\it i\/})}$|\dHG(U^*,W^*)-\dHG(U,W)|\leq5\delta$,
\item{({\it ii\/})}$|\dHG(U^*,W^*)^2-\dHG(U,W)^2|\leq9\delta$.
\endproclaim
\proof
Note first that we have~$\eta\leq\delta$, as~$\eta n\leq\delta|U|$,
$\delta|W|\leq\delta n$. Let~$U^*$, $W^*$ be as given in the lemma.
We first check~({\it i\/}). 

({\it i\/})~We start by noticing that
$$
\eqalignno{
\dHG(U^*,W^*)&\geq{\eH(U,W)-2(1+\eta)p\delta|U||W|\over\eG(U,W)} \cr
  &\qquad\qquad\geq\dHG(U,W)-2\delta{1+\eta\over1-\eta}
           \geq\dHG(U,W)-3\delta.
}
$$
Moreover,
$$
\eqalignno{
\dHG(U^*,W^*)\leq{\eH(U,W)\over\eG(U^*,W^*)}
                  \leq{\eH(U,W)\over(1-\eta)p|U^*||W^*|} 
  \leq{\eH(U,W)\over(1-\eta)p(1-\delta)^2|U||W|}\quad\qquad&\cr
    \leq{1+\eta\over(1-\eta)(1-\delta)^2}\dHG(U,W)\leq\dHG(U,W)+5\delta. \cr
}
$$
Thus~({\it i\/}) follows.

({\it ii\/})~The argument here is similar. First
$$
\eqalignno{
\dHG(U^*,W^*)
      &\geq{\big(\eH(U,W)-2(1+\eta)p\delta|U||W|\big)^2\over\eG(U,W)^2}\cr 
      &\geq\dHG(U,W)^2-{4(1+\eta)p\delta|U||W|\eH(U,W)
          \over\eG(U,W)(1-\eta)p|U||W|} \cr
      &\geq\dHG(U,W)^2-4\delta{1+\delta\over1-\delta}
                \geq\dHG(U,W)^2-5\delta. \cr
}
$$
Secondly,
$$
\eqalignno{
\dHG(U^*,W^*)^2&\leq{\eH(U,W)^2\over\eG(U^*,W^*)^2}\cr
&\leq{\eH(U,W)^2\over(1-\eta)^2p^2|U^*|^2|W^*|^2}
               \leq{\eH(U,W)^2\over(1-\eta)^2(1-\delta)^4p^2|U||W|}\cr
&\leq\(1+\eta\over(1-\eta)(1-\delta)^2\)^2\dHG(U,W)^2
   \leq\dHG(U,W)^2+9\delta. \cr
}
$$
Thus~({\it ii\/}) follows.
\endproof

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 {\deffont atoms\/} of~$C_s$. Now let~$q=4^k$ and
set~$m=\lfloor|C_s|/q\rfloor$ ($1\leq s\leq k$). Note
that~$\lfloor|C_s|/m\rfloor=q$ as~$|C_s|\geq n/2k\geq2q^2$. Moreover, for
later use, note that~$m\geq\eta n$. We now let~$Q'$ be a partition of~$V=V(G)$
refining~$P$ such that ({\it i\/})~$C_0$ is a block of~$Q'$, ({\it ii\/})~all
other blocks of~$Q'$ have cardinality~$m$, except for possibly one, which has
cardinality at most~$m-1$, ({\it iii\/})~for all~$1\leq s\leq k$, every
atom~$A\subset C_s$ contains exactly~$\lfloor|A|/m\rfloor$ blocks of~$Q'$,
({\it iv\/})~for all~$1\leq s\leq k$, the set~$C_s$ contains
exactly~$q=\lfloor|C_s|/m\rfloor$ blocks of~$Q'$.

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

\proclaim Lemma {\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}$.
\endproclaim
\proof
Clearly~$Q$ refines~$P$. Moreover, clearly~$m=|C'_1|=\ldots=|C'_{k'}|$ and,
for all~$1\leq s\leq k$, we
have~$|C'_0|\leq|C_0|+k(m-1)\leq|C_0|+k|C_s|/q\leq|C_0|+n4^{-k}$.
\endproof

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~{\LemmaB}
we have, for all~$1\leq s<t\leq k$,
$$
|\dHG(C_s^*,C_t^*)-\dHG(C_s,C_t)|\leq5q^{-1} \slabel{S}
$$
and
$$
|\dHG(C_s^*,C_t^*)^2-\dHG(C_s,C_t)^2|\leq9q^{-1} \slabel{SS}
$$
Similarly to~{\refSz}, we define the {\deffont 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$. Our aim now is to show that,
for~$Q=Q(P)$ defined as above, we have~$\ind(Q)\geq\ind(P)+\epsilon^5/100$. We
start with the following lemma.

\proclaim Lemma {\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}.
$$
\endproclaim
\proof
By the $(P_0,\eta)$-uniformity of~$G$ and the fact that~$(C_s,C_t)\prec P_0$,
we have 
$$
\eqalignno{
{1\over q^2}\sum_{1\leq i\leq q}\sum_{1\leq j\leq q}&\dHG(C_s(i),C_t(j))
  ={1\over q^2}\sum_{i,\,j}{\eH(C_s(i),C_t(j))\over\eG(C_s(i),C_t(j))}\cr
  &\qquad\geq\sum_{i,\,j}{\eH(C_s(i),C_t(j))\over(1+\eta)q^2p|C_s(i)||C_t(j)|}
   ={\eH(C_s^*,C_t^*)\over(1+\eta)p|C_s^*||C_t^*|}\cr
  &\qquad\geq{1-\eta\over1+\eta}\dHG(C_s^*,C_t^*)
          \geq\dHG(C_s^*,C_t^*)-2\eta.\cr
}
$$
Thus, by the Cauchy--Schwarz inequality, we have
$$
{1\over q^2}\sum_{1\leq i\leq q}\sum_{1\leq j\leq q}\dHG(C_s(i),C_t(j))^2
   \geq\dHG(C_s^*,C_t^*)^2-4\eta.
$$
Furthermore, by~{\eqnoSS}, we
have~$\dHG(C_s^*,C_t^*)^2\geq\dHG(C_s,C_t)^2-9q^{-1}$.
Since~$9q^{-1}+4\eta\leq\epsilon^5/100$, the lemma follows.
\endproof

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

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

We are now ready to prove the main lemma needed in the proof of
Theorem~{\SSz}.

\proclaim Lemma {\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 ({\it i\/})~$Q$~refines~$P$, ({\it ii\/})~$k'=k4^k$, ({\it
iii\/})~$|C_0'|\leq|C_0|+n4^{-k}$, and ({\it
iv\/})~$\ind(Q)\geq\ind(P)+\epsilon^5/100$.
\endproclaim
\proof
Let~$P$ be as in the lemma. We show that the $k'$-equitable
partition~$Q=(C'_i)_0^{k'}$ defined from~$P$ as above satisfies~({\it
i\/})--({\it iv\/}). In view of Lemma~{\LemmaC}, it only remains to
check~({\it iv\/}). By Lemmas~{\LemmaD} and~{\LemmaE}, we have
$$
\eqalignno{
\ind(Q)
&={2\over(kq)^2}\sum_{1\leq i\leq q}\sum_{1\leq j\leq q}\dHG(C'_i,C'_j)^2 \cr
&\geq{2\over k^2}\sum_{1\leq s<t\leq k}{1\over q^2}
   \sum_{1\leq i\leq q}\sum_{1\leq j\leq q}\dHG(C_s(i),C_t(j))^2\cr
&\geq{2\over k^2}
  \Bigg\{\sum_{1\leq s<t\leq k}\(\dHG(C_s,C_t)^2-{\epsilon^5\over100}\)
         +\epsilon{k\choose2}{\epsilon^4\over40}
  \Bigg\}\cr
&\qquad\geq\ind(P)-{\epsilon^5\over100}+{\epsilon^5\over50}
\geq\ind(P)+{\epsilon^5\over100}.\cr
}
$$
This completes the proof of the lemma.
\endproof

\proofof{{\it Theorem~{\SSz}\/}}. Let~$\epsilon>0$, $k_0\geq1$,
and~$\ell\geq1$ be given. We may assume that~$\epsilon\leq1/2$. Pick~$s\geq1$
such that~$4^{s/4\ell}\geq1800\epsilon^{-5}$,
$s\geq\max\{2k_0,3\ell/\epsilon\}$, and~$\epsilon4^{s-1}\geq1$. Let~$f(0)=s$,
and put inductively~$f(t)=f(t-1)4^{f(t-1)}$ ($t\geq1$).
Let~$t_0=\lfloor100\epsilon^{-5}\rfloor$ and set~$N=\max\{n_0(f(t)):0\leq t\leq
t_0\}=f(t_0)4^{2f(t_0)+1}$, $K_0=\max\{6\ell/\epsilon,N\}$,
and~$\eta=\eta(\epsilon,k_0,\ell)=\min\{\eta_0(f(t)):0\leq t\leq
t_0\}=1/4f(t_0+1)>0$. We claim that~$\eta$ and~$K_0$ as
defined above will do.

To prove our claim, let~$G=G^n$ be a fixed $(P_0,\eta)$-uniform graph,
where~$P_0=(V_i)_1^\ell$ is a partition of~$V=V(G)$. Furthermore,
let~$H\subset G$ be a spanning subgraph of~$G$.  Note that we may clearly
assume that~$n\geq K_0$.  Suppose~$t\geq0$. Let us say that an equitable
partition~$P^{(t)}=(C_i)_0^k$ of~$V$ is {\deffont$t$-valid\/} if ({\it
i\/})~$P^{(t)}$ refines~$P_0$, ({\it ii\/})~$s/4\ell\leq k\leq f(t)$, ({\it
iii\/})~$\ind\{P^{(t)}\}\geq t\epsilon^5/100$, and ({\it
iv\/})~$|C_0|\leq\epsilon n(1-2^{-(t+1)})$. We now verify that a $0$-valid
partition~$P^{(0)}$ of~$V$ does exist. Let~$m=\lceil n/s\rceil$, and let~$Q$
be a partition of~$V$ with all blocks of cardinality~$m$, except for possibly
one, which has cardinality at most~$m-1$, and moreover such that each~$V_i$
($1\leq i\leq\ell$) contains~$\lfloor|V_i|/m\rfloor$ blocks of~$Q$. Grouping
at most~$\ell$ blocks of~$Q$ into a single block~$C_0$, we arrive at an
equitable partition~$P^{(0)}=(C_i)_0^k$ of~$V$ that is $0$-valid. Indeed,
({\it i\/})~is clear, and to check~({\it ii\/}) note that~$k\leq n/m\leq
s=f(0)$, and that there is~$1\leq i\leq\ell$ such that~$|V_i|\geq n/\ell$, and
so~$k\geq\lfloor|V_i|/m\rfloor\geq\lfloor(n/\ell)/\lceil
n/s\rceil\rfloor\geq(1/2)\{(n/\ell)/(2n/s)\}=s/4\ell$. Also, ({\it iii\/})~is
trivial and~({\it iv\/}) does follow, since~$|C_0|<\ell m\leq\ell\lceil
n\epsilon/3\ell\rceil\leq n\epsilon/2$ as~$n\geq K_0\geq6\ell/\epsilon$.

Now note that if there is a $t$-valid partition~$P^{(t)}$ of~$V$, then~$t\leq
t_0=\lfloor100\epsilon^{-5}\rfloor$, since~$\ind\{P^{(t)}\}\leq1$. Suppose~$t$
is the maximal integer for which there is a $t$-valid partition~$P^{(t)}$
of~$V$. We claim that~$P^{(t)}$ is $(\epsilon,H,G)$-regular. Suppose to the
contrary that~$P^{(t)}$ is not $(\epsilon,H,G)$-regular. Then simply note that
Lemma~{\LemmaF} gives a $(t+1)$-valid equitable
partition~$P^{(t+1)}=Q=Q(P^{(t)})$, contradicting the maximality of~$t$. This
completes the proof of the theorem.
\endproof
\finalnotes
Acknowledgements. The author was supported by Churchill College, Cambridge, 
where he was a Junior Research Fellow while this work was being done.
\endfinalnotes
%
% \shipoutreferences
%
\firstgofalse\refno=0
\beginreferences
\paper[AYu] \Al, Yuster, R.
            Almost $H$-factors in dense graphs
            \GC\vol8
            95--102, 1992
\dammit[BESiSz] \BB, \Er, \Si, \Sz
            Extremal graphs without large forbidden subgraphs, in %
            {\it Advances in Graph Theory\/} (\BB, ed.), %
            Annals of Discrete Mathematics~3, North--Holland, %
            Amsterdam~1978, pp.~29--41
\paper[Chung] \Chung
            Regularity lemmas for hypergraphs and quasi-randomness
            \RSA\vol2
            241--252, 1991
\paper[ChRoSzTr] Chv\'atal, V., \Ro, \Sz, Trotter, W.T.
            The Ramsey number of a graph with bounded degree 
            \JCTB\vol34
            239--243, 1983          
\paper[CSz] Chv\'atal, V., \Sz
            On the Erd\H os--Stone theorem
            \JLMS\vol23
            207--214, 1981
\paper[EFR] \Er, \Fr, \Ro
            The asymptotic number of graphs not containing a fixed %
            subgraph and a problem for hypergraphs having no exponent
            \GC\vol2
            113--121, 1986
\paper[FrRoRL] \Fr, \Ro
            The uniformity lemma for hypergraphs
            \GC\vol8
            309--312, 1992
\paper[FuDiam] \Fu
            The maximum number of edges in a %
            minimal graph of diamter~$2$
            \JGT\vol16
            81--98, 1992
\dammit[HKb] Haxell, P.E., Kohayakawa, Y.
            On an anti-Ramsey property of Ramanujan graphs, in preparation 
\dammit[HKc] Haxell, P.E., Kohayakawa, Y.
            Ramsey and Tur\'an type results for cycles in %
            pseudo-random graphs, in preparation
\paper[PrSte] Pr\"omel, H.-J., Steger, A.
            Excluding induced subgraphs~III: a general asymptotic
            \RSA\vol3
            19--31, 1992
\paper[Ro]  \Ro
            On universality of graphs with uniformly distributed edges 
            \DM\vol59
            125--143, 1986
\dammit[RoPC] \Ro
            Personal communication, August, 1993
\paper[RoDu] \Ro, Duke, R.A.
            On graphs with small subgraphs %
            of large chromatic number
            \GC\vol1
            91--96, 1985
\paper[RuSz] Ruzsa, I.Z., \Sz
            Triple systems with no six points carrying three triangles
            Coll. Math. Soc. J\'anos Bolyai\vol18
            939--945, 1978
\paper[SzAP] \Sz
            On a set containing no $k$~elements %
            in arithmetic progression 
            Acta Arithmetica\vol{XXVII}
            199--245, 1975
\dammit[Sz] \Sz
            Regular partitions of graphs, %
            in {\it Probl\`emes Combinatoires et Th\'eorie des Graphes\/}, %
            Proc. Colloque Inter. CNRS %
            (Bermond, J.-C., Fournier, J.-C., Las Vergnas, M., %
            Sotteau, D., eds), CNRS, Paris~1978, pp.~399--401
\endreferences
\bye
