%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%                          AmSTeX file for
%
%  ARITHMETIC PROGRESSIONS OF LENGTH THREE IN SUBSETS OF A RANDOM SET
%
%               by Y. Kohayakawa, T. Luczak, and V. Rodl
%
%                     Latest update: 5 June 1995
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\magnification=\magstep1
%\input style
\input amstex
%\input amssym
\loadmsam
\loadmsbm
%\load
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% my.sty
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\documentstyle{my}
\catcode`\@=11
\ifx\amspptloaded@AmS\relax\catcode`\@=\active
 \endinput\else\let\amspptloaded@AmS\relax\fi
\parindent10\p@
%\voffset=-0.65 cm
\ifnum\mag=1000
  \hsize 16.5 cm
  \vsize 23 cm
  \captionwidth@\hsize
  \advance\captionwidth@-3 cm
\else  
  \hsize 16.5  true cm
  \vsize 23 true cm
  \captionwidth@\hsize
  \advance\captionwidth@-3 true cm
\fi
\normallineskiplimit\p@
%\captionwidth@\hsize
%\advance\captionwidth@-1.5in
\font@\ninerm=cmr9
\font@\eightrm=cmr8
\font@\sixrm=cmr6
\font@\ninei=cmmi9    \skewchar\ninei='177
\font@\eighti=cmmi8   \skewchar\eighti='177
\font@\sixi=cmmi6     \skewchar\sixi='177
\font@\ninesy=cmsy9   \skewchar\ninesy='60
\font@\eightsy=cmsy8  \skewchar\eightsy='60
\font@\sixsy=cmsy6    \skewchar\sixsy='60
\font@\ninebf=cmbx9
\font@\eightbf=cmbx8
\font@\sixbf=cmbx6
\font@\nineit=cmti9
\font@\eightit=cmti8
\font@\ninesl=cmsl9
\font@\eightsl=cmsl8
%\font@\nineeux=euxm9
%\font@\eighteux=euxm8
%\font@\sixeux=euxm6
%\font@\nineeuy=euym9
%\font@\eighteuy=euym8
%\font@\sixeuy=euym6
\font@\tensmc=cmcsc10
\font@\lc=cmcsc10 %at 8truept
\def\tenpoint{\def\pointsize@{10}%
% \normalbaselineskip12\p@
% \abovedisplayskip12\p@ plus3\p@ minus9\p@
% \belowdisplayskip12\p@ plus3\p@ minus9\p@
% \abovedisplayshortskip\z@ plus3\p@
% \belowdisplayshortskip7\p@ plus3\p@ minus4\p@
% Changed all skips to be roughly proportional to 16pt baselineskip 
% (12 pt after reduction by 75%, 13 1/3 points before magnification=1200).
% \normalbaselineskip12\p@
% \abovedisplayskip12\p@ plus3\p@ minus9\p@
% \belowdisplayskip12\p@ plus3\p@ minus9\p@
% \abovedisplayshortskip\z@ plus3\p@
% \belowdisplayshortskip7\p@ plus3\p@ minus4\p@
 \normalbaselineskip 13.333333 pt
 \abovedisplayskip 13.333333 pt plus 3.333333 pt minus 9.999999 pt
 \belowdisplayskip 13.333333 pt plus 3.333333 pt minus 9.999999 pt
 \abovedisplayshortskip 0 pt plus 3.333333 pt
 \belowdisplayshortskip 7.777777 pt plus 3.333333 pt minus 4.444444 pt
% Added the following changes to various skips to make them proportional to
% 16 pt baselineskips (12 points after reduction). 
% Also, I made the parskip bigger; there seemed to
% be too little space between paragraphs and items in a \roster.
% see the definitions in plain.tex.
 \smallskipamount= 3.333333 pt plus 1.111111 pt minus 1.111111 pt
 \medskipamount=6.666666 pt plus 2.222222 pt minus 2.222222 pt
 \bigskipamount=13.333333 pt plus 4.444444 pt minus 4.444444 pt
 \parskip=2 pt plus 1 pt
 \parindent 16.666666 pt
% end of addition
 \textonlyfont@\rm\tenrm
 \textonlyfont@\it\tenit
 \textonlyfont@\sl\tensl
 \textonlyfont@\bf\tenbf
 \textonlyfont@\smc\tensmc
 \ifsyntax@\def\big##1{{\hbox{$\left##1\right.$}}}\else
 \let\big\tenbig@
 \textfont\z@\tenrm  \scriptfont\z@\sevenrm  \scriptscriptfont\z@\fiverm
 \textfont\@ne\teni  \scriptfont\@ne\seveni  \scriptscriptfont\@ne\fivei
 \textfont\tw@\tensy \scriptfont\tw@\sevensy \scriptscriptfont\tw@\fivesy
 \textfont\thr@@\tenex \scriptfont\thr@@\tenex \scriptscriptfont\thr@@\tenex
 \textfont\itfam\tenit
 \textfont\slfam\tensl
 \textfont\bffam\tenbf \scriptfont\bffam\sevenbf
  \scriptscriptfont\bffam\fivebf
 %\textfont\euxfam=\teneux
 %\scriptfont\euxfam=\seveneux
 %\scriptscriptfont\euxfam=\fiveeux
 %\textfont\euyfam=\teneuy
 %\scriptfont\euyfam=\seveneuy
 %\scriptscriptfont\euyfam=\fiveeuy
 \fi
 \setbox\strutbox\hbox{\vrule height8.5\p@ depth3.5\p@ width\z@}%
 \setbox\strutbox@\hbox{\vrule height8\p@ depth3\p@ width\z@}%
 \normalbaselines\tenrm\ex@=.2326ex}
\def\eightpoint{\def\pointsize@{8}%
 \normalbaselineskip10\p@
 \abovedisplayskip10\p@ plus2.4\p@ minus7.2\p@
 \belowdisplayskip10\p@ plus2.4\p@ minus7.2\p@
 \abovedisplayshortskip\z@ plus2.4\p@
 \belowdisplayshortskip5.6\p@ plus2.4\p@ minus3.2\p@
% Made values for the following skips explicit.
% The values for single spaced 10 point were used, except for parskip.
 \smallskipamount=3\p@ plus 1\p@ minus 1\p@
 \medskipamount=6\p@ plus 2\p@ minus 2\p@
 \bigskipamount=12\p@ plus 4\p@ minus 4\p@
 \parskip=0\p@ plus 1\p@
 \parindent 11.111111 pt
% end of addition
  \textonlyfont@\rm\eightrm
 \textonlyfont@\it\eightit
 \textonlyfont@\sl\eightsl
 \textonlyfont@\bf\eightbf
 \ifsyntax@\def\big##1{{\hbox{$\left##1\right.$}}}\else
 \let\big\eightbig@
 \textfont\z@\eightrm \scriptfont\z@\sixrm  \scriptscriptfont\z@\fiverm
 \textfont\@ne\eighti \scriptfont\@ne\sixi  \scriptscriptfont\@ne\fivei
 \textfont\tw@\eightsy \scriptfont\tw@\sixsy \scriptscriptfont\tw@\fivesy
 \textfont\thr@@\tenex \scriptfont\thr@@\tenex \scriptscriptfont\thr@@\tenex
 \textfont\itfam\eightit
 \textfont\slfam\eightsl
 \textfont\bffam\eightbf \scriptfont\bffam\sixbf
   \scriptscriptfont\bffam\fivebf
 %\textfont\euxfam=\eighteux
 %\scriptfont\euxfam=\sixeux
 %\scriptscriptfont\euxfam=\fiveeux
 %\textfont\euyfam=\eighteuy
 %\scriptfont\euyfam=\sixeuy
 %\scriptscriptfont\euyfam=\fiveeuy
 \fi
 \setbox\strutbox\hbox{\vrule height7\p@ depth3\p@ width\z@}%
 \setbox\strutbox@\hbox{\vrule height6.5\p@ depth2.5\p@ width\z@}%
 \normalbaselines\eightrm\ex@=.2326ex}
\def\tenbig@#1{{\hbox{$\left#1\vbox to8.5\p@{}\right.\n@space$}}}
\def\eightbig@#1{{\hbox{$\textfont\z@\ninerm\textfont\tw@\ninesy
 \left#1\vbox to6.5\p@{}\right.\n@space$}}}
\def\footmarkform@#1{$^{#1}$}
\let\thefootnotemark\footmarkform@
\def\makefootnote@#1#2{\insert\footins
 {\interlinepenalty\interfootnotelinepenalty
 \eightpoint\splittopskip\ht\strutbox\splitmaxdepth\dp\strutbox
 \floatingpenalty\@MM\leftskip\z@\rightskip\z@\spaceskip\z@\xspaceskip\z@
 \indent{#1}\footstrut\ignorespaces#2\unskip\lower\dp\strutbox
 \vbox to\dp\strutbox{}}}
\newcount\footmarkcount@
\footmarkcount@\z@
\def\footnotemark{\let\@sf\empty\relaxnext@\ifhmode\edef
 \@sf{\spacefactor\the\spacefactor}\/\fi
 \def\next@{\ifx[\next\let\next\nextii@\else
  \ifx"\next\let\next\nextiii@\else
  \let\next\nextiv@\fi\fi\next}%
 \def\nextii@[##1]{\footmarkform@{##1}\@sf}%
 \def\nextiii@"##1"{{##1}\@sf}%
 \def\nextiv@{\global\advance\footmarkcount@\@ne
  \footmarkform@{\number\footmarkcount@}\@sf}%
 \futurelet\next\next@}
\def\footnotetext{\relaxnext@
 \def\next@{\ifx[\next\let\next\nextii@\else
  \ifx"\next\let\next\nextiii@\else
  \let\next\nextiv@\fi\fi\next}%
 \def\nextii@[##1]##2{\makefootnote@{\footmarkform@{##1}}{##2}}%
 \def\nextiii@"##1"##2{\makefootnote@{##1}{##2}}%
 \def\nextiv@##1{\makefootnote@{\footmarkform@{\number\footmarkcount@}}{##1}}%
 \futurelet\next\next@}
\def\footnote{\let\@sf\empty\relaxnext@\ifhmode\edef
 \@sf{\spacefactor\the\spacefactor}\/\fi
 \def\next@{\ifx[\next\let\next\nextii@\else
  \ifx"\next\let\next\nextiii@\else
  \let\next\nextiv@\fi\fi\next}%
 \def\nextii@[##1]##2{\footnotemark[##1]\footnotetext[##1]{##2}}%
 \def\nextiii@"##1"##2{\footnotemark"##1"\footnotetext"##1"{##2}}%
 \def\nextiv@##1{\footnotemark\footnotetext{##1}}%
 \futurelet\next\next@}
\def\adjustfootnotemark#1{\advance\footmarkcount@#1\relax}
\let\topmatter\relax
\newbox\titlebox@
\setbox\titlebox@\vbox{}
\Invalid@\overlong
\def\overlong@{\def\next@{\ifx\next\overlong\def\filhss@
 {plus\@m\p@ minus\@m\p@}\def\next@\overlong{\nextii@}\else
 \def\filhss@{plus\@m\p@\relax}\let\next@\nextii@\fi\next@}}
\def\title{\relaxnext@
 \def\nextii@##1\endtitle{{\let\\=\cr
 \global\setbox\titlebox@\vbox{\tabskip\z@\filhss@
 \halign to\hsize{\tenpoint\bf\hfil\ignorespaces####\unskip\hfil\cr##1\cr}}}}%
 \overlong@
 \futurelet\next\next@}
\newif\ifauthor@
\newbox\authorbox@
\def\author{\relaxnext@
 \def\nextii@##1\endauthor{{\let\\=\cr
 \global\setbox\authorbox@\vbox{\tabskip\z@\filhss@
 \halign to\hsize{\tenpoint\smc\hfil\ignorespaces####\unskip\hfil\cr##1\cr
 }}}}\overlong@\global\author@true
 \futurelet\next\next@}
\newif\ifaffil@
\newbox\affilbox@
\def\affil{\relaxnext@
 \def\nextii@{\bgroup\let\\=\cr
 \global\setbox\affilbox@\vbox\bgroup\tabskip\z@\filhss@
 \halign to\hsize\bgroup\tenpoint\hfil\ignorespaces####\unskip\hfil\cr}%
 \overlong@
 \global\affil@true
 \futurelet\next\next@}
\def\endaffil{\cr\egroup\egroup\egroup}
\newcount\addresscount@
\addresscount@\@ne
\def\address#1{\expandafter\gdef\csname address\number\addresscount@
 \endcsname{\noindent\eightpoint\ignorespaces#1\par}\global
 \advance\addresscount@\@ne}
\newif\ifdate@
\def\date#1{\global\date@true\gdef\date@{\tenpoint\ignorespaces#1\unskip}}
\newif\ifthanks@
\def\thanks#1{\global\thanks@true\gdef\thanks@{\eightpoint\ignorespaces
 #1\unskip}}
\Invalid@\nofrills
\Invalid@\usualspace
\newif\ifnofrills@
\def\usualspace@#1{\ifnofrills@\def\usualspace{#1}\fi}
\def\nofrills@#1#2{\def\next@{\ifx\next\nofrills\nofrills@true\let#2\relax
 \def\next@\nofrills{\nextii@}\else\nofrills@false
 \def#2{#1}\let\next@\nextii@\fi\next@}}
\newif\ifkeywords@
\def\thekeywords@{}
\def\keywords{\relaxnext@\nofrills@{{\eightpoint\bf Key words:\enspace}\rm }%
\keywords@
 \def\nextii@##1{\def\thekeywords@{\usualspace@{{\it\enspace}}\noindent
  \eightpoint\keywords@\ignorespaces##1\par}}%
\global\keywords@true
\futurelet\next\next@}
\newif\ifsubjclass@
\def\thesubjclass@{}
\def\subjclass{\relaxnext@\nofrills@{{{\bf 1991 Mathematics subject
 classifications:\enspace}\rm }}\subjclass@
 \def\nextii@##1{\def\thesubjclass@{\usualspace@
  {{\rm\spacefactor2000 \space}}\noindent\eightpoint
  \subjclass@\ignorespaces##1\par}}%
 \global\subjclass@true
 \futurelet\next\next@}
\def\proclaim{\innerproclaim@}
\def\endproclaim{\innerendproclaim@}
\newif\ifabstract@
\def\theabstract@{}
\def\abstract{\relaxnext@\nofrills@{{\bf Abstract.\enspace}}\abstract@
 \long\def\nextii@##1{\long\gdef\theabstract@{\usualspace@
  {{\eightpoint\enspace}}\eightpoint\abstract@\ignorespaces##1\par}}%
 \global\abstract@true
 \futurelet\next\next@}
\def\pretitle{}
\def\preauthor{}
\def\preaffil{}
\def\predate{}
\def\preabstract{}
\def\prepaper{}
\def\endtopmatter{\hrule height\z@\vskip-\topskip
 \pretitle
 \vskip 26.666666 pt plus 13.333333 pt minus 13.333333 pt
 \unvbox\titlebox@
 \preauthor
 \ifauthor@\vskip 13.333333 pt plus 6.666666pt minus 3.333333 pt%
\unvbox\authorbox@\fi
 \preaffil
 \ifaffil@\vskip10\p@ plus5\p@ minus2\p@\unvbox\affilbox@\fi
 \predate
 \ifdate@\vskip6\p@ plus2\p@ minus\p@\hbox to\hsize{\hfil\date@\hfil}\fi
 \preabstract
 \ifthanks@\makefootnote@{}{\thanks@}\fi
 \ifabstract@\vskip 16.666666 pt plus 7%13.333333
 pt minus 7%13.333333
 pt
%  {\leftskip 26.666666 pt \rightskip 26.666666 pt
   {\eightpoint\indent  \theabstract@}\fi
 \ifsubjclass@\vskip 10%6.666666
 pt plus 4.333333 pt minus 4.333333 pt
   {\eightpoint\indent\thesubjclass@}\fi
 \ifkeywords@\vskip 10%6.666666
 pt plus 4.333333 pt minus 4.333333 pt
   {\eightpoint\indent\thekeywords@}\fi
   \prepaper
 \outer\def\proclaim{\innerproclaim@}%
 \outer\def\endproclaim{\innerendproclaim@}%
 \vskip 20 pt plus 13.333333 pt minus 6.666666 pt \tenpoint}
\newcount\addressnum@
\outer\def\enddocument{\nobreak\sfcode`\.=3000 \vskip12\p@ minus6\p@%
%\thekeywords@\thesubjclass@
\nobreak\vskip12\p@ minus6\p@\addressnum@\z@
 \loop\ifnum\addressnum@<\addresscount@\advance\addressnum@\@ne
 \csname address\number\addressnum@\endcsname\repeat
 \vfill\supereject\end}
\newbox\headingbox@
\outer\def\heading{\relaxnext@
 \def\nextii@{\bigbreak\bgroup\let\\=\cr
 \global\setbox\headingbox@\vbox\bgroup\tabskip\z@\filhss@
 \halign to\hsize\bgroup\tenpoint\smc\hfil\ignorespaces####\unskip\hfil\cr}%
 \overlong@
 \futurelet\next\next@}
\def\endheading{\cr\egroup\egroup\egroup\unvbox\headingbox@
 \nobreak\medskip}
\def\subheading{\relaxnext@\nofrills@{.\enspace}\subheading@
 \def\nextii@##1{\medbreak\indent{\usualspace@{{\bf\enspace}}%
  \tenpoint\bf\ignorespaces##1\unskip\subheading@}\ignorespaces}%
 \futurelet\next\next@}
\newif\ifproclaim@
\def\innerproclaim@{\relaxnext@\nofrills@{.\enspace}\proclaim@
 \def\nextii@##1{\message{(##1)}\medbreak\indent\def\next{8}%
  \ifx\pointsize@\next\uppercase
  {\usualspace@{{\rm\enspace}}\ignorespaces\rm##1\unskip\proclaim@}\else
  {\usualspace@{{\smc\enspace}}\smc\ignorespaces##1\unskip\proclaim@}\fi\sl
  \ifproclaim@\Err@{Previous \expandafter
 \eat@\string\\proclaim has no matching \expandafter
 \eat@\string\\endproclaim}\else\proclaim@true\fi\ignorespaces}%
 \futurelet\next\next@}
\def\innerendproclaim@{\proclaim@false\par\rm
 \ifdim\lastskip<\medskipamount\removelastskip\penalty55 \medskip\fi}
\def\demo{\relaxnext@\nofrills@{.\enspace}\demo@
 \def\nextii@##1{\par\ifdim\lastskip<\smallskipamount\removelastskip
  \smallskip\fi\indent{\usualspace@{{\sl\enspace}}%
  \sl\ignorespaces##1\unskip\demo@}\rm
  \ifproclaim@\Err@{Previous \expandafter
  \eat@\string\\proclaim had no matching \expandafter
  \eat@\string\\endproclaim}\fi\ignorespaces}%
 \futurelet\next\next@}
\def\enddemo{\par\smallskip}
\def\qed{\ifhmode\unskip\nobreak\fi\ifmmode\ifinner\else\hskip5\p@\fi\fi
 \hbox{\hskip5\p@\lower 1.5 pt\hbox{\vrule width .2 pt 
\vbox{\hrule width 4 pt height .2 pt \vskip 7.1 pt\hrule width 4 pt 
height .2 pt }\unskip\vrule width .2 pt}\hskip\p@}}
\def\cite#1{\relaxnext@
 \def\nextiii@##1,##2\end@{[{\bf##1},##2]}%
 \in@,{#1}\ifin@\def\next{\nextiii@#1\end@}\else
 \def\next{[{\bf#1}]}\fi\next}
\newcount\rostercount@
\newif\iffirstitem@
\newtoks\everypartoks@
\let\plainitem@\item
\def\par@{\everypartoks@=\expandafter{\the\everypar}\everypar{}}
\def\roster{\edef\leftskip@{\leftskip\the\leftskip}\relaxnext@
 \rostercount@\z@\def\item{\futurelet\next\rosteritem@}%
 \def\next@{\ifx\next\runinitem\let\next\nextii@\else
  \let\next\nextiii@\fi\next}%
 \def\nextii@\runinitem{\unskip
  \def\next@{\ifx\next[\let\next\nextii@\else
   \ifx\next"\let\next\nextiii@\else\let\next\nextiv@\fi\fi\next}%
  \def\nextii@[####1]{\rostercount@####1\relax
   \enspace{\rm(\number\rostercount@)}~\ignorespaces}%
  \def\nextiii@"####1"{\enspace{\rm####1}~\ignorespaces}%
  \def\nextiv@{\enspace{\rm(1)}\rostercount@\@ne~}%
  \par@\firstitem@false
  \futurelet\next\next@}%
 \def\nextiii@{\par\par@\penalty\@m\smallskip 
  \firstitem@true}%
 \futurelet\next\next@}
\def\rosteritem@{\iffirstitem@\firstitem@false\else\par\fi
 \leftskip3\parindent\noindent
 \def\next@[##1]{\rostercount@##1\relax
  \llap{\hbox to2.5\parindent{\hss\rm(\romannumeral\rostercount@)}\hskip
  .5\parindent}\ignorespaces}%
 \def\nextii@"##1"{%
  \llap{\hbox to2.5\parindent{\hss\rm##1}\hskip.5\parindent}\ignorespaces}%
 \def\nextiii@{\advance\rostercount@\@ne
  \llap{\hbox to2.5\parindent{\hss\rm(\romannumeral\rostercount@)}\hskip
  .5\parindent}}%
 \ifx\next[\let\next\next@\else\ifx\next"\let\next\nextii@\else
 \let\next\nextiii@\fi\fi\next}
\def\therosteritem#1{{\rm(\ignorespaces#1\unskip)}}
\newif\ifnextRunin@
\def\endroster{\relaxnext@\par\leftskip@
 \penalty-50 \vskip-\parskip\smallskip
 \def\next@{\ifx\next\Runinitem\let\next@\relax
  \else\nextRunin@false\let\item\plainitem@\ifx\next\par
  \def\next@\par{\everypar=\expandafter{\the\everypartoks@}}%
  \else\def\next@{\noindent\everypar=\expandafter{\the\everypartoks@}}%
  \fi\fi\next@}%
 \futurelet\next\next@}
\newcount\rosterhangafter@
\def\Runinitem#1\roster\runinitem{\relaxnext@\rostercount@\z@
 \def\item{\futurelet\next\rosteritem@}%
 \def\runinitem@{#1}%
 \def\next@{\ifx\next[\let\next\nextii@\else\ifx\next"\let\next\nextiii@
  \else\let\next\nextiv@\fi\fi\next}%
 \def\nextii@[##1]{\rostercount@##1\relax\def\item@{{\rm(\romannumeral
  \rostercount@)}}\nextv@}%
 \def\nextiii@"##1"{\def\item@{{\rm##1}}\nextv@}%
 \def\nextiv@{\advance\rostercount@\@ne\def\item@{{\rm(\romannumeral
  \rostercount@)}}\nextv@}%
 \def\nextv@{\setbox\z@\vbox
  {\ifnextRunin@\noindent\fi
  \runinitem@\unskip\enspace\item@~\par
  \global\rosterhangafter@\prevgraf}%
  \firstitem@false\ifnextRunin@\else\par\fi
  \hangafter\rosterhangafter@\hangindent3\parindent
  \ifnextRunin@\noindent\fi\runinitem@\unskip\enspace
  \item@~\ifnextRunin@\else\par@\fi\nextRunin@true\ignorespaces}%
 \futurelet\next\next@}
\outer\def\Refs{\relaxnext@\def\refskip@{\hskip\@ne sp\hskip\m@ne sp}%
 \def\next@{\ifx\next\nofrills\def\next@\nofrills{\nextii@}\else
  \def\next@{\nextii@{REFERENCES}}\fi\next@}%
 \def\nextii@##1{\bigbreak\hbox to\hsize{\hfil\eightpoint
  \rm\ignorespaces##1\unskip\hfil}\nobreak
  \bigskip\eightpoint\sfcode`.=\@m}%
 \futurelet\next\next@}
\outer\def\Lit{\relaxnext@\def\refskip@{\hskip\@ne sp\hskip\m@ne sp}%
 \def\next@{\ifx\next\nofrills\def\next@\nofrills{\nextii@}\else
  \def\next@{\nextii@{LITERATURA}}\fi\next@}%
 \def\nextii@##1{\bigbreak\hbox to\hsize{\hfil\eightpoint
  \rm\ignorespaces##1\unskip\hfil}\nobreak
  \bigskip\eightpoint\sfcode`.=\@m}%
 \futurelet\next\next@}
\newbox\nobox@        \newbox\keybox@        \newbox\bybox@
\newbox\bysamebox@    \newbox\paperbox@      \newbox\paperinfobox@
\newbox\jourbox@      \newbox\volbox@        \newbox\issuebox@
\newbox\yrbox@                               \newbox\pagesbox@
\newbox\bookbox@
\newbox\bookinfobox@  \newbox\publbox@       \newbox\publaddrbox@
\newbox\finalinfobox@
\newif\ifno@          \newif\ifkey@          \newif\ifby@ \newif\ifmanyby@
\newif\ifbysame@      \newif\ifpaper@        \newif\ifpaperinfo@
\newif\ifjour@        \newif\ifvol@          \newif\ifissue@
\newif\ifyr@ \newif\iftoappear@              \newif\ifpages@ \newif\ifpage@
\newif\ifbook@ \newif\ifinbook@
\newif\ifbookinfo@    \newif\ifpubl@         \newif\ifpubladdr@
\newif\iffinalinfo@   \newif\ifafterbook@
\newif\iffirstref@    \newif\iflastref@      \newif\ifprevjour@
\newif\ifprevbook@    \newif\ifprevinbook@   \newif\ifnojourinfo@
\newdimen\maxbysamerule@
\maxbysamerule@1in
\def\ref@{\global\no@false\global\key@false\global\by@false
 \global\bysame@false\global\paper@false\global\paperinfo@false
 \global\jour@false\global\vol@false\global\issue@false
 \global\yr@false\global\toappear@false\global\pages@false\global\page@false
 \global\book@false\global\inbook@false
 \global\bookinfo@false\global\publ@false\global\publaddr@false
 \global\finalinfo@false
 \bgroup\ignorespaces}
\Invalid@\moreref
\outer\def\ref{\begingroup
 \noindent\hangindent20\p@\hangafter\@ne\firstref@true
 \lastref@false\def\moreref{\egroup\endref@\global\firstref@false\ref@}\ref@}
\def\refdef@#1#2{\def#1{\egroup
 \csname\expandafter\eat@\string#1@true\endcsname
 \expandafter\setbox
 \csname\expandafter\eat@\string#1box@\endcsname\hbox\bgroup#2}}
\refdef@\no\relax \refdef@\key\relax
\def\manyby{\egroup\global\manyby@true\by@true\setbox\bybox@\hbox\bgroup\smc}
\def\by{\egroup\by@true\bysame@false\global\manyby@false
 \setbox\bybox@\hbox\bgroup\rm}
\def\bysame{\egroup\bysame@true\bgroup}
\refdef@\paper\sl
\refdef@\paperinfo\relax
\def\jour{\egroup\jour@true\prevjour@true\setbox
 \jourbox@\hbox\bgroup}
\refdef@\vol\bf
\refdef@\issue\relax \refdef@\yr\relax
\def\toappear{\egroup\toappear@true\bgroup}
\refdef@\pages\relax
\def\page{\egroup\page@true\setbox\pagesbox@\hbox\bgroup}
\refdef@\book\relax
\def\inbook{\egroup\inbook@true\previnbook@true\setbox
 \bookbox@\hbox\bgroup}
\refdef@\bookinfo\relax
\refdef@\publ\relax
\refdef@\publaddr\relax
\refdef@\finalinfo\relax
\def\setpunct@{\def\prepunct@{\ifnum\lastpenalty<0
 \edef\penalty@{\penalty\the\lastpenalty}\unpenalty,\ifafterbook@''\fi
  \penalty@\relax\space\else
 \ifdim\lastskip=\@ne sp\unskip\unskip
 \edef\penalty@{\penalty\the\lastpenalty}\unpenalty,\ifafterbook@''\fi
  \penalty@\relax\space
 \else,\ifafterbook@''\fi\space\fi\fi\afterbook@false}}
\def\ppunbox@#1{\prepunct@\unhbox#1\unskip}
\def\endref@{\let\prepunct@\relax
 \iffirstref@
  \ifno@\hbox to 22.222222 pt {\hss[\unhbox\nobox@\unskip]\kern 8.5 pt }\else
  \ifkey@\hbox to 22.222222 pt {\hss\unhbox\keybox@\unskip\kern 8.5 pt} 
  \else \hbox to 8.5 pt{}\fi\fi
  \ifmanyby@
   \ifby@\hbox{\unhcopy\bybox@\unskip}\setpunct@
  \global\setbox\bysamebox@\hbox{\unhcopy\bybox@\unskip}\else
  \ifbysame@\ifdim\wd\bysamebox@>\maxbysamerule@
    \hbox to\maxbysamerule@{\leaders\hrule\hfill}\else
    \hbox to \wd\bysamebox@{\leaders\hrule\hfill}\fi\setpunct@\fi
   \fi
  \else
  \ifby@\unhcopy\bybox@\unskip\setpunct@\fi\fi
 \fi
 \ifpaper@\ppunbox@\paperbox@\setpunct@\fi
 \ifpaperinfo@\ppunbox@\paperinfobox@\setpunct@\fi
 \ifjour@\ppunbox@\jourbox@\setpunct@
   \ifvol@\ppunbox@\volbox@\unskip\setpunct@\fi
   \ifissue@\ \unhbox\issuebox@\unskip\setpunct@\fi
   \ifyr@\ (\unhbox\yrbox@\unskip)\setpunct@\fi
   \iftoappear@\ (to appear)\setpunct@\fi
   \ifpages@\prepunct@ pp.\ \unhbox\pagesbox@\unskip\setpunct@\fi
   \ifpage@\prepunct@ p.\ \unhbox\pagesbox@\unskip\setpunct@\fi
 \else
  \ifprevjour@\unskip\nojourinfo@false
   \ifvol@\else\ifissue@\else\ifyr@\else\nojourinfo@true\fi\fi\fi
   \ifnojourinfo@\else,\fi
   \ifvol@\ppunbox@\volbox@\unskip\setpunct@\fi
   \ifissue@\ \unhbox\issuebox@\unskip\setpunct@\fi
   \ifyr@\ (\unhbox\yrbox@\unskip)\setpunct@\fi
   \iftoappear@\ (to appear)\setpunct@\fi
   \ifpages@\prepunct@  pp.\ \unhbox\pagesbox@\unskip\setpunct@\fi
   \ifpage@\prepunct@ p.\ \unhbox\pagesbox@\unskip\setpunct@\fi
  \fi
 \fi
 \ifbook@\prepunct@``\unhbox\bookbox@\unskip\afterbook@true\setpunct@\fi
 \ifinbook@\prepunct@\unskip\ in ``\unhbox\bookbox@\unskip\afterbook@true
  \setpunct@\global\book@true\fi
 \ifbookinfo@\ppunbox@\bookinfobox@\setpunct@\fi
 \ifpubl@\ppunbox@\publbox@\setpunct@\fi
 \ifpubladdr@\ppunbox@\publaddrbox@\setpunct@\fi
 \ifbook@
  \ifyr@\prepunct@\unhbox\yrbox@\unskip\setpunct@\fi
  \iftoappear@\ifafterbook@''\fi\ (to appear)\afterbook@false
   \setpunct@\fi
  \ifpages@\prepunct@ pp.\ \unhbox\pagesbox@\unskip\setpunct@\fi
  \ifpage@\prepunct@ p.\ \unhbox\pagesbox@\unskip\setpunct@\fi
 \else
  \ifprevinbook@\unskip
   \ifyr@\prepunct@\unhbox\yrbox@\unskip\setpunct@\fi
   \iftoappear@\ (to appear)\setpunct@\fi
   \ifpages@\prepunct@ pp.\ \unhbox\pagesbox@\unskip\setpunct@\fi
   \ifpage@\prepunct@ p.\ \unhbox\pagesbox@\unskip\setpunct@\fi
  \fi
 \fi
\iffinalinfo@.\ifafterbook@''\fi\afterbook@false
\spacefactor3000\relax\space\unhbox\finalinfobox@\else
 \iflastref@.\ifafterbook@''\fi\afterbook@false\else;\ifafterbook@''\fi
  \afterbook@false\space\fi
\fi}
\def\endref{\egroup\global\lastref@true\endref@\global\prevjour@false\global
 \previnbook@false\par\endgroup}
\newif\iflogo@
\def\nologo{\logo@false}
\def\logo{\logo@true}
\logo@false
\newif\ifdraft@
\def\nodraft{\draft@false}
\def\draft{\draft@true}
\draft@false
\output={\output@}
\def\output@{% 
\ifdraft@  \shipout\vbox{\vbox to\vsize
  {\boxmaxdepth\maxdepth\pagecontents}\baselineskip2pc
\hbox to\hsize{\relaxnext@\hphantom{\eightpoint\jobname\quad
 \number\month/\number\day/\number\year\quad DRAFT}  \hfil
  \tenpoint\number\pageno\hfil \eightpoint\jobname\quad
 \number\month/\number\day/\number\year\quad DRAFT
 }}\else\ifnum\pageno=\@ne\shipout\vbox{\vbox to\vsize
  {\boxmaxdepth\maxdepth\pagecontents}\baselineskip2pc
 \iflogo@\hbox to\hsize{\hfil\eightpoint Typeset by \AmSTeX}\fi}\else
 \shipout\vbox{\vbox to\vsize
  {\boxmaxdepth\maxdepth\pagecontents}\baselineskip2pc
 \hbox to\hsize{\hfil\tenpoint\number\pageno\hfil}}%
 \fi\fi
  \global\advance\pageno\@ne
 \ifnum\outputpenalty>-\@MM\else\dosupereject\fi}
 \def\footertext{{\hbox to\hsize{\hfil\tenpoint\number\pageno\hfil}}}
%\def\draft{%
\def\footertext{\hbox to\hsize{\relaxnext@\hphantom{\eightpoint
\jobname\quad
  \number\month/\number\day/\number\year\quad DRAFT}\hfil
  \tenpoint\number\pageno\hfil
  \eightpoint\jobname\quad\number\month/\number\day/\number\year\quad DRAFT}}
%}
\def\footnoterule{\vskip-3\p@\hrule width 2truein \vskip 2.6\p@}
\def\m@g{\mag\count@
  \hsize 6.5 true in\vsize 9.0 true in\dimen\footins 8 true in%
\captionwidth@\hsize
  \advance\captionwidth@-1.5 true in
}
\tenpoint
\def\marginal#1{\strut\setbox0=%
      \vtop{\hsize=%20mm
17.5mm\sevenrm\parindent=0pt\baselineskip=8pt
             \raggedright\rightskip=1em plus 2em\hfuzz=.5em\tolerance=9000
             \overfullrule=\z@
             #1}%
      \dimen0=\ht0
      \advance\dimen0 by \dp\strutbox
      \ht0=0pt\dp0=\dimen0
      \vadjust{\kern-\dimen0\moveleft\wd0\box0}%
      \ignorespaces}
\def\nomarginals{\def\marginal##1{\ignorespaces}}
\catcode`\@=\active
\def\styname{m}\def\styversion{1.0}
\pageno=1
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\input statems
%\baselineskip=16pt
\NoBlackBoxes
%\draft
\redefine\E{\operatorname{E}}
\redefine\P{\operatorname{Prob}}
\redefine\Var{\operatorname{Var}}
\def\sums{\operatornamewithlimits{\sum\sum}}
%%
\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})}
%%
\let\oldqed=\qed
\redefine\qed{\oldqed{\ifdim\lastskip<\medskipamount
                        \removelastskip\penalty-10\medskip\fi}}
%%
\redefine\:{\colon}
\def\cond{\,\big|\,}
\redefine\epsilon{\varepsilon}
\def\ykcomm[#1]{[{\it yk\/}: {\sl \#1\/}]}
\redefine\db#1#2{\dsize\binom{#1}{#2}}
\redefine\df#1#2{\dsize\frac{#1}{#2}}
\define\deffont{\it}
\define\){\right)}                    
\define\]{\right]}
\define\({\left(}
\define\[{\left[}
\define\lb{\left\{}
\define\rb{\right\}}
\define\ov{\overrightarrow}
%\redefine\i{\infty}
\redefine\a{\alpha}
\define\al{\alpha}
\redefine\b{\beta}
\redefine\d{\delta}
\redefine\hd{\hat\delta}
\redefine\td{\tilde\delta}
\redefine\bd{\bar\delta}
\redefine\D{\Delta}
\redefine\ep{\epsilon}
\define\ue{\underline{\ep}}
\redefine\e{\text{\rm e}}
\define\g{\gamma}
\define\G{\Gamma}
\redefine\la{\lambda}
\redefine\La{\Lambda}
\redefine\Th{\Theta}
\define\tPi{\tilde\Pi}
\redefine\k{\xi}
\redefine\K{\Xi}
\redefine\th{\theta}
\redefine\s{\sigma}
\redefine\o{\omega}
\redefine\li{\lim_{n\to\infty}}
\define\bE{\bar E}
\redefine\an{\mathop{\longrightarrow}\limits_{n\to\infty}}
\define\x{\bold x}
\define\Z{Z}
\define\ssh#1{\subheading{%\hskip-1truecm 
#1}}
\define\N{\Bbb N}
\define\ff{\Cal F}
\define\CC{\Cal C}
\define\J{\Cal J}
\define\cF{\Cal F}
\define\cS{\Cal S}
\define\cB{\Cal B}
\define\NN{\text{{\rm I\kern-.22em N}}}
%%
\def\Bi{\text{\rm Bi}}
\def\G{{\Cal G}}
\def\tcG{{\tilde\G}}
\def\tG{{\tilde G}}
\def\cR{{\Cal R}}
\def\tcR{{\tilde\cR}}
\def\tR{\tilde R}
\def\cF{{\Cal F}}
\def\bH{{\bf H}}
\def\bm{{\bf m}}
\def\bl{{\bf l}}
\def\ghat{{\hat g}}
\let\phi=\varphi
\def\hG{\hat G}
\def\hV{\hat V}
\def\hX{\hat X}
\def\hY{\hat Y}
\def\hU{\hat U}
\def\hW{\hat W}
\redefine\sb{\subseteq}
\define\Vb{\bar V}
\define\hR{\hat R}
\define\pl{\oplus}
\define\mn{\ominus}
\define\X{\hat X}
\define\onee{1\kern-2.6pt I}
\define\one{\operatorname{\onee}}
\define\Cov{\operatorname{Cov}}
\define\ble{b_{\ge}}
\redefine\subheading#1{\bigskip\centerline{\smc #1}\medskip}
\define\rbr#1{r(#1)}
\define\sbr#1{s(#1)}
\define\tbr#1{t(#1)}
\define\umax{u_{\text{\rm max}}}
\define\ddd{\dag}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% definitions of theorem/lemma labels
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcount\statemno\statemno=1
\define\newstatemno{\advance\statemno by1}
\define\statementlabel{\number\statemno} %new command
%
% sec0
%
\edef\MainThmRM   
{\statementlabel}\newstatemno
\edef\MainThmRp    
{\statementlabel}\newstatemno
\edef\SparseCor
{\statementlabel}\newstatemno
%
% sec2
%
\edef\SparseSz
{\statementlabel}\newstatemno
\edef\MultiSSz
{\statementlabel}\newstatemno
\edef\FactA
{\statementlabel}\newstatemno
\edef\FactB
{\statementlabel}\newstatemno
%
% sec3
%
\edef\RSzThm
{\statementlabel}\newstatemno
\edef\SparseRSz
{\statementlabel}\newstatemno
\edef\FlowerLemma
{\statementlabel}\newstatemno
%
% sec4
%
\edef\IndSubgr
{\statementlabel}\newstatemno
%
% sec5
%
\edef\PairInter
{\statementlabel}\newstatemno
\edef\UnifCond
{\statementlabel}\newstatemno
%
% sec6
%
\edef\DiffGr
{\statementlabel}\newstatemno
\edef\FactC
{\statementlabel}\newstatemno
%
% sec7
%
\edef\FactD
{\statementlabel}\newstatemno
\edef\FactE
{\statementlabel}\newstatemno
\edef\MainLemmaA
{\statementlabel}\newstatemno
\edef\MainLemmaB
{\statementlabel}\newstatemno
\vfil\eject
\pageno=1
%%
\topmatter
\title
ARITHMETIC PROGRESSIONS OF LENGTH THREE \\
IN SUBSETS OF A RANDOM SET
\endtitle
\author YOSHIHARU KOHAYAKAWA\footnote"\dag"{\ 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.  Research
  partially supported by FAPESP (Proc.~93/0603--1) and by CNPq
  (Proc.~300334/93--1 and ProTeM-CC-II Project ProComb).}, 
TOMASZ \L UCZAK\footnote"\ddag"{\ Department of Mathematics and
  Computer Science, Emory University, Atlanta, Georgia 30322.  On
  leave from Mathematical Institute of the Polish Academy of Sciences,
  and Adam Mickiewicz University, Pozna\'n, Poland.}
  % Research partially supported by~KBN grant~2~1087~91~01.}
and VOJT\v ECH R\"ODL\footnote"*"{\ Department of Mathematics and
  Computer Science, Emory University, Atlanta, Georgia 30322.
  Research partially supported by NSF grant DMS--9401559.}
\endauthor
\abstract{For integers~$1\leq M\leq n$, let~$\cR(n,M)$ denote the
  uniform probability space which consists of all the $M$-element
  subsets of~$[n]=\{0,1,\dots,n-1\}$.  It is shown that for every
  $\al>0$ there exists a constant~$C$ such that if $M=M(n)\ge C\sqrt
  n$ then, with probability tending to~$1$ as $n\to\infty$, the random
  set~$R\in{\cR(n,M)}$ has the property that any subset of~$R$
  with at least $\al|R|$ elements contains a $3$-term arithmetic
  progression.  In particular, this result implies that for every
  $\al>0$ there exist `sparse' sets~$S\sb [n]$ with the property that
  every subset of~$S$ with at least~$\al|S|$ elements contains
  an arithmetic progression of length three.} 
\keywords{Szemer\'edi's
  theorem, arithmetic progressions, combinatorial number theory,
  regularity lemma, random sets of integers}
\subjclass{11B25, %``Arithmetic progressions''
           05D99, %05D++ is ``Extremal Combinatorics''; 05D99 is
                  %``None of the above, but in this section''
           11B05, %11B++ is ``Sequences and sets''; and 11B05 is 
                  %``Density, gaps, topology''
           11K99  %11K++ is
                  %``Probabilistic theory: distribution modulo~$\ell$;
                  %metric theory of algorithms''; 
                  %11K99 is ``None of the above, but in this section''
           }
\endtopmatter

\document

\subheading{\S0. Introduction} 

In~1936 Erd\H os and Tur\'an~[ET~36] asked whether  for every
natural number~$k$ and every positive constant~$\alpha$, every
subset~$A$ of~$[n]=\{0,1,\dots,n-1\}$ with at least~$\alpha n$
elements contains a $k$-term arithmetic progression provided~$n$ is
sufficiently large with respect to~$\alpha$ and~$k$. This conjecture
was resolved by Roth~[Ro~53] for~$k=3$, whereas for general~$k$ it
 was settled in the affirmative by the outstanding theorem
of Szemer\'edi~[Sz~75]. A few years after Szemer\'edi's paper was
published, an entirely different proof of this result, based on
ergodic theory, was given by Furstenberg~[Fu~77]. Since then, the main
open problem concerning the original question of Erd\H os and
Tur\'an has been to find better lower bounds for the size of~$A$ that
guarantee the existence of arithmetic progressions of length~$k$
in~$A$.  Unfortunately, not much has been accomplished for~$k\ge 4$.
The explicit estimates that follow from Szemer\'edi's original proof
are very poor and Furstenberg's approach does not provide such bounds
at all.  The case when~$k=3$ is much better understood. Roth's
original argument implies that it is enough to assume that~$|A|\ge
n/\log\log n$ and the best lower bound to date has been given
independently by Heath-Brown and Szemer\'edi (see~[H-B~87]), who
showed that for some absolute constant $c>0$ every subset of~$[n]$
with at least~$n/(\log n)^c$ elements contains an arithmetic
progression of length three, provided~$n$ is sufficiently large.

In this paper we approach a related problem. Namely, here we are
interested in the existence of a `small' and `sparse' set~$R\sb [n]$
with the property that every subset~$A\sb 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 be so
that it reflects 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. Our main result here confirms this appealing,
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\subseteq[n]$, let us write~$R\to_\alpha3$ if any~$A\subseteq R$
with~$|A|\geq\alpha|R|$ contains a $3$-term arithmetic progression.
Our main result may then be stated as follows.

\proclaim{Theorem~\MainThmRM} For every constant~$0<\a\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$.
\endproclaim

 From Theorem~{\MainThmRM}, it is easy to deduce the following
analogous result for the random sets~$R_p\subseteq[n]$ ($0\leq
p=p(n)\leq1$) whose elements are chosen from~$[n]$ independently with
probability~$p$. Thus, if we write~$\cR(n,p)$ for the probability
space of such~$R_p$, then for a given set~$R\subseteq[n]$ the
probability that~$R_p=R$ is~$p^{|R|}(1-p)^{n-|R|}$.

\proclaim{Theorem~\MainThmRp} For every constant~$0<\a\leq1$, there
exists a constant~$C=C(\alpha)$ such that if~$C/\sqrt n\leq
p=p(n)\leq1$ then the probability that~$R_p\in\cR(n,M)$
satisfies~$R_p\to_\alpha3$ tends to~$1$ as~$n\to\infty$.\qed
\endproclaim

Note that Theorems~{\MainThmRM} and~{\MainThmRp} are, 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 
%%%
{\it not\/}
hold for~$\alpha=1-2\epsilon^2$. Clearly, a similar phenomenon happens
%%%
for~$R_p$ with~$p=p(n)=\epsilon/\sqrt n$.

Our results above immediately imply 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.

\proclaim{Corollary~\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 are constants~$C$ and~$N$ such that for every~$n\ge N$ there
exists~$S\sb[n]$ satisfying~$S\to_\alpha3$ for which the following
three conditions hold.  
\roster
\item"(i)" For every~$k\geq0$ and~$\ell\ge1$ the
  set~$\{k,k+\ell,\dots,k+s\ell\}$ contains at most three elements
  of~$S$, and therefore, in particular, $S$~contains no $4$-term
  arithmetic progression. 
\item"(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"(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$.
\endroster
\endproclaim

In words, conditions~(i) and~(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~(iii) is more combinatorial in nature, and says that the
$3$-term arithmetic progressions contained in~$S$ locally form 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~{\SparseCor} was proved in~[R\"o~90], 
thereby settling a problem raised by Spencer~[Sp~75]. 
Let~$k$, $g\geq3$ be fixed integers
and~$0<\alpha\leq1$ be a fixed real. Theorem~4.3 in~[R\"o~90] 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\subseteq[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~[GN~86],
Ne\v set\v ril and R\"odl~[NR~87] and Pr\"omel and
Voigt~[PV~88]. Note that Corollary~{\SparseCor} strengthens the above
result of~[R\"o~90] in the case in which~$k=3$.

The proof of Theorem~{\MainThmRM} is unfortunately quite long.  In the
next section we describe our general approach, stressing the main
ideas involved and ignoring several quite technical parts. We hope
that the outline of our method presented there will be of some use in
following the actual proof. The organisation of the paper is also
discussed in the next section. 

\subheading{\S1. Outline of the Method of Proof} 

The main lemma in the proof of Theorem~{\MainThmRM} is
Lemma~{\MainLemmaB}. In essence, what this lemma says is quite simple.
Assume~$C\sqrt n\leq M'=M'(n)\leq n$ for some large~$C>0$.
Disregarding some technicalities, Lemma~{\MainLemmaB} states the
following: if we condition on our set~$R_{M'}\in\cR(n,M')$ satisfying
a certain `sparseness' condition, the probability that~$R_{M'}$ {\it
  fails\/} to contain an arithmetic progression of length three is at
most~$\exp\{-cM'\}$, where we may make~$c$ arbitrarily large by
picking~$C$ appropriately large.

Theorem~{\MainThmRM} is shown to follow from Lemma~{\MainLemmaB} in
two steps.  Suppose~$C$ is a large constant with respect to a given 
fixed~$\alpha>0$ and~$M=M(n)\leq\alpha^{-1}M'$.  We aim at showing
that~$R_M\to_\alpha3$ with probability approaching~$1$.  Our first
step consists of a quick calculation based on Lemma~{\MainLemmaB} to
deduce that a typical random set~$R_M\in\cR(n,M)$ will {\it not\/}
contain a `sparse' $M'$-element subset~$R'$ that is free of $3$-term
arithmetic progressions. Our second step is then to show that our
`sparseness' condition is weak enough for {\it every\/} $M'$-element
subset~$R'$ of a typical~$R_M\in\cR(n,M)$ to be sparse.  Hence
Theorem~{\MainThmRM} follows.

%%% I have changed it a little bit
%%% The crucial ingredient of the argument above is Lemma~{\MainLemmaB},
Thus, all our efforts go into proving Lemma~{\MainLemmaB}. 
An important tool in the proof will be a version of
Szemer\'edi's regularity lemma~[Sz~78].
As is well known, this is an important graph theoretical component of
Szemer\'edi's proof of his theorem on arithmetic progressions. It
turns out that it is most convenient to phrase our arguments below in
terms of graphs as well.  Following an idea of Ruzsa and
Szemer\'edi~[RSz~78] (see also Erd\H os, Frankl and R\"odl~[EFR~86] or
Graham and R\"odl~[GR~87]), for every subset~$R'$ of~$[n]$ we
construct a graph~$G(n,R')$ that, roughly speaking, has the property
that it contains a triangle (more precisely, a `spontaneous' triangle)
if and only if~$R'$ contains a $3$-term arithmetic progression (more
precisely, an `arithmetic triple').  Lemma~{\MainLemmaB} is in fact
stated in terms of sparse graphs and spontaneous triangles, and it
asserts that sparse graphs free of such triangles are extremely rare.

Unfortunately, the proof of Lemma~{\MainLemmaB} is quite complex, and
we shall not attempt to give a non-technical 
%%%
outline of it here.
Probably any such sketch would fail to be of much help. 
%%%
 Nonetheless, we remark that the argument below is divided
into several steps, which are, to a large extent, independent from one
another, and perhaps of some interest in their own right.
 
The organization of our paper is as follows. In~\S2 we
introduce the notions of regularity, uniformity and sparseness of
graphs, and state a version of Szemer\'edi's regularity lemma for
suitably sparse graphs together with a few related results.  We
start~\S3 with an analogue of a theorem of Ruzsa and
Szemer\'edi~[RSz~78] for sparse graphs (cf.~Theorem~{\RSzThm} and
Lemma~{\SparseRSz}), and then give an important but rather technical
lemma, Lemma~{\FlowerLemma}, concerning the existence of certain
structures we call `flowers' in edge-coloured sparse graphs.  It is in
proving Lemma~{\FlowerLemma} that we shall make use of Szemer\'edi's
regularity lemma in the form given in~\S2.

One of the main probabilistic ingredients in the proof of
Lemma~{\MainLemmaB} is given in~\S4.  Roughly speaking, we show in
Lemma~{\IndSubgr} that a random induced subgraph of a bipartite
uniform graph contains with very large probability a fair number of
edges.  In~\S5 we give a simple sufficient condition for a regular
bipartite graph to be uniform.  In~\S6 we relate our graph theoretical
results of the previous sections to subsets of~$[n]$: we define the
`difference graph'~$G_R=G_R(n)$ for any given subset~$R$ of~$[n]$ and,
using a result from~\S5, show that if~$R$ is a random set of suitably
large expected size, then its difference graph~$G_R$ is uniform with
large probability. Finally, the statement and proof of our main lemma,
Lemma~{\MainLemmaB}, and the proof of Theorem~{\MainThmRM} are given
in~\S7, together with a sketch of the proof of Corollary~{\SparseCor}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%We deduce from results of~\S5 that for a random set~$R$ the
%graph~$G(n,R)$ is, with large probability, uniform, and use results of
%\S2 and~\S4 to show that if a random subset $R$ is large and $G(n,R)$
%is sparse the probability that $R$ contains no arithmetic progressions
%of length three tends to~0 exponentially fast as the size of $R$
%grows. As we have already observed, from this fact and Szemeredi's
%regularity lemma Theorem~{\MainThmRM} will follow.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subheading{\S2. Uniform Graphs and Szemer\'edi's Lemma} 

Let~$G$ be a graph with vertex set~$V=V(G)$ and edge set~$E(G)$.
Write~$|G|=|V(G)|=n$ for the order of $G$, and~$e(G)=|E(G)|$ for its
size~$|E(G)|$. Furthermore, let ~$U$, $W\sb V$ be a pair of disjoint,
non-empty subsets of $G$, let~$E_G(U,W)$ denote the set of edges
of~$G$ that have one end-vertex in~$U$ and the other in~$W$, and
set~$e(U,W)=e_G(U,W)=|E_G(U,W)|$.  The {\deffont density\/}~$d_G(U,W)$
of the pair~$(U,W)$ is defined by
$$
d_G(U,W)={e_G(U,W)\over |U||W|}\Big / {e(G)\over n^2}\;.
$$
For~$0<\epsilon\leq1$, we say that the pair~$(U,W)$ is
{\deffont$(\epsilon,G)$-regular\/}, or simply
{\deffont$\epsilon$-regular\/}, if for all~$U'\subseteq U$,
$W'\subseteq W$ with~$|U'|\geq\epsilon|U|$ and~$|W'|\geq\epsilon|W|$
we have
$$
\big|d_G(U,W)-d_G(U',W')\big|\leq\epsilon\;.
$$ 
We say that an $\ell$-partite graph~$G$ is
{\deffont$(\ell,\ep)$-uniform\/}, or just {$\ep$-uniform\/}, if all  
the~$\ell\choose2$ pairs of distinct vertex classes of the
$\ell$-partition of~$G$ are $\ep$-regular.

We say that a partition~$\Pi=(V^i)_0^k$ of the vertex set~$V=V(G)$
of~$G$ is {\deffont$(\epsilon,k)$-equitable\/} if~$|V^0|\leq\epsilon
n$ and~$|V^1|=\ldots=|V^k|$. We refer to~$V^0$ as the {\deffont 
  exceptional\/} class of~$\Pi$. We say that the $(\ep,k)$-equitable 
partition~$\Pi$ is a {\deffont subpartition\/} of a partition
$\Pi'=(W^j)_0^s$ of~$V$ if each~$V^i$ with~$1\le i\le k$, that is
every {\it non-exceptional\/} class of~$\Pi$, is contained in some
member of the partition~$\Pi'$.   
%%%%%%%%%%%%
%When the value of~$\epsilon$ is not
%relevant, we refer to an $(\epsilon,k)$-equitable partition as a
%{\deffont$k$-equitable\/} partition. Similarly, $\Pi$ is an {\deffont
%equitable\/} partition of~$V$ if it is a $k$-equitable partition for
%some~$k$.
%%%%%%%%%
For~$\Pi$ to be a subpartition of~$\Pi'$ in the case in which~$\Pi'$
is an equitable partition as well, we require every non-exceptional
class of~$\Pi$ to be contained in some {\it non-exceptional\/} class
of~$\Pi'$.  We say that an $(\epsilon,k)$-equitable
partition~$\Pi=(V^i)_0^k$ is {\deffont$(\epsilon,k;G)$-regular\/}, or
simply {\deffont$(\epsilon,G)$-regular\/}, if at
most~$\epsilon{k\choose2}$ pairs~$(V^i,V^j)$ with~$1\le i<j\le k$
are not $(\epsilon,G)$-regular.

Finally, for a given~$b>2$ and~$0<\eta\leq1$, we say that~$G$ is
{\deffont$(b,\eta)$-sparse\/} if, for every disjoint pair of sets~$U$,
$W\sb V$ such that $|U|$, $|W|\ge\eta n$, we have $d_G(U,W)\le b$.
Thus, roughly speaking, a graph is $(b,\eta)$-sparse if all of its
large induced subgraphs are not much denser that the graph itself.  We
can now state our extension of Szemer\'edi's lemma for
$(b,\eta)$-sparse graphs.

\proclaim {Lemma~\SparseSz} For any given~$\epsilon>0$,
$b>2$, $k_0\geq1$ and~$s\geq1$, there are
constants~$\eta=\eta(\epsilon,b,k_0,s)>0$
and~$K_0=K_0(\epsilon,b,k_0,s)\geq k_0$ that depend only
on~$\epsilon$, $b$, $k_0$, and~$s$ for which the following holds. 
For every $(b,\eta)$-sparse graph~$G$ and every partition~$(W^j)_0^s$ of
the vertex set of~$G$, there exists an $(\epsilon,G)$-regular
$(\epsilon,k)$-equitable subpartition of~$(W^j)_0^s$ with~$k_0\leq
k\leq K_0$.\qed
\endproclaim

The proof of Lemma~{\SparseSz} goes along the same lines as the proof
of Szemer\'edi's original result~[Sz~78], and hence we omit it here.
As a matter of fact, in order to prove Lemma~{\SparseSz}, one may just
rewrite the argument from [Sz~78] putting the `scaled' density
$d_G(U,W)$ (or, more precisely, $d_G(U,W)/b$) in place of
Szemer\'edi's original density $d(U,W)=e_G(U,W)/|U||W|$. 

 From Lemma~{\SparseSz} it immediately follows that one can uniformly
partition any {\it fixed\/} number of graphs at the same time.
Let~$G_1,\dots,G_m$ be a sequence of graphs defined on the same vertex
set~$V$, and let~$G=\bigcup_{i=1}^mG_i$ be their union, {\it
i.e.\/},~the graph on~$V$ with the edge set $\bigcup_{i=1}^m E(G_i)$.
We say that~$G_1,\dots,G_m$ is {\deffont$(b,\eta)$-sparse\/} if~$G$ is
$(b,\eta)$-sparse. 
%%%Similarly, 
Furthermore, an $(\epsilon,k)$-equitable
partition~$\Pi=(V^i)_0^k$ is
{\deffont$(\epsilon,k;G_1,\dots,G_m)$-regular\/} if it is
$(\epsilon,k;G_i)$-regular for all~$1\le i\le m$.

One can easily deduce from Lemma~{\SparseSz} that every
$(b,\eta)$-sparse sequence of graphs $G_1,\dots,G_m$ admits an
$(\ep,k;G_1,\dots,G_m)$-regular partition, provided $\eta$ is small
enough with respect to $\ep$, $b$ and~$1/k$. Roughly speaking, we
first choose a rapidly decreasing
sequence~$\epsilon=\epsilon_m\geq\epsilon_{m-1}\geq\dots\geq\epsilon_1>0$
of constants, and then invoke Lemma~{\SparseSz} in turn to define a
sequence~$\Pi_1,\dots,\Pi_m$ of finer and finer partitions of~$V$.  To
be precise, $\Pi_i$ is required to be a subpartition of~$\Pi_{i-1}$
for all~$1<i\leq m$, and~$\Pi_i$ ($1\leq i\leq m$) is required to be
an $(\epsilon_i,G_i)$-regular partition of~$V$ with a `small' number
of classes (as small as Lemma~{\SparseSz} can guarantee). Choosing
the~$\epsilon_i$ ($1\leq i\leq m$) carefully enough, the final
partition~$\Pi_m$ of our sequence~$\Pi_1,\dots,\Pi_m$ will be the
$(\ep,k;G_1,\dots,G_m)$-regular partition we seek.

It will be important later that, for any~$1<i\leq m$, the
partition~$\Pi_i$ above may be determined {\it solely\/}
from~$\Pi_{i-1}$ and~$G_i$. In other words, the
graphs~$G_{i+1},\dots,G_m$ play no r\^ole in the definition
of~$\Pi_i$.  

We now make the above informal discussion precise.  Thus, let $k_0$
and $m\ge 3$ be natural numbers, let~$\ue$ be a sequence of numbers
$\ep_1,\dots,\ep_m$ such that $0<\ep_1\le \dots\le \ep_m<1$ and
let~$G_1,\dots,G_m$ be graphs with the same vertex set~$V$, where
$|V|\geq k_0$.  In the definition below, we shall assume that the set
of all equitable partitions of~$V$ have been given a fixed ordering,
say~$\prec$.  The {\deffont$(\ue,k_0)$-canonical sequence of
  partitions\/}~$\tPi_1,\dots,\tPi_m$ for $G_1,\dots,G_m$ is defined
recursively in the following way:
\roster
\item "(i)" Among all the $(\ep_1,k;G_1)$-regular partitions which
  minimize~$k\ge k_0$, let~$\tPi_1$ be the first one according
  to~$\prec$. 
\item "(ii)" Assume that $2\le i\le m$ and that the partition
  $\tPi_{i-1}$ has  already been defined. Then we let $\tPi_i$ be the 
  $\prec$-first $(\ep_i,k;G_1,\dots,G_i)$-regular subpartition of
  $\tPi_{i-1}$ which minimizes~$k$.
\endroster
Note that any partition of the vertices of~$G$ into singletons is
$(\ep,k;G)$-regular for~$k=|V|$ and every $\ep>0$. Thus, for each
sequence~$G_1,\dots,G_m$ as above, an $(\ep,k_0)$-canonical sequence
of partitions does exist and is of course unique by definition.

Now we can use Lemma~{\SparseSz} to deduce that for $(b,\eta)$-sparse
sequences of graphs the sizes of the partitions in the associated
canonical partition can be uniformly bounded from above.

\proclaim {Lemma~\MultiSSz} For every~$\epsilon>0$, $b>2$, $k_0\geq1$
and~$m\geq1$, there are constants~$\eta=\eta(\epsilon,b,k_0,m)>0$
and~$K_0=K_0(\epsilon,b,k_0,m)\geq k_0$ and a sequence
$\ue=\ue(m,b,\epsilon,k_0)=(\ep_1,\dots,\ep_m)$
with~$0<\ep_1\le\dots\le\ep_m=\ep$ such that~$\eta$, $K_0$ and~$\ue$
depend only on~$\epsilon$, $b$, $k_0$ and~$m$ and the following holds.
For every $(b,\eta)$-sparse sequence of graphs~$G_1,\dots,G_m$, the
$(\ue,k_0)$-canonical sequence of partitions~$\tPi_1,\dots,\tPi_m$
associated to~$G_1,\dots,G_m$ only contains partitions of sizes
bounded by $K_0+1$. In fact, we have 
$$ 
k_0+1\le |\tPi_1|\le \dots \le |\tPi_m|\le K_0+1.\oldqed
$$
\endproclaim

Note that~$\ue$ in the lemma above depends only on~$m$, $b$,
$\epsilon$, and~$k_0$. In fact, throughout the paper we shall assume
that, for any given~$m$, $b$, $\epsilon$, and~$k_0$ as in
Lemma~{\MultiSSz}, we have a {\it fixed\/}
vector~$\ue=\ue(m,b,\epsilon,k_0)$ as in that lemma associated with
this choice of~$m$, $b$, $\epsilon$, and~$k_0$.

Let us conclude this section with two simple observations.  The
definition of $\ep$-regularity deals with the distribution of edges 
between `large' sets. Nonetheless, it turns out that each
$\ep$-uniform $\ell$-partite graph~$G$ contains a large $3\ep$-uniform 
$\ell$-partite subgraph~$\bar G$ such that {\it each\/} vertex of
$\bar G$ has a fairly large degree. In fact, more is true as shows
the following lemma. 

\proclaim{Fact~\FactA} Suppose~$\ell\geq 2$ and~$0<\ep<1/5\ell$.
Let~$G$ be an $\ep$-uniform $(\ell+1)$-partite graph
with $(\ell+1)$-partition~$V(G)=V_0\cup\dots\cup V_\ell$.  
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% and $|V_1|=|V_2|=\dots=|V_\ell|=n$. 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Then there exist subsets~$\Vb_i\sb V_i$ $(1\le i\le\ell)$ such that, 
for every~$1\leq i\leq\ell$, we have~$|\Vb_i|\ge(1-\ell\ep )|V_i|$
and for every vertex~$v\in\Vb_i$ we have
$$
|N_G(v)\cap {\bar V}_j|\ge(1-2\ell\ep )e_G(V_i,V_j)/|V_j|
$$
for every~$j\neq i$ $(1\le j\le\ell)$. In particular, the
graph~$\bar G$ induced in~$G$ by $\bigcup_{i=1}^\ell\Vb_i$ is
$3\epsilon$-uniform. 
\endproclaim

\demo{Proof} Since proofs of very similar statements may be found
in~[HK\L~$\star\star$], here we only mention the simple idea behind
the argument.  In order to find the~$\Vb_i$ ($0\le i\le\ell$) we
successively delete from~$V_i$ the vertices that violate the
conditions we seek. Then one can easily show that, because of the
$\ep$-uniformity of~$G$, this process finishes with the required
sets~$\Vb_i$ ($0\le i\le\ell$).\qed

Finally, since every graph~$G$ on~$n$ vertices contains a bipartite
subgraph~$H$ whose vertex classes are of cardinality~$\lfloor
n/2\rfloor$ and~$\lceil n/2\rceil$ and such that~$e(H)\ge e(G)/2$, the
following fact is an immediate consequence of the definition of a
$(b,\eta)$-sparse graph.

\proclaim{Fact~\FactB} If $G$ is $(b,\eta)$-sparse then every
subgraph~$H$ of~$G$ with~$|V(H)|\ge2\eta|V(G)|+2$ vertices contains at
most~$b|V(H)|^2e(G)/|V(G)|^2$ edges.\qed
\endproclaim

\subheading{\S3. The Ruzsa--Szemer\'edi Theorem for Sparse Graphs}  

In this section we state and prove an analogue of a result of Ruzsa
and Szemer\'edi~[RSz~78] (see also Erd\H os, Frankl and
R\"odl~[EFR~86] or Graham and R\"odl~[GR~87]) which remains valid for
$(b,\eta)$-sparse graphs.  Let us say that a graph is
{\deffont$3$-decomposable\/} if it is the union of edge-disjoint
triangles. Then the Ruzsa--Szemer\'edi theorem that we shall need (and
generalize below) may be stated as follows.

\proclaim{Theorem~\RSzThm} For every constant~$c>0$ there exists a
constant~$\hd(c)>0$ such that every $3$-decomposable graph~$G$ with at
least~$cn^2$ edges contains at least~$\hd(c)n^3$ triangles.\qed
\endproclaim  

We would like to apply a similar result for graphs which are not so
dense. Unfortunately, in this case the above theorem is no longer
valid: there are 3-decomposable graphs~$G$ with~$n$ vertices and at
least~$n^2\exp(-3\sqrt{\log n})$ edges which contain only~$e(G)/3$
triangles (see, {\it e.g.\/}, Theorem~6.6 in~[GR~87]). 
We are thus forced to take another approach.  Very roughly speaking, 
our method will consist in proving a probabilistic version of 
Theorem~{\RSzThm}, Lemma~{\MainLemmaB}, asserting that, in some
sense, `counterexamples' as above are rare. 
However, we need to work for a while before we may
state and prove Lemma~{\MainLemmaB}.

We start with a result saying that if a $3$-decomposable graph~$G$
admits an $\ep$-regular partition then, although $G$ may contain only
a few triangles, it must contain many `dense' triples of partition
classes.  To emphasize the difference between triangles on the one
hand and triples of partition classes on the other, we shall refer to
the latter as {\deffont triads\/}.

Thus, let~$G$ be a $(b,\eta)$-sparse graph on~$n$ vertices and let
$\Pi=(V^i)_0^k$ be an $(\ep,k)$-equitable $(\ep,G)$-regular partition
of the vertex set of~$G$. We say that a pair $(V^r,V^s)$ ($1\le r<s\le
k$) is {\deffont thick\/} if it is $(\ep,G)$-regular and
$$
e_G(V^r,V^s)\ge|V^r||V^s|e(G)/50n^2\;.
$$
We say that a triad~$(V^r,V^s,V^t)$  ($1\le r<s<t\le k$) is 
{\deffont thick\/} if all three pairs $(V^r,V^s)$, $(V^r,V^t)$ 
and~$(V^s, V^t)$ are thick. 

\proclaim{Lemma~\SparseRSz} For every $b>2$ there exist constants
$\bd=\bd(b)>0$ and $\bar k_0=\bar k_0(b)\geq1$ that depend only on~$b$
such that the following holds. For every $(b,\eta)$-sparse
$3$-decomposable graph~$G$, if~$\Pi$ is an $(\epsilon,k)$-equitable
$(\epsilon,G)$-regular partition of~$G$ such that~$200\ep b\le1$,
$k\geq \bar k_0$, and $0<\eta\leq\min\{\epsilon,1/2k\}$, then~$\Pi$
contains at least $\bd k^3$ thick triads.
\endproclaim

\demo{Proof} Let~$\bar k_0=\bar k_0(b)=
%%% 40{,}000b$
40000b$ and~$\bd=\bd(b)=\hd(0.3/b)>0$, where~$\hd$ is as given by
Theorem~{\RSzThm}. We shall show that these values will do for our
lemma. Suppose~$200\ep b\le1$ and let~$\Pi$ be an
$(\epsilon,k)$-equitable $(\ep,G)$-regular partition of a
$(b,\eta)$-sparse $3$-decomposable graph~$G$, where~$k\geq \bar k_0$
and $0<\eta\leq\min\{\epsilon,1/2k\}$.  Then the following assertions
hold: 
\roster
\item the number of edges of~$G$ that have both ends in one set
  of~$\Pi$ is, by Fact~{\FactB}, less than  
$$
\ep^2 n^2 b e(G)/n^2+ k(n/k)^2 b e(G)/n^2
  =(\ep^2 b+b/k)e(G)\le e(G)/100\;,
$$
\item the number of edges of~$G$ incident to the vertices in~$V^0$ is
  less than  
$$
\ep n^2 b e(G)/n^2\le \ep b e(G)\le e(G)/200\;,
$$
\item the number of edges between pairs~$(V^r,V^s)$ ($1\le r<s\le k$)
  that are not $\ep$-regular is less than  
$$
\ep\binom k2\(\df nk\)^2\df{be(G)}{n^2}\le \ep be(G)\le e(G)/200\;,
$$
\item the number of edges between pairs $(V^r,V^s)$ ($1\le r< s\le
  k$) that are not thick is less than 
$$ 
\binom k2\(\df nk\)^2\df{e(G)}{50n^2}\le e(G)/100\;. 
$$
\endroster
Hence, at least~$0.97e(G)$ edges of~$G$ belong to thick
pairs~$(V^r,V^s)$. Let these edges form the edge set of the spanning
subgraph~$G^0$ of~$G$. Let~$\cF$ be a family of edge-disjoint
triangles of~$G$ such that~$G=\bigcup\cF$.  Clearly, just
considering~$\cF$, we see that~$G^0$ contains at
least~$e(G)/3-0.03e(G)\ge0.3e(G)$ triangles. In particular, the
partition~$\Pi$ has at least one thick triad,
say~$(V^{\rbr1},V^{\sbr1},V^{\tbr1})$.  Let us delete from~$G^0$ all
edges between the sets~$V^{\rbr1}$, $V^{\sbr1}$ and~$V^{\tbr1}$, and
let~$G^1$ be the graph obtained in this way.  Since the number of
edges we delete is smaller than~$3b(n/k)^2e(G)/n^2\le3be(G)/k^2$, 
we destroy at most~$3be(G)/k^2<0.3e(G)$ triangles from~$\cF$. 
Thus, the graph~$G^1$ contains a triangle and hence 
the partition~$\Pi$, viewed as a partition of~$G^1$, 
contains at least one thick triad. We repeat the procedure above and
obtain a sequence~$G=G^0\supset\dots\supset G^\ell$ of spanning
subgraphs of~$G$ with~$G^\ell$ such that~$\Pi$, viewed as  
a partition of $G^\ell$, contains no thick triad. 
Since in every step we decrease the number of triangles in~$\cF$ by   
at most~$3be(G)/k^2$, we have~$\ell\ge0.1k^2/b$.
Hence, the graph~$G(\Pi)$, whose vertices are the sets~$V^1,\dots,V^k$
and~$V^r$, $V^s$ ($1\le r<s\le k$) are joined by an edge if and only
if the pair~$(V^r,V^s)$ is thick, contains at least~$0.1k^2/b$
edge-disjoint triangles. Thus, by Theorem~{\RSzThm} and our choice
of~$\bd=\bd(b)=\hd(0.3/b)$, the graph~$G(\Pi)$ contains at least~$\bd
k^3$ triangles. Consequently, there exist at least~$\bd k^3$ thick
triads in~$\Pi$ and Lemma~{\SparseRSz} follows.\qed 

We now turn to the main lemma of this section, Lemma~{\FlowerLemma}.
As we have already mentioned in~\S1, this is a rather technical
result, and before we may state it we need to introduce a few
definitions, including the definition of a `flower' in an
edge-coloured graph. Let us say that a sequence~$G_1,\dots,G_m$ of
graphs on the same vertex set is {\deffont balanced\/} if 
\roster
\item $E(G_i)\cap E(G_j)=\emptyset$ for all~$1\le i<j\le m$,
\item $e(G_i)=e(G_j)$ for all~$1\le i<j\le m$,
\item for all~$1\le i\le m$, all the vertices of~$G_i$ have the same 
  degree. 
\endroster
It will be convenient to think of a balanced sequence as above as a
graph~$G$, namely~$G=\bigcup_{i=1}^mG_i$, whose edges have been
coloured with~$m$ colours.  Let~$\tG=(G_i)_{i=1}^m$ be a balanced
sequence of graphs and~$G=\bigcup_{i=1}^mG_i$. Let~$n=|V(G)|$. Suppose
also that $\tPi_1,\dots,\tPi_m$ is the $(\ue,k_0)$-canonical sequence
of partitions associated to~$G_1,\dots,G_m$ for some given~$k_0$ and
some~$\ue=(\ep_1,\dots,\ep_m)$. Then, for any
constant~$0<\delta\leq1$, a {\deffont$(\delta,k_0,\ue;\tG)$-flower\/},
or, for short, a {\deffont$(\delta,\tG)$-flower\/}, consists of three
indices~$1\leq w(1)<w(2)<w(3)\leq m$ together with a vertex~$v$ of~$G$
and a family~$\{(X^{(i)},Y^{(i)})\:1\leq i\leq g\}$ of pairs of
non-exceptional elements~$X^{(i)}$ and~$Y^{(i)}$ of~$\tPi_{w(1)}$ such
that 
\roster
\item $2g|X^{(i)}|=2g|Y^{(i)}|\geq\delta n$, 
\item the~$2g$ sets~$X^{(i)}$, $Y^{(i)}$ ($1\leq i\leq g$) are
  all distinct, 
\item all pairs~$(X^{(i)},Y^{(i)})$ are
  $(\ep_{w(i)},G_{w(1)})$-regular  and 
$$
\eqalign{
e_{G_{w(1)}}(X^{(i)},Y^{(i)})
  &\ge\delta|X^{(i)}||Y^{(i)}|e(G_{w(1)})/10^6n^2\cr
  &=\delta|X^{(i)}||Y^{(i)}|e(G)/10^6mn^2\;,\cr
}
$$
\item the vertex~$v$ is joined to each $X^{(i)}$ ($1\leq i\leq g$)
  by at least~$\delta|X^{(i)}|e(G_{w(2)})/10^6n^2
  =\delta|X^{(i)}|e(G)/10^6mn^2$ edges of~$G_{w(2)}$, 
\item the vertex~$v$ is joined to each $Y^{(i)}$ ($1\leq i\leq g$)
  by at least~$\delta|Y^{(i)}|e(G_{w(3)})/10^6n^2
  =\delta|Y^{(i)}|e(G)/10^6mn^2$ edges of~$G_{w(3)}$. 
\endroster
We may now state and prove Lemma~{\FlowerLemma}. 

\proclaim {Lemma~\FlowerLemma} Let~$b>2$ be given. Then there exist
integers~$m=m(b)\geq3$ and $k_0=k_0(b)$, and a real
number~$0<\delta=\delta(b)\leq1$ that depend only on~$b$ such that,
for any~$0<\epsilon\leq1$, there exists a
constant~$0<\eta=\eta(b,\epsilon)\leq1$ for which the following holds.
Let~$\ue=\ue(m,b,\epsilon,k_0)$.  If~$\tG=(G_i)_{i=1}^m$ is a balanced
$m$-edge-colouring of a $(b,\eta)$-sparse $3$-decomposable
graph~$G=\bigcup_{i=1}^mG_i$, then the $(\ue,k_0)$-canonical sequence
of partitions $\tPi_1,\dots,\tPi_m$ associated to~$\tG=(G_i)_{i=1}^m$
admits a $(\delta,k_0,\ue;\tG)$-flower.
\endproclaim

\demo{\it Remark} In the sequel, when considering $(b,\eta)$-sparse
sequences of graphs~$\tG$ as above, we shall often say that `a
$(\delta,k_0,\ue;\tG)$-flower exists' or that `$\tG$ contains a
$(\delta,\tG)$-flower'. In such cases, we are tacitly assuming that
these flowers are built from the $(\ue,k_0)$-canonical sequence of
partitions associated to our~$\tG$, where~$\ue=\ue(m,b,\epsilon,k_0)$
is the vector we have explicitly associated with~$m$, $b$, $\epsilon$
and~$k_0$.
\enddemo
 
\demo{Proof of Lemma~{\FlowerLemma}} Let~$\bd(b)>0$ be as given by
Lemma~{\SparseRSz}.  Set~$m=m(b)=\lceil3\times10^6/\bd(b)\rceil$,
$\delta=\delta(b)=\bd(b)/1600m^3>0$ and ~$k_0=k_0(b)=\max\{\bar
k_0(b),800m^3/\bd(b)\}\geq1$, where~$\bar k_0(b)$ is given by
Lemma~{\SparseRSz}.  We shall show that the assertion holds with this
choice of~$m$ and~$\delta$ and $k_0$. Thus, let an
arbitrary~$0<\epsilon\leq1$ be given. Clearly, we may assume
that~$\epsilon\leq\min\{1/200b,\bd(b)/800m^3\}$. Now let us invoke
Lemma~{\MultiSSz} to obtain~$\eta(\epsilon,b,k_0,m)>0$
and~$K_0=K_0(\epsilon,b,k_0,m)\geq k_0$ as given by that lemma. We may
and shall assume that~$\eta\leq\min\{\epsilon,1/2K_0\}$. Our aim is to
show that the assertion holds for
$\eta=\eta(b,\epsilon)=\eta(\epsilon,b,k_0,m)$ given above. Therefore,
let~$\tG=(G_i)_{i=1}^m$ be a balanced $m$-edge-colouring of a
$(b,\eta)$-sparse $3$-decomposable graph~$G=\bigcup_{i=1}^mG_i$.  We
need to verify that, under these conditions, a
$(\delta,k_0,\ue;\tG)$-flower does indeed exist.

Let $\tPi_1,\dots,\tPi_m$ be the $(\ue,k_0)$-canonical sequence of
partitions associated $G_1,\dots,G_m$.  We first concentrate our
attention on the graph~$G=\bigcup_{i=1}^mG_i$ and the
partition~$\tPi_m$.  We show that each of at least a half of the thick
triads~$(V^r,V^s,V^t)$ in~$\tPi_m$, whose existence is guaranteed by
Lemma~{\SparseRSz}, has the property that we may assign to its
`sides', {\it i.e.\/},~the pairs $(V^r,V^s)$, $(V^r,V^t)$
and~$(V^s,V^t)$, some three distinct colours so that, if a side is
assigned colour~$1\leq w\leq m$, then it contains a substantial number
of edges from~$G_w$.

Let us eliminate first the triads for which an assignment as we seek is
not possible. Given~$1\leq w\leq m$, we say that a thick
triad~$(V^r,V^s,V^t)$ of the $\epsilon$-regular partition~$\tPi_m$
of~$G$ is {\deffont dominated\/} by~$w$ if,
putting~$u=|V^r|=|V^s|=|V^t|$, at least two out of the
three pairs of sets~$(V^r,V^s)$, $(V^r,V^t)$ and~$(V^s,V^t)$ are
joined by more than
$$ 
u^2e(G)/150n^2\ge(n/2k_m)^2e(G)/150n^2=e(G)/600k_m^2
$$  
edges of~$G_w$, where $k_m=|\tPi_m|-1\le K_0$.
If a thick triad is not dominated by any~$w$ ($1\leq
w\leq m$), we say that it is {\deffont balanced\/}. Since every vertex
of~$G_w$ has degree~$2e(G_w)/n=2e(G)/mn$, at most~$2e(G)/mk_m$ edges
of~$G_w$ are incident to a given set~$V^r$ of~$\tPi_m$. Consequently,
the number of thick triads dominated by~$w$ 
is less than
$$
k_m\[\df{2e(G)/mk_m}{e(G)/600k_m^2}\]^2
  \leq\df{1.5\times10^6k_m^3}{m^2}\leq\df{\bd(b)k_m^3}{2m}\;,
$$
so the number of thick triads dominated by some~$w$ ($1\le w\le m$)
is less than~$\bd(b)k_m^3/2$.  Thus, by Lemma~{\SparseRSz}, the
graph~$G$ contains at least~$\bd(b)k^3_m/2$ balanced thick triads.
  
We call a pair~$(V^r,V^s)$ of partition classes of~$\tPi_m$ a {\deffont
  $w$-rich\/} pair, where~$1\le w\le m$, if the number of edges
of~$G_w$ between~$V^r$ and~$V^s$ is larger
than~$|V^r||V^s|e(G_w)/150n^2=|V^r||V^s|e(G)/150mn^2$.  We say
that~$(V^{r},V^{s},V^{t})$ is
{\deffont$(w(1),w(2),w(3))$-colourable\/}, where the~$w(i)$
($i\in\{1,2,3\}$) are three distinct colours from~$\{1,\dots,m\}$, if
and only if we may assign the colours~$w(1)$, $w(2)$ and~$w(3)$ to the
pairs~$(V^r,V^s)$, $(V^r,V^t)$ and~$(V^s,V^t)$, in some order, in such
a way that a colour~$w$ is assigned to a pair only if this pair is
$w$-rich. Now, let $(V^r,V^s,V^t)$ be a balanced thick triad. 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Thus, if at least one sixth of all edges between 
%some pair of partition classes of this triad, say, 
%$(V^r, V^s)$, is coloured using a colour $w$, 
% then less than one sixth of edges between two 
%other  pairs $(V^r,V^t)$, $(V^s, V^t)$, are coloured
%using $w$.  One can easily see that this fact implies that each such
%not dominated thick triad is $(w1,w2,w3)$-colourable for some
%$w1,w2,w3$. 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
A moment's thought reveals that any such triad is
$(w(1),w(2),w(3))$-colourable for some~$1<w(1)<w(2)<w(3)\leq m$.
Consequently, there is a choice of~$(w(1),w(2),w(3))$ with~$1\le
w(1)<w(2)<w(3)\le m$ such that~$\tPi_m$ contains at
least~$\bd(b)k^3_m/2{m\choose3}$ thick triads that are
$(w(1),w(2),w(3))$-colourable.

Thus, there exist a non-exceptional partition class~$\bar V$ of~$\tPi_m$ and 
pairs~$(U^i_m,W^i_m)$ ($1\leq i\leq f=\lceil\bd(b)k^2_m/2m^3\rceil$)
of non-exceptional partition classes of~$\tPi_m$
such that, for all~$1\leq i\leq f$, 
the triple~$(\bar V,U^i_m, W^i_m)$ satisfies the following conditions: 
\roster
\item the pair~$(U_m^i, W_m^i)$ is $(\ep,G_{w(1)})$-regular, and
$$
e_{G_{w(1)}}(U_m^{i},W_m^i)\ge|U_m^i||W_m^i|e(G_{w(1)})/150n^2,
$$
\item the pair~$(\bar V,U_m^i)$ is $(\ep,G_{w(2)})$-regular, and
$$
e_{G_{w(2)}}(\bar V,U_m^i)\ge|\bar V||U_m^i|e(G_{w(2)})/150n^2,
$$
\item the pair~$(\bar V,W_m^i)$ is $(\ep,G_{w(3)})$-regular, and
$$
e_{G_{w(3)}}(\bar V,W_m^i)\ge|\bar V||W_m^i|e(G_{w(3)})/150n^2.
$$
\endroster

Now, it follows from Fact~{\FactA} with $\ell=3$ that, for every
given~$i$ ($1\leq i\leq f$), at least a half of the vertices of~$\bar
V$ is joined both by at least~$|U_m^i|e(G_{w(2)})/300n^2$ edges
of~$G_{w(2)}$ to~$U_m^i$ and by at least~$|W_m^i|e(G_{w(3)})/300n^2$
edges of~$G_{w(3)}$ to~$W_m^i$.  Thus, by an elementary averaging
argument, there is a vertex~$v$ in~$\bar V$ and a
set~$\Xi=\{(U^i_m,W^i_m)\:i\in\Lambda\}$ of $w(1)$-rich
pairs~$(U^i_m,W^i_m)$ of cardinality~$|\Lambda|
%%%  $ at least~$
\ge f/2\geq\bd(b)k^2_m/4m^3$ such that~$v$ is joined by at
least~$|U_m^i|e(G_{w(2)})/300n^2$ edges of~$G_{w(2)}$ to~$U_m^i$ and
by at least~$|W_m^i|e(G_{w(3)})/300n^2$ edges of~$G_{w(3)}$ to~$W_m^i$
for all~$(U^i_m,W^i_m)\in\Xi$.

We shall show that the existence of such a vertex~$v$ and such a
set~$\Xi$ implies the existence of a $(\delta,\tG)$-flower. The three
colours associated to the flower we shall exhibit are~$w(1)$, $w(2)$,
$w(3)$.  
%%% Note 
Our only problem is that so far we have only considered the
partition~$\tPi_m$, whereas the definition of the flower deals with
subsets of the partition $\tPi_{w(1)}$. Thus, in the rest of the proof
we shall try to relate the properties of~$\tPi_m$ with those
of~$\tPi_{w(1)}$. In order to do this, we shall consider the
graph~$\hG(\tPi_m,\Xi)$, whose vertex set is the set of
non-exceptional partition classes of~$\tPi_m$, with two such
vertices~$U_m$, $W_m$ being connected by an edge in~$\hG(\tPi_m,\Xi)$
if and only if~$(U_m,W_m)\in\Xi$.

Note first that~$\hG(\tPi_m,\Xi)$ has~$N=k_m$ vertices and at
least~$cN^2$ edges, where $c=\bd(b)/8m^3$.  Furthermore, since~$\tPi_m$
is a subpartition of $\tPi_{w(1)}$, each non-exceptional partition
class of~$\tPi_m$ is contained in some non-exceptional partition class
of~$\tPi_{w(1)}$. Thus, the partition~$\tPi_{w(1)}$ of~$G$ naturally
induces a partition~$\hat\Pi_{w(1)}$ of the vertex set
of~$\hG(\tPi_m,\Xi)$.  Unfortunately, because of the exceptional
class~$V^0_m$ of~$\tPi_m$, not all partition classes
of~$\hat\Pi_{w(1)}$ need have the same size. However,
since~$|V^0_{w(1)}|$, $|V^0_m|\le\ep n$ we immediately see that all of
them contain at most~$2k_m/k_{w(1)}$ elements, and a little argument
shows that at least $(1-3\ep)k_{w(1)}$ of them have at
least~$k_m/2k_{w(1)}$ elements. 

Now suppose~$\ell\ge100/c$ and~$\ep\le c/100$. Then simple
calculations show that the following holds: for any graph~$\hG$
with~$N$ vertices and at least~$cN^2$ edges, and every
partition~$\hat\Pi=(V^i)_{i=1}^\ell$ of the vertex set of~$\hG$
into~$\ell$ classes such that all the partition classes~$V^i$ have
cardinality at most~$2N/\ell$ and not fewer than~$(1-3\ep)\ell$ of
them have cardinality greater than or equal to~$N/2\ell$, there exist
at least~$c\ell^2/100$ pairs~$\{\hV,\hV'\}$ of distinct partition
classes of~$\hat\Pi$ such that~$|\hV|$, $|\hV'|\ge N/2\ell$ and~$\hV$,
$\hV'$ are joined by at least~$c|\hV||\hV'|/10$ edges.  Hence, since
every graph on at most~$k$ vertices and at least~$ck^2$ edges contains
a matching of size at least~$ck/2$, the above partition~$\hat\Pi$
of~$\hG$ must contain at least~$g=\lceil{c\ell/200}\rceil$ disjoint
pairs~$(\hX^i,\hY^i)$ ($1\leq i\leq g$) such that~$|\hX^i|$,
$|\hY^i|\ge N/2\ell$ and such that the number of edges between~$\hX^i$
and~$\hY^i$ is at least~$c|\hX^i||\hY^i|/10$ for all~$1\leq i\leq g$.
Finally, we may again use the fact that dense graphs contain large
matchings to deduce that there is a matching of size at
least~$cN/40\ell$ between~$\hX^i$ and~$\hY^i$ for all~$1\leq i\leq g$.

We apply this observation to~$\hG=\hG(\tPi_m,\Xi)$ and the 
partition~$\hat\Pi=\hat\Pi_{w(1)}$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Let $(X^i_{w1},Y^i_{w1})$,be pairs of partition classes of $\tPi_{w1}$ 
%which correspond to pairs of partition classes $(\hX^i, \hY^i)$ of  
%$\hat\Pi_{w1}$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Thus let us check the required hypotheses for our observation to
apply. First note that the condition~$\ell\ge100/c$ becomes in our
context~$k_{w(1)}\ge800m^3/\bd(b)$, whilst $\ep\le c/100$ corresponds
to~$\ep\le\bd(b)/800m^2$. The number of disjoint pairs~$(\hX^i,\hY^i)$
($1\leq i\leq g$) guaranteed by the observation is~$g=\lceil
ck_{w(1)}/200\rceil=\lceil\bd(b)k_{w(1)}/1600m^3\rceil$. Moreover,
$\hX^i$ is joined to~$\hY^i$ by at least
$$
\df{c|\hX^i||\hY^i|}{10}
  \ge\df c{10}\(\df{k_m}{2k_{w(1)}}\)^2
  \ge\df 1{10}\cdot\df{\bd(b)}{8m^3}\cdot\df{k_m^2}{4k^2_{w(1)}}
  =\df{\bd(b)k_m^2}{320k^2_{w(1)}m^3}
$$
edges of~$\hG(\tPi_m,\Xi)$, and hence the corresponding 
pair~$(X^i_{w(1)},Y^i_{w(1)})$ of partition classes of~$\tPi_{w(1)}$ 
is joined by at least
$$
\df{\bd(b)k_m^2}{320k^2_{w(1)}m^3}\(\df{n}{2k_m}\)^2
\df{e(G_{w(1)})}{150n^2}
  \ge\df{\bd(b)|U^i_{w(1)}||W^i_{w(1)}|e(G)}{2\times10^5m^4n^2}
$$
edges of $G_{w(1)}$. 

Furthermore, we know that, for every~$1\leq i\leq g$, the
graph~$\hG(\tPi_m,\Xi)$ contains a matching $\hat M_i$ between~$\hX^i$
and~$\hY^i$ of size at least 
$$
\df{c}{40}\cdot\df{k_m}{k_{w(1)}}
  =\df{\bd(b)}{320m^3}\cdot\df{k_m}{k_{w(1)}}\;.
$$ 
Recall that every edge of~$\hG(\tPi_m,\Xi)$ corresponds to a
pair~$(U_m,W_m)$ from~$\Xi$. We may and shall assume that at least
$(\bd(b)/640m^3)k_m/k_{w(1)}$ of the edges~$(U_m,W_m)$ from~${\hat
  M}_i$ are such that~$U_m\in\hX^i$ and $W_m\in\hY^i$ ({\it 
  i.e.\/},~$U_m\subseteq X^i_{w(1)}$ and~$W_m\subseteq Y^i_{w(1)}$).
Recall that, for every~$(U_m,W_m)\in\Xi$, the vertex~$v$ is joined
to~$U_m$ by at least  
$$
\df{|U_m|e(G_{w(2)})}{300n^2}
  \ge\df{n}{2k_m}\cdot\df{e(G)}{300mn^2}
  =\df{e(G)}{600k_mmn}
$$
edges of~$G_{w(2)}$, and similarly it is joined to~$W_m$ by at
least~$e(G)/600k_mmn$ edges of~$G_{w(3)}$. Therefore the 
vertex~$v$ is joined to~$X^i_{w(1)}$ by at least
$$
\df{\bd(b)}{640m^3}\cdot\df{k_m}{k_{w(1)}}\cdot\df{e(G)}{600k_mmn} 
   \ge|X^i_{w(1)}|\df{\bd(b)e(G)}{4\times10^5m^4n^2}
$$ 
edges of~$G_{w(2)}$. Clearly, the same argument applied
to~$Y^i_{w(1)}$ shows that~$v$ is joined to~$Y^i_{w(1)}$ by at
least~$|Y^i_{w(1)}|\bd(b)e(G)/4\times10^5m^4n^2$ edges of~$G_{w(3)}$.
Since~$\delta=\bd(b)/1600m^3$, we conclude that there are at
least~$g=\lceil\delta k_{w(1)}\rceil$ pairwise disjoint
pairs~$(X^i_{w(1)},Y^i_{w(1)})$ of non-exceptional partition classes
of~$\tPi_{w(1)}$ such that every such pair is $(\ep,G_{w(1)})$-regular,
between every such pair there are at
least~${\bd(b)|U^i_{w(1)}||W^i_{w(1)}|e(G)}/{10^6m^4n^2}$ edges
of~$G_{w(1)}$, and one set of every such pair is joined to~$v$ by at
least  
$$
|X^i_{w(1)}|\df{\bd(b)e(G)}{4\times10^5m^4n^2}
  \ge\df{\bd(b)|X^i_{w(1)}|e(G)}{10^6m^4n^2}
   =\df{\bd(b)|Y^i_{w(1)}|e(G)}{10^6m^4}
$$
edges of~$G_{w(2)}$, while the other is joined to~$v$ by at
least~$\bd(b)|Y^i_{w(1)}|e(G)/10^6m^4n^2$ edges
of~$G_{w(3)}$. Finally, if~$u$ is the common cardinality of the
sets~$X^i_{w(i)}$, $Y^i_{w(1)}$ ($1\leq i\leq g$), 
then~$2gu\geq\delta n$.  Therefore~$1\leq w(1)<w(2)<w(3)\leq m$, 
together with~$v\in V(G)$, and~$\{(X^i_{w(1)},Y^i_{w(1)})\:1\leq i\leq
g\}$ form a $(\delta,\tG)$-flower, and
Lemma~{\FlowerLemma} follows.\qed 

\subheading{\S4. Random Subgraphs of Uniform Bipartite Graphs}

In this section we give a result that, although a little technical,
may be of independent interest. Namely, we prove that, under quite
weak hypotheses, with very large probability a random induced
subgraph~$H'$ of a bipartite uniform graph~$H$ contains a fair number
edges. In fact, we show that, in selecting the random subgraph~$H'$ in
question, we may 
%%% even 
allow an `adversary' to `mark', {\it during the
  selection process\/}, a few vertices of~$H$ as forbidden vertices
for~$H'$ so as to minimize our chances of getting many edges in our
random subgraph; even with this rule the probability that we fail to
get a few edges in~$H'$ is essentially super-exponentially small in
the number of edges of the original bipartite graph~$H$.

Let~$H=H(u,\rho,\epsilon)$ be an $\epsilon$-uniform bipartite graph
with bipartition~$V(H)=V_1\cup V_2$, where~$|V_1|=|V_2|=u\geq1$, and
with edge-density~$e(H)u^{-2}=\rho$. Let~$d_1$, $d_2\leq u$ be two
given positive integers. 
%%% Let us now 
Now select a random induced subgraph
of~$H$ in the following manner. First, an adversary
chooses a set~$S_1\subset V_1$ with~$|S_1|\leq u/\log\log u$. Then we
randomly pick a set~$D_1\subset V_1\setminus S_1$ with~$|D_1|=d_1$,
with all the $d_1$-subsets of~$V_1\setminus S_1$ equiprobable. Next,
under the full knowledge of the sets~$S_1$ and~$D_1$, our adversary
picks a set~$S_2\subset V_2$ with~$|S_2|\leq u/\log\log u$, and we
randomly pick a set~$D_2\subset V_2\setminus S_2$ with~$|D_2|=d_2$,
with all the $d_2$-subsets of~$V_2\setminus S_2$ equiprobable. Let us
call the outcome of the above procedure a {\deffont random
  $(d_1,d_2;S_1,S_2)$-subgraph\/} of~$H$, or simply a
{\deffont$(d_1,d_2)$-subgraph\/} of~$H$.

\proclaim{Lemma~\IndSubgr} For every constant~$0<\beta\leq1$, there
exist a constant~$0<\epsilon=\epsilon(\beta)\leq1$ and a natural
number~$u_0$ such that, for any real~$d\ge2(u/\epsilon)^{1/2}$ and any
given graph~$H=H(u,\rho,\ep)$ as above with~$u\geq u_0$ and~$\rho\geq
d/u$, the following assertion holds. If~$d_1$, $d_2\geq d$, regardless
of the choices for~$S_1$ and~$S_2$ of our adversary, the probability
that a random $(d_1,d_2;S_1,S_2)$-subgraph of~$H$ fails to contain at
least~$d/2$ edges is at most~$\beta^d$.
\endproclaim 

\demo{Proof} Given~$0<\beta\leq1$, we choose~$\epsilon=\beta^2/16>0$
and show that this choice of~$\epsilon>0$ will do.  In the sequel, we
assume that~$u$ is large enough for our inequalities to hold.  Let our
adversary choose the set~$S_1\subset V_1$. Recall that~$|S_1|\leq
u/\log\log u$. We show first that the set~$U$ of those vertices
of~$V_2$ that are adjacent to the vertices in our random
set~$D_1\subset V_1\setminus S_1$ is larger than~$(1-\ep)n$ with
probability at least $1-(4\ep)^{d/2}$.  In order to do so we generate
the vertices of~$D_1$ one by one and prove that, typically, in each
step we enlarge the set~$U$ by a fair number of vertices.

Let us randomly choose a vertex~$v^1$ among all the vertices
of~$V_1\setminus S_1$ to be the first vertex of~$D_1$.  Denote
by~$W^1$ the set of the vertices of~$V_1$ that have fewer
than~$d\ep/2<(1-\epsilon)d$ neighbours in~$V_2$. Then, by
the~$\epsilon$-regularity of~$(V_1,V_2)$, we have that~$|W^1|\le\ep
u$.  If~$v^1$ belongs to~$W^1$, let us say that it is a {\deffont
  bad\/} vertex, whereas if~$v^1\notin W^1$ let us say that it is a
{\deffont good\/} vertex. Finally, let~$U^1\sb V_2$ be the set of the 
neighbours of~$v^1$ in~$V_2$.


%%% I have made a few editorial changes in the text that follows
Similarly, let us suppose that for some~$2\leq i\leq d_1$ the
vertices~$v^1,\dots,v^{i-1}$ have already been put into~$D_1$. 
We randomly pick a vertex~$v^i$
from~$V_1\setminus(\{v^1,\dots,v^{i-1}\}\cup S_1)$ to be the~$i$th
vertex of~$D_1$ and  denote by~$U^{\leq i-1}$ the set of neighbours
of~$v^1,\dots,v^{i-1}$. Then, if~$|U^{\leq i-1}|\leq(1-\epsilon)u$, we
let~$W^i$ be the set of all the vertices in~$V_1$ that have fewer than
$d\ep/2\le(1-\epsilon)\epsilon d$ neighbours in~$V_2\setminus U^{\le
  i-1}$. Note that, by the $\epsilon$-regularity of the pair
$(V_1, V_2)$, we have $|W^i|\le\epsilon u$. As before, we call~$v^i$  
{\deffont bad\/} if it belongs to~$W^i$ and {\deffont
  good\/} otherwise. Moreover, in the case in which~$|U^{\leq
  i-1}|>(1-\epsilon)u$, we always say that~$v^i$ is good.
This process is continued until all the~$d_1$ elements of~$D_1$ have been
chosen.

Now, suppose that our process has terminated with a set~$D_1$
with~$U=U^{\leq d_1}$ of cardinality~$|U|<(1-\epsilon)u$.  Since each
good vertex~$v^i$ increases the size of the neighbourhood
of~$D_1$ in~$V_2$ by at least $d\ep/2$, the number of good elements
in~$D_1$ must be less than $2u/d\ep\le d_1/2$.  Hence, at least a half
of all the elements of~$D_1$ must be bad, but the probability of this
happening is smaller
than~$2^{d_1}\epsilon^{d_1/2}\leq(4\epsilon)^{d/2}$.  Thus,
$|U|\ge(1-\ep)n$ with probability at least~$1-(4\ep)^{d/2}$.

Assume now that our process has terminated with a set~$D_1$
with~$U=U^{\leq d_1}$ of cardinality~$|U|\geq(1-\epsilon)u$.  We now
let our adversary pick his set~$S_2\subset V_2$.  Then the probability
that at least a half of the~$d_2\ge d$ vertices of~$D_2$ should lie
outside~$U$ is at most~$2^{d_2}\big(\epsilon
n/(n-|S_2|)\big)^{d_2/2}$, which, 
%%%
for sufficiently large~$u$, is less
than~$2^{d_2}(2\epsilon)^{d_2/2}\leq(8\epsilon)^{d/2}$.

Thus, the probability that our random $(d_1,d_2)$-subgraph of~$H$
contains fewer than~$d/2$ edges is bounded from above
by~$(4\ep)^{d/2}+(8\epsilon)^{d/2}\leq(16\ep)^{d/2}=\b^d$, as
required.\qed

\subheading{\S5. A Sufficient Condition for Uniformity}

Let~$G$ be an $\ell$-partite graph with
$\ell$-partition~$V(G)=V_1\cup\cdots\cup V_\ell$ ($\ell\geq2$).
%%%
Recall that~$G$ is $\ep$-uniform if all pairs~$(V_i,V_j)$ ($1\leq
i<j\leq\ell$) are $\epsilon$-regular.  Moreover, observe that in order
to check the $\epsilon$-regularity for any such pair~$(V_i,V_j)$, in
principle one must examine the density of many pairs~$(A,B)$
with~$A\subseteq V_i$, $B\subseteq V_j$.  However, it
turns out that the $\ep$-regularity of~$(V_i,V_j)$ is implied by a
rather simple condition imposed upon the intersection of the
neighbourhoods of pairs of vertices. This idea has been exploited in
many places; see, {\it e.g.\/}, Alon, Duke, Lefmann, R\"odl and
Yuster~[ADLRY~94], Frankl, R\"odl and Wilson~[FRW~88] and
Thomason~[Th~87a] (see also [Th~87b]).  The following fact is a
slight refinement of earlier results 
%%% in~[FRW~88, Th~87a]. Since in the proof we repeat Andrew's
%%% argument I have decided to move him to the first place.
in~[Th~87a] and~[FWR~88]. 

\proclaim{Lemma~\PairInter} Let~$G$ be a $d$-regular bipartite graph
with bipartition~$V(G)=V_1\cup V_2$, where~$|V_1|=|V_2|=n$ and~$d=pn$
$(0<p\leq1)$. Assume that for a subset~$B$ of~$V_2$ with~$b$ vertices
and some~$\ep>0$ we have
$$
\sum_{x,x'\in B}|N(x)\cap N(x')|\le(1+\ep)\db b2np^2\;, 
  \slabel{InterCond}
$$
where the sum is taken over all unordered pairs~$x$, $x'\in B$
with~$x\neq x'$. Then, for every subset~$A$ of $V_1$ with~$a$
vertices, we have 
$$
(e(A,B)-abp)^2\le\ep a(n-a)b^2 p^2+abnp\;.
$$
\endproclaim

\demo{Proof} Suppose~$V_1=\{x_1,\dots,x_n\}$ and let~$d_i$ ($1\leq
i\leq n$) be the number of neighbours the vertex~$x_i$ has
in~$B$. For simplicity of notation, assume that~$A=\{x_1,\dots,x_a\}$. 
Then, since~$G$ is $d$-regular, we have
$$
\sum_{i=1}^nd_i=e(V_1,B)=db=e(A,B)+e(V_1\setminus A,B)\;.
$$
Furthermore, using~{\eqnoInterCond}, counting directed paths of length
two with both ends in~$B$ leads to  
$$
(1+\ep)b(b-1)np^2\ge \sum_{i=1}^nd_i(d_i-1)
   =\sum_{i=1}^ad_i(d_i-1)+\sum_{i=a+1}^nd_i(d_i-1)\;.
$$
Since~$\sum_{i=1}^ad_i=e(A,B)$ and~$\sum_{i=a+1}^nd_i=e(V_1\setminus
A,B)=db-e(A,B)$, by the Cauchy--Schwarz inequality we have
$$ 
\eqalign{
(1+\ep)b(b-1)np^2
  \ge{1\over a}&e(A,B)(e(A,B)-a)\cr
               &\quad+{1\over n-a}(db-e(A,B))(db-e(A,B)-n+a)\;,\cr  
}
$$
which, after elementary calculations, may be reduced to 
$$
abpn(n-a)(1-p)+\ep a b(b-1)p^2n(n-a)  
   \ge n(e(A,B)- abp)^2\;,
$$
from which the assertion easily follows.\qed

As an immediate consequence of the above result we obtain a simple
sufficient condition for the $\eta$-uniformity of a regular bipartite
graph~$G$.

\proclaim{Lemma~\UnifCond} Let~$G$ be a $d$-regular bipartite graph
with bipartition~$V(G)=V_1\cup V_2$, where~$|V_1|=|V_2|=n$, $d=pn$,
and~$p=\omega/n$ with~$\omega=\omega(n)\to\infty$ as~$n\to\infty$.
Suppose that for some constant~$0<\ep<1/2$ independent of~$n$ we have
$$
\sum_{x,x'}\(|N(x)\cap N(x')|-(1+\ep)np^2\)\le4\ep^3 n^3p^2\;, 
   \slabel{InterCondB}
$$
where the sum is taken over all unordered pairs~$x$, $x'\in V_2$
with~$x\neq x'$ and~$|N(x)\cap N(x')|\ge(1+\ep)np^2$. Then~$G$ is 
$8\ep^{1/3}$-uniform provided~$n$ is large enough. 
\endproclaim

\demo{Proof} Take any~$A\sb V_1$, $B\sb V_2$ of
sizes~$a=|A|\geq2\ep^{1/3}n$ and $b=|B|\geq2\ep^{1/3}n$.  
Then, writing~$\sum'_{x,x'\in B}$ for the sum over all unordered pairs
of distinct vertices~$x$, $x'\in B$, and~$\sum''_{x,x'\in V_2}$ for
the sum over all unordered pairs of distinct vertices~$x$, $x'\in V_2$
with~$|N(x)\cap N(x')|\geq(1+\ep)np^2$, 
we have from~{\eqnoInterCondB} that 
$$
\align\sum_{x,x'\in B}\nolimits'&|N(x)\cap N(x')|
      \le(1+\ep)\db b2 np^2+\sum_{x,x'\in V_2}\nolimits''
                               \(|N(x)\cap N(x')|-(1+\ep)np^2)\)\\ 
 &\qquad\le(1+\ep)\db b2 np^2+4\ep^3n^3p^2
           \le(1+\ep+2\ep^2)\db b2 np^2
            \le(1+2\ep)\db b2 np^2\;.
\endalign
$$
Furthermore, since~$\omega=pn\to\infty$ as~$n\to\infty$, for large
enough~$n$ we have that~$abpn\leq\epsilon anb^2p^2$ and hence, by
Lemma~{\PairInter}, we have 
$$
|e(A,B)-abp|\le\sqrt{4\ep anb^2p^2}
   \le2\ep^{1/3}abp.
$$
Now, to complete the proof, it is enough to observe 
that, according to our definition of density,
$d_G(A,B)=4e(A,B)/abp$ while $d_G(V_1,V_2)=4$.
Hence
$$|d_G(A,B)-d_G(V_1,V_2)|={4|e(A,B)-abp|\over abp}\le 8 \ep^{1/3}\;,$$
as required.\qed


\subheading{\S6. Difference-Graphs}

Let~$A$ be a subset of~$[n]=\{0,1,\dots,n-1\}$.  The associated
{\deffont difference-graph\/}~$G_A=G_A(n)$ is the bipartite graph with
bipartition~$V(G_A)=V\cup W$, where both~$V$ and~$W$ are copies
of~$[n]$, and for~$v\in V$ and~$w\in W$ the pair~$\{v,w\}$ is an edge
of~$G_A$ if and only if~$w\equiv v+a\pmod n$ for some~$a\in A$.  It is
immediate that each vertex of~$G_A$ has degree~$|A|$, and that the
number of common neighbours of two distinct vertices~$v$ and~$v'$ that
belong to the same class of the bipartition depends only on the value
of~$v-v'$. In fact, this value 
%%%equals 
is the same as the number~$t_A(v-v')$ of
ordered pairs~$(a,a')\in A\times A$ such that $a'-a\equiv v-v'\pmod
n$.  Therefore, the structure of~$G_A$ is closely related to the
behaviour of the numbers~$t_A(j)$ ($1\leq j<n$).  Our next result
deals with the distribution of the~$t_R(j)$ for a random
set~$R\in\cR(n,p)$. In the sequel, we write~$\pl$ and~$\mn$ for 
addition and subtraction modulo~$n$, respectively.

\proclaim{Lemma~\DiffGr} For every fixed~$0<\ep\leq1$
and~$0<\eta\leq1$ there exists a constant~$C=C(\epsilon,\eta)$ for
which the following holds.  For every~$p=p(n)\ge C/\sqrt n$, the
probability that~$R\in\cR(n,p)$ satisfies
$$
\sum\big\{t_R(j)-(1+\ep)np^2\big\}\le\eta n^2p^2, \slabel{LargeDev}
$$
where the sum is taken over all~$1\leq j<n$ such
that~$t_R(j)\ge(1+\ep)np^2$, tends to~$1$ as~$n\to\infty$. 
\endproclaim

\demo{Proof} 
For~$i\in[n]$, let~$I_i$ be the characteristic function of the
event~$\{i\in R\}$. Thus~$I_i$ is a $0$--$1$~random variable
with~$I_i=1$ if and only if~$i\in R$.  For a given~$1\leq j<n$, let us
divide the set of all~$n$ pairs $(i,i\pl j)$ ($i\in[n]$) into three
classes~$B^1(j)$, $B^2(j)$ and $B^3(j)$ in such a way that~$\lfloor
n/3\rfloor\le|B^\ell(j)|\le\lceil n/3\rceil$ for
all~$\ell\in\{1,2,3\}$, and such that, for any~$i\in[n]$,
no~$B^\ell(j)$ contains both pairs~$(i\mn j,i)$ and~$(i,i\pl j)$.  The
fact that such a partition is always possible follows from the simple
observation that every $2$-regular graph admits a proper
$3$-edge-colouring in which the sizes of any two colour classes differ
by at most one. In fact, for later convenience, we may and shall
further require of the~$B^\ell(j)$ that, for all~$\ell\in\{1,2,3\}$,
if~$j_1+j_2=n$, then the set of unordered pairs that naturally
correspond to the elements of~$B^\ell(j_1)$ should be the same as the
corresponding set for~$B^\ell(j_2)$. Now, for all~$1\leq j<n$
and~$\ell\in\{1,2,3\}$, define the random variables~$X(j,\ell)$
and~$\X(j,\ell)$ by setting
$$
X(j,\ell)=\sum_{(i,i\pl j)\in B^\ell(j)}I_iI_{i\pl j},
$$
and
$$
\X(j,\ell)=\cases 0         &\quad\text{ if } 
                                X(j,\ell)<(1+\ep)|B^\ell(j)|p^2\\
                   X(j,\ell) &\quad\text{ otherwise}
           \endcases
$$
or, shortly, $\X(j,\ell)=\one(j,\ell)X(j,\ell)$, where~$\one(j,\ell)$ 
is the characteristic function of the event~$\{X(j,\ell)
\ge(1+\ep)|B^\ell(j)|p^2\}$. Then, clearly, we
have~$t_R(j)=X(j,1)+X(j,2)+X(j,3)$ for all~$1\leq j<n$. Notice now
that the left-hand side of~{\eqnoLargeDev} is at most
$$
\sum_{\ell=1}^3\sum_{j=1}^{n-1}
         \(\X(j,\ell)-\one(j,\ell)(1+\ep)|B^\ell(j)|p^2\)\;. 
$$
Hence it is enough to show that, with probability tending to~$1$
as~$n\to\infty$, we have  
$$
Z=\sum_{\ell=1}^3\sum_{j=1}^{n-1}\X(j,\ell)\le \eta n^2p^2. 
    \slabel{AimDiffGra} 
$$

Let us estimate first the expectation~$\E\X(j,\ell)$ of $\X(j,\ell)$.
%%%  changed slightly as Yoshi suggested
Note that~$X(j,\ell)$ is a sum of {\it independent\/} 0--1 random
variables, and thus it has binomial distribution~$\Bi(m,p^2)$,
where~$m=|B^\ell(j)|$. (It was for achieving the above independence
that the classes~$B^1(j)$, $B^2(j)$ and~$B^3(j)$ were introduced).
Therefore, setting~$r_0=\lceil(1+\ep)p^2m\rceil$, we get  
$$
\eqalignno{
\E(\X(j,\ell))&=\sum_{r=r_0}^m r\db mr p^{2r}(1-p^2)^{m-r}
               =mp^2\sum_{r=r_0}^m\db{m-1}{r-1}p^{2r-2}(1-p^2)^{m-r}\cr
              &=mp^2\sum_{r=r_0-1}^{m-1}\db{m-1}{r}p^{2r}(1-p^2)^{m-r-1}  
               =mp^2\ble(r_0-1;m-1,p^2),
&\alabel{ExpXhat}
}
$$
where~$\ble(r_0-1;m-1,p^2)$ is the probability that a binomial
random variable with parameters~$m-1$ and~$p^2$ takes 
values greater than or equal to~$r_0-1$. 
The behaviour of the function~$\ble$ is, of course,  
well studied, and it is known that for every choice of~$m'$, $p'$
and~$k'$ such that~$k'\le m'p'$ we have  
$$
\ble(m'p'+k';m',p')\le\exp\Big(-\df{(k')^2}{3m'p'}\Big)\;.
$$
(See, for instance, \S6~in McDiarmid~[McD~89]). Thus, in our case, 
$$
\ble(r_0-1;m-1,p^2)\le \exp\Big(-\df{(\ep p^2m-1)^2}{3(m-1)p^2}\Big) 
   \le\exp\Big\{-\df1{10}\ep^2np^2\Big\}\;,
$$
where here and below we assume that~$n$ is large enough for all our
inequalities to hold. Hence~$\E\X(j,\ell)\le|B^\ell(j)|p^2\exp(-\ep^2
np^2/10)$ and, consequently,  
$$
\E(Z)=\E\Big(\sum_{\ell=1}^3\sum_{j=1}^{n-1}\X(j,\ell)\Big)
       \le n^2p^2\exp\Big\{-\df1{10}\ep^2np^2\Big\}\;.
$$
Thus, if~$p=p(n)$ is such that~$np^2\to\infty$ as~$n\to\infty$, then 
the right-hand side of the above inequality
is~$o(n^2p^2)$. Therefore, by Markov's inequality,
relation~{\eqnoAimDiffGra} holds with probability~$1-o(1)$
as~$n\to\infty$, and hence our lemma follows in this case.

In order to complete the proof, it is enough to consider the case when
$p=p(n)>C/\sqrt n$ for some large~$C>0$ but, say, $np^2<\log\log n$.
Thus we henceforth assume that~$p=p(n)$ satisfies these conditions.
In the remaining, rather technical part of the proof, 
we shall compute the variance
of~$Z=\sum_{\ell=1}^3\sum_{j=1}^{n-1}\X(j,\ell)$ for such a~$p$ and
then show that this random variable is concentrated around its
expectation through a direct application of Chebyshev's inequality. 

First, let us note that with~$m=|B^\ell(j)|$ as before we have that
the variance~$\Var(\X(j,\ell))$ of~$\X(j,\ell)$ is no greater than
$$
\eqalignno{
\sum_{r=r_0}^m r^2 \db mr p^{2r}&(1-p^2)^{m-r}
       =\sum_{r=r_0}^m r(r-1) \db mr p^{2r}(1-p^2)^{m-r}+\E\X(j,\ell)\cr
  &=m(m-1)p^4\sum_{r=r_0-2}^{m-2}\db{m-2}{r}p^{2r-2}(1-p^2)^{m-r-2}
              +\E\X(j,\ell)\cr
  &=m(m-1)p^4\ble(r_0-2;m-2, p^2)+mp^2\ble(r_0-1;m-1,p^2)\cr
  &\le n^2p^4\exp\Big\{-\df1{10}\ep^2np^2\Big\}=O(1).\cr
}
$$ 
Note that for~$j_1$, $j_2\in\{1,\dots,n-1\}$, if~$j_1+j_2=n$,
then~$\X(j_1,\ell)=\X(j_2,\ell)$ for all~$\ell\in\{1,2,3\}$. Thus the
covariance~$\Cov(\X(j_1,\ell),\X(j_2,\ell))$ between~$\X(j_1,\ell)$
and~$\X(j_2,\ell)$ coincides with~$\Var(X(j_1,\ell))=O(1)$.  Now
let~$(j_1,\ell_1)\neq(j_2,\ell_2)$ and suppose also that
if~$j_1+j_2=n$ then~$\ell_1\neq\ell_2$. We shall
estimate~$\Cov(\X(j_1,\ell_1),\X(j_2,\ell_2))$. For simplicity,
put~$U_1=\X(j_1,\ell_1)$ and~$U_2=\X(j_2,\ell_2)$. We
have~$\Cov(\X(j_1,\ell_1),\X(j_2,\ell_2))
=\Cov(U_1,U_2)=\E(U_1U_2)-\E(U_1)\E(U_2)$.
We shall first estimate from above the value of~$\E(U_1U_2)$. Recall
that we write~$R$ for a random element of our probability
space~$\cR(n,p)$. We have
$$
\E(U_1U_2)=\sum_{R_0\subseteq[n]}U_1(R_0)U_2(R_0)\P(R=R_0). 
  \slabel{ExpProd}
$$ 
Let us say that~$R\in\cR(n,p)$ is {\deffont exceptional\/} if
either~$U_1(R)$ or~$U_2(R)$ is at least as large as~$\umax=\lfloor\log
n\rfloor$.  Standard inequalities for the tail of the binomial
distribution gives that the probability that~$R\in\cR(n,p)$ is
exceptional is no greater than~$n^{-(1/2)\log\log n}$. Since~$U_1$
and~$U_2$ are at most~$n$, we have that the exceptional~$R_0$
contribute with~$n^{2-(1/2)\log\log n}$ to the sum
in~{\eqnoExpProd}. In the sequel we concentrate our attention on
non-exceptional~$R\in\cR(n,p)$.

Let us introduce some notation. Let~$G_s$ ($s\in\{1,2\}$) be the
directed graph with vertex set~$[n]$ and edge set~$B^{\ell_s}(j_s)$.
Thus each~$G_s$ simply consists of some isolated edges. Moreover, the
directed graph~$G_1\cup G_2$ contains no cycle of length~$2$. 
Let~$H_s=H_s(R)$ ($s\in\{1,2\}$) be the random subgraph of~$G_s$
induced by the elements of~$R\in\cR(n,p)$, and put~$H=H(R)=H_1(R)\cup
H_2(R)\subseteq G_1\cup G_2$.

We now consider the structure of~$H$. Let us say that~$R\in\cR(n,p)$
is {\deffont typical\/} if~$H=H(R)$ is a matching.  The probability
that~$R\in\cR(n,p)$ is not typical is at most~$np^3\leq(\log\log
n)^{3/2}/\sqrt n$. Thus, the contribution of the atypical,
non-exceptional~$R_0\subseteq[n]$ in~{\eqnoExpProd} is at
most~$\umax^2(\log\log n)^{3/2}n^{-1/2}=O((\log n)^2(\log\log
n)^{3/2}n^{-1/2})$. From here onwards we only take into
account~$R\in\cR(n,p)$ that are typical and non-exceptional.
Thus~$H=H(R)$ will always consist of isolated edges.

To bound the contribution of the typical,
non-exceptional~$R_0\subseteq[n]$ to the sum in~{\eqnoExpProd}, we
shall need the following consequence of a large deviations inequality
of Janson, \L uczak, and Ruci\'nski~[J\L R~90]. Let~$J$ be a graph
with maximal degree at most~$2$, with~$\bar m$ edges, and~$n_2$
vertices of degree two. Let~$J^p$ be a random induced subgraph of~$J$
obtained by selecting its vertices randomly and independently each
with probability~$p$. Then the inequality of Janson, \L uczak and
Ruci\'nski gives that the probability that~$J^p$ has no edges is at
most~$\exp\{-{\bar m}p^2+2n_2p^3\}$. 

We are now ready to bound~$\E'(U_1U_2)=\sum
U_1(R_0)U_2(R_0)\P(R=R_0)$, where the sum is taken over all typical
and non-exceptional~$R_0\subseteq[n]$.  For~$s\in\{1,2\}$,
let~$m_s=|B^{\ell_s}(j_s)|$
and~$u_s=\lceil(1+\epsilon)m_sp^2\rceil$. Then~$\E'(U_1U_2)$ is at
most 
$$
\eqalign{
\sum_{u_1=r_1}^{\umax}u_1&\binom{m_1}{u_1}
                 \sum_{u_2=r_2}^{\umax}u_2\binom{m_2}{u_2}
                  p^{2u_1+2u_2}\exp(-(m_1+m_2-3u_1-3u_2)p^2+2np^3)\cr
&\le\sum_{u_1=r_1}^{\umax}u_1\binom{m_1}{u_1}p^{2u_1}(1-p^2)^{m_1-u_1} 
     \sum_{u_2=r_2}^{\umax}u_2\binom{m_2}{u_2}p^{2u_2}(1-p^2)^{m_2-u_2}\cr 
&\hskip6.5cm\times\exp(2\umax p^2+np^4+2np^3) \cr
&\leq(1+O(n^{-1/2}(\log\log n)^{3/2})\E(U_1)\E(U_2)\;.\cr
}
$$
Therefore
$$
\eqalign{
&\Cov(\hX(j_1,\ell_1),\hX(j_2,\ell_2))=\Cov(U_1,U_2)
    =\E(U_1U_2)-\E(U_1)\E(U_2)\cr
&\quad\qquad\leq n^{2-(1/2)\log\log n}+O(n^{-1/2}(\log n)^2(\log\log n)^{3/2})
                +O(n^{-1/2}(\log\log n)^{7/2})\cr
&\quad\qquad\qquad=O(n^{-1/2}(\log n)^2(\log\log n)^{3/2}). 
}
$$
Thus, 
$$
\eqalignno{
\Var(Z)
  &=\Var\Big(\sum_{\ell=1}^3\sum_{j=1}^{n-1}\X(j,\ell)\Big)
   =\sum_{\ell_1=1}^3\sum_{j_1=1}^{n-1}\sum_{\ell_2=1}^3\sum_{j_2=1}^{n-1}
           \Cov(\hX(j_1,\ell_1),\hX(j_2,\ell_2))\cr
  &\qquad\qquad=6nO(1)+9n^2O(n^{-1/2}(\log n)^3)=O(n^{3/2}(\log n)^3).\cr
}
$$
We now note that~{\eqnoExpXhat} and the trivial fact that
$$
\ble(r_0-1;m-1,p^2)\geq{m-1\choose r_0-1}p^{2(r_0-1)}(1-p^2)^{m-r_0} 
                   \geq\exp\{-3np^2\}
$$
implies that
$$
\E(Z)=\sum_{\ell=1}^3\sum_{j=1}^{n-1}\E\X(j,\ell)
    \geq n(n-1)p^2\exp\{-3np^2\}\geq C^2n/2(\log n)^3. 
$$
Thus~$\Var(Z)=o((\E(Z))^2)$ and, hence, from Chebyshev's inequality,
with probability tending to~$1$ as $n\to\infty$, we
have~$Z\leq2\E(Z)\leq2n^2p^2\exp(-\ep^2np^2/10)$. 
Thus~{\eqnoAimDiffGra} holds with probability tending to~$1$ as
$n\to\infty$ provided~$C^2\geq10\ep^{-2}\log(2/\eta)$.\qed

Lemmas~{\UnifCond} and~{\DiffGr} immediately imply that the difference
graph~$G_R=G_R(n)$ for a random subset~$R\in\cR(n,p)$ is
$\eta$-uniform, provided the probability~$p$ is large enough.

\proclaim{Fact~\FactC} For every~$0<\eta\leq1$ there exists a
constant~$C=C(\eta)$ such that, if~$p=p(n)\ge C/\sqrt n$
and~$R\in\cR(n,p)$, then the bipartite graph~$G_R=G_R(n)$ is
$\eta$-uniform with probability tending to~$1$ as~$n\to\infty$.\qed
\endproclaim  

\subheading{\S7. Proof of Theorem~\MainThmRM}

Let~$S$ be a subset of~$[n]=\{0,\dots,n-1\}$, where~$n$ is an odd
natural number.  Following Ruzsa and Szemer\'edi~[RSz~78] (see also
Erd\H os, Frankl and~R\"odl [EFR~86] and Graham and R\"odl~[GR~87]) we
introduce a graph~$G(n,S)$ that reflects the arithmetic structure
of~$S$. Thus, $G(n,S)$ is a tripartite graph whose vertex set consists
of three copies~$V_1$, $V_2$, $V_3$ of the set~$[n]$ and $\{i,j\}$ is
an edge of~$G(n,S)$ if and only if one of the following three
conditions holds: 
\roster
\item $i\in V_1$, $j\in V_2$ and $j=i\pl k$ for some $k\in S$,  
\item $i\in V_2$, $j\in V_3$ and $j=i\pl k$ for some $k\in S$, 
\item $i\in V_1$, $j\in V_3$ and $j=i\pl 2k$ for some $k\in S$, 
\endroster
where here and below~$\pl$ and~$\mn$ stand for addition and
subtraction modulo~$n$. Clearly, if~$k\in S$ then the vertices~$i\in
V_1$, $i\pl k\in V_2$ and~$i\pl2k\in V_3$ induce a triangle
in~$G(n,S)$. A triangle of~$G(n,S)$ of this type is said to be
{\deffont trivial\/}.  We are interested in the non-trivial, or
{\deffont spontaneous\/}, triangles of~$G(n,S)$, since they reflect
the arithmetic structure of~$S$ in the sense made precise below.

Clearly, each $G(n,S)$ contains precisely~$n|S|$ trivial triangles,
and in fact~$G(n,S)$ is the edge-disjoint union of those triangles.
More importantly, the number of spontaneous triangles in~$G(n,S)$
depends on the number of {\deffont arithmetic triples\/} in~$S$, that
is triples of {\it distinct\/} elements~$a$, $b$, and~$c\in S$ such
that $a\mn c =c\mn b$.  Indeed, for any arithmetic
triple~$\Delta=(a,b,c)$ and every~$i\in [n]$, the graph~$G(n,S)$
contains the associated spontaneous triangle with vertices~$i\in V_1$,
$i\pl a\in V_2$ and $i\pl a\pl b\in V_3$, and, conversely, any
spontaneous triangle is associated to such a pair~$(\Delta,i)$. Thus,
%%% I have changed the sentence slightly 
in order to verify whether $S$ contains an arithmetic triple it is 
enough to look for a spontaneous triangle in~$G(n,S)$.


Naturally, we shall be particularly interested in the structure
of~$G(n,R)$ for a random subset~$R$ of~$[n]$.  It will be later
crucial that, for a large random set~$R\subseteq[n]$, the
graph~$G(n,R)$ is typically uniform, and hence sparse, as show our
next two results.  In the sequel, it will be convenient to extend the
definition of $\eta$-uniformity to subsets of~$[n]$ in the obvious
way.  If~$S\subseteq[n]$ is such that~$G(n,S)$ is $\eta$-uniform for
some~$0<\eta\leq1$, then let us say that~$S$ itself is
{\deffont$\eta$-uniform\/}. Moreover, given~$b>2$ and~$0<\eta\leq1$,
we define the notion of $(b,\eta)$-sparseness for~$S$ above in the
analogous way.

\proclaim {Fact~\FactD} For every~$0<\eta\leq1$ there exists a
constant~$C=C(\eta)$ such that, if~$p=p(n)\geq C/\sqrt n$, then the
probability that~$R\in\cR(n,p)$ is $\eta$-uniform tends to~$1$
as~$n\to\infty$ along the odd integers.
\endproclaim
   
\demo{Proof} Since for odd~$n$ the graph~$G_{2R}=G_{2R}(n)$ may be
identified with~$G_{\bar R}=G_{\bar R}(n)$ for some~$\bar R\in
\cR(n,p)$, with the map~$R\mapsto{\bar R}$ measure preserving, the
assertion follows from Fact~{\FactC} and the definition
of~$G(n,R)$.\qed

 From Fact~{\FactD} one may deduce the following result concerning the
uniformity and sparseness of~$R_M\in\cR(n,M)$ for large~$M$.

\proclaim{Fact~\FactE} For every~$0<\eta\leq1$ there exists a
constant~$C=C(\eta)$ such that, if~$M=M(n)\ge C\sqrt n$, then the
probability that~$R\in\cR(n,M)$ is $\eta$-uniform and
$(4,\eta)$-sparse tends to~$1$ as~$n\to\infty$ along the odd
integers.
\endproclaim

\demo{Proof} We start by noticing that, for any~$0<\eta\leq1$,
if~$0<\eta_0\leq1$ is small enough, then for any~$S\subseteq[n]$ the
fact that the graph~$G=G(n,S)$ is $\eta_0$-uniform implies that~$G$
is, say, $(4,\eta)$-sparse. Therefore we proceed to show that for
any~$0<\eta_0\leq1$, if~$Cn^{1/2}\leq M=M(n)\leq n$ for some
sufficiently large constant~$C$, then~$G=G(n,R_M)$ is $\eta_0$-uniform
with probability~$1-o(1)$ as~$n\to\infty$ along the odd integers.

Pick~$\eta_1=\eta_0/6$ and~$\epsilon=\eta_1^2/3$.
Let~$C=(1+\epsilon)C_1$, where~$C_1=C(\eta_1)$ is as given by
Fact~{\FactD}.  and assume that~$C\sqrt n\leq M=M(n)\leq n$.
Set~$p=p(n)=M/(1+\epsilon)n$. We may generate~$R_M\in\cR(n,M)$ by
picking~$R_p\in\cR(n,p)$ conditioned on~$R_p$ satisfying~$|R_p|\leq
M$, and then by adding random elements of~$[n]\setminus R_p$ to~$R_p$
to obtain a set~$R_M$ of cardinality~$M$.  Since with
probability~$1-o(1)$ as~$n\to\infty$, we
have~$|R_p|\geq(1-\epsilon)pn$, we shall assume that our~$R_p$ does
satisfy this condition. Assume also that~$G=G(n,R_p)$ is
$\eta_1$-uniform, and recall that by Fact~{\FactD} this event also
holds with probability~$1-o(1)$. It now suffices to show that, under
these two conditions on~$R_p$, the set~$R_M$ is $\eta_0$-uniform
whatever elements were added to~$R_p$ to generate~$R_M$.

Write~$G_M$ for~$G(n,R_M)$ and~$G_p$ for~$G(n,R_p)$.  Let~$U$,
$W\subset V(G_M)$ be two disjoint sets contained in two distinct
vertex classes of~$G_M$ with~$|U|$,
$|W|\geq\eta_1n$. Put~$\rho_M=M/n$ and~$\rho_p=|R_p|/n$. Note that
then~$(1-2\epsilon)\rho_M\leq\rho_p\leq\rho_M$ and
that~$|\rho_p-p|\leq\epsilon p$. Moreover, we have
$$
e_{G_M}(U,W)\geq e_{G_p}(U,W)\geq(1-\eta_1)\rho_p|U||W|
\ge (1-2\eta_1)\rho_M|U||W|$$ 
and
$$
\eqalign{
e_{G_M}(U,W)\leq e_{G_p}(U,W)+2\epsilon pn|U|
       &\leq(1+\eta_1)\rho_p|U||W|+2(\epsilon p/\eta_1)|U||W|\cr 
         &\quad\leq(1+2\eta_1)\rho_p|U||W|\le (1+2\eta_1)\rho_M|U||W|. 
}
$$
Now notice that
$$
d_{G_M}(U,W)=3e_{G_M}(U,W)/\rho_M |U||W|\;
$$
and the density  between  two any sets of tripartition of $G(n,R_M)$ 
is~$3$.
Thus, 
$$
\left|d_{G_M}(U,W)-3\right|\leq{3|e_{G_M}(U,W)-\rho_M |U||W|\,|
\over \rho_M |U||W|} \le 6\eta_1=\eta_0\;,
$$
and so $G_M=G(n,R_M)$ is indeed $\eta_0$-uniform, as required.\qed 

In the sequel, it will be necessary for us to look at~$\cR(n,M)$ in a
way that it resembles a product of a large number of spaces.  Let us
assume that the integer~$m$ divides~$M$, and put~$M_0=M/m$. We then
define the space~$\tcR(n,m,M_0)$ as the uniform space of
$m$-tuples~$\tR=(R_i)_{i=1}^m$ of pairwise disjoint
$M_0$-subsets~$R_i\subseteq[n]$. Thus all
$m$-tuples~$\tR\in\tcR(n,m,M_0)$ are equiprobable, and the
map~$\tR=(R_i)_{i=1}^m\in\tcR(n,m,M_0)
\mapsto\bigcup_{i=1}^mR_i\in\cR(n,M)$ is measure-preserving. We shall
also consider the probability space~$\tcG=\tcG(n,m,M_0)$ of
the balanced $3$-decomposable $m$-edge-coloured
graphs $\tG=\tG(n,\tR)=(G_i)_{i=1}^m$ determined by the $G_i=G(n,R_i)$
($1\leq i\leq m$), where~$\tR=(R_i)_{i=1}^m$ is a
random element of~$\tcR(n,m,M_0)$. 
%(we shall also refer to an element of $\tcG(n,m,M_0)$ 
%as to a sequence of graphs $G_1,\dots,G_m$)
In this space we consider the event $\Cal A(b,\eta)$ that a graph from
$\tcG$ should be $(b,\eta)$-sparse, and denote the conditional
probability space obtained from $\tcG$ by conditioning on~$\Cal
A(b,\eta)$ by $\tcG(n,m,M_0 \cond b,\eta)$.

\proclaim{Lemma~\MainLemmaA} Let~$m\geq3$, $k_0\ge 1$, $b>4$,
$0<\xi\leq1$ and~$0<\delta\leq1$ be given. Then there exist
constants~$0<\epsilon=\epsilon(m,\xi,\delta)\leq1$
and~$C=C(m,k_0,b,\xi,\delta)$ for which the following holds for any
sufficiently large~$n$. Suppose~$Cn^{1/2}\leq M=mM_0=mM_0(n)\leq
n/(\log\log n)^2$, let $\tG=(G_i)_{i=1}^m\in\tcG(n,m,M_0\cond b,\eta)$
and let $\tPi_1,\dots,\tPi_m$ be the $(\ue,k_0)$-canonical sequence of
partitions associated to~$\tG$, where as usual~$\ue=\ue(m,b,\ep,k_0)$.
Then the probability that there exists a $(\delta,k_0,\ue;\tG)$-flower
which contains no spontaneous triangles is smaller than~$\xi^M$.
\endproclaim

\demo{Proof} Put~$\beta=\xi^{10^8m\delta^{-2}}$, and
let~$0<\epsilon=\epsilon(\beta)=\epsilon(m,\xi,\delta)\leq1$ be as
given by Lemma~{\IndSubgr}. Furthermore, let~$\eta$ and~$K_0\ge
1/2\ep$ be such that Lemma~{\MultiSSz} holds and let $C_1=C(\eta)$ be
as in Fact~{\FactE}.  Finally,
set~$C=\max\{C_1,10^7m\sqrt{K_0}/\delta\sqrt{\ep}\}$.  We shall show
that for such a choice of~$\epsilon$, $\eta$ and~$C$ the
assertion holds. We also remark that in the sequel we tacitly assume
that~$n$ is sufficiently large whenever it is needed.

Let us first restate our result in terms of $m$-coloured graphs
$\tG=(G_i)_{i=1}^m$ from $\tcG(n,m,M_0)$.  Let $\Cal B(\delta)$ be
the event that $\tG$ should be $(b,\eta)$-sparse and moreover it
should contain a $(\delta,k_0,\ue;\tG)$-flower without a spontaneous
triangle.  We have to show that
$$
\P(\Cal B(\delta)\cond\Cal A(b,\eta))\le \xi ^M\;.
$$
Suppose we show that 
$$
\P(\Cal B(\delta))\le \xi^M/2. \slabel{WotNot}
$$
Then, by our choice of~$C$, we have that for any large enough~$n$ we
have~$\P(\Cal A(b,\eta))>1/2$. Therefore 
$$
\P(\Cal B(\delta)\cond \Cal A(b,\eta))
  ={\P(\Cal B(\delta)\cap\Cal A(b,\eta))\over\P(\Cal A(b,\eta))}
  \le{\P(\Cal B(\delta))\over\P\Cal A(b,\eta))}
  \le\xi^M, 
$$
as required. Hence it only remains to prove~{\eqnoWotNot}. 

Let us estimate first the probability that a fixed
$(\delta,\tG)$-flower should contain no spontaneous triangle.
Thus, let the colours~$1\leq w(1)<w(2)<w(3)\leq m$, the vertex~$v\in
V(G)$, and the family~$\{(X^{(i)},Y^{(i)})\:1\leq i\leq g\}$, where
$$
u=|X^{(i)}|=|Y^{(i)}|\ge n/2K_0\;,
$$ 
and $2gu\ge \d n$, form a $(\delta,\tG)$-flower.  We may further
assume that all the~$X^{(i)}$ ($1\leq i\leq g'=\lceil g/2\rceil$) are
contained in a single vertex class of the tripartition of~$G$, as are
all the~$Y^{(i)}$ ($1\leq i\leq g'$). Below we shall only
consider~$X^{(i)}$ and~$Y^{(i)}$ for~$1\leq i\leq g'$. Also, let us
mention for completeness that~$G$ has~$3n$ vertices
and~$e(G)=|E(G)|=3nM=3nmM_0$ edges. 

Let us now suppose that the~$R_i$ ($1\leq i<w(2)$) have been chosen.
Thus, in particular, the graphs~$H_i=G_{w(1)}[X^{(i)},Y^{(i)}]$
($1\leq i\leq g'$), namely the bipartite subgraphs of~$G_{w(1)}$ with
bipartition~$V(H_i)= X^{(i)}\cup Y^{(i)}$ and edge
set~$E_{G_{w(1)}}(X^{(i)},Y^{(i)})$, have been fixed. By the
definition of a $(\delta,\tG)$-flower, each~$H_i$ ($1\leq i\leq g'$)
is $\epsilon$-uniform, and for all $1\le i\le g'$ we have
$e(H_i)=e_{G_{w(1)}}(X^{(i)},Y^{(i)})\geq\rho_0u^2$,
where~$\rho_0=10^{-6}\d M_0/n$.

Let us now pick~$R_{w(2)}$, and let us study the
neighbourhood~$N^{(i)}_{w(2)}(v)\subset X^{(i)}$ ($1\leq i\leq g'$) of
the vertex~$v$ in the graph~$G_{w(2)}$ inside the set~$X^{(i)}$.
Put~$d=\rho_0u$.  Again by the definition of a $(\delta,\tG)$-flower,
we know that~$d^{(i)}_1=|N^{(i)}_{w(2)}(v)|\geq d=\rho_0u$. Now let us
condition on the values of the~$d^{(i)}_1$ ($1\leq i\leq g'$).  Once
these~$g'$ numbers are fixed, for every~$1\leq i\leq g'$, all the
subsets of cardinality~$d^{(i)}_1$ of the set~$X^{(i)}\setminus
S^{(i)}_1$ are equally likely to be chosen as~$N^{(i)}_{w(2)}(v)$,
where~$S^{(i)}_1$ is the neighbourhood of~$v$ within~$X^{(i)}$ in the
graph~$\bigcup_{1\leq k<w(2)}G_k$. Furthermore, we make the simple but
important observation that, because we choose~$R_{w(2)}$ randomly and
uniformly from all the $M_0$-subsets of~$[n]\setminus\bigcup_{1\leq
  k<w(2)}R_k$, and because we have decided on the
cardinalities~$d^{(i)}_1$ ($1\leq i\leq g'$) in advance, the
sets~$N^{(i)}_{w(2)}(v)$ $(1\leq i\leq g')$ are all selected
independently.

Let us now suppose that the~$R_i$ ($w(2)\leq i<w(3)$) have also been
chosen, and pick~$R_{w(3)}$.  Let~$N^{(i)}_{w(3)}(v)\subset Y^{(i)}$
be the $G_{w(3)}$-neighbourhood of~$v$ within~$Y^{(i)}$.
Put~$d^{(i)}_2=|N^{(i)}_{w(3)}(v)|$ ($1\leq i\leq g'$), and note that
again~$d^{(i)}_2\geq d=\rho_0u$. We now condition on the values of
the~$d^{(i)}_2$ ($1\leq i\leq g'$).  As above, under this
conditioning, for every~$1\leq i\leq g'$, all the subsets of
cardinality~$d^{(i)}_2$ of the set~$Y^{(i)}\setminus S^{(i)}_2$ are
equally likely to be chosen as~$N^{(i)}_{w(3)}(v)$, where~$S^{(i)}_2$
is the neighbourhood of~$v$ within~$Y^{(i)}$ in the
graph~$\bigcup_{1\leq k<w(3)}G_k$. As before, the
sets~$N^{(i)}_{w(3)}(v)$ $(1\leq i\leq g')$ are all selected
independently.

We now apply Lemma~{\IndSubgr} to all the~$H_i$ ($1\leq i\leq g'$).
Recall that~$d=\rho_0u$ and notice that, for all~$1\leq i\leq
g'$, the density~$e(H_i)u^{-2}$ of~$H_i$ is at least~$\rho_0=d/u$
and~$d^{(i)}_j\geq d$ ($j\in\{1,2\}$). Also, by the choice of~$C$, we
have that~$d\geq2(u/\epsilon)^{1/2}$.  Moreover, since~$M=mM_0\leq
n/(\log\log n)^2$, for large enough~$n$ we have that~$|S^{(i)}_j|\leq
u/\log\log u$ for all~$1\leq i\leq g'$, $j\in\{1,2\}$. We now recall
that the sets~$N^{(i)}_{w(2)}(v)$ $(1\leq i\leq g')$ are all selected
independently, as are all the~$N^{(i)}_{w(3)}(v)$ $(1\leq i\leq g')$.
Thus, applying Lemma~{\IndSubgr} simultaneously to all the~$H_i$
($1\leq i\leq g'$), we see that the probability that we do not have a
spontaneous triangle in~$G$ is at most~$\beta^{dg'}\le \xi^{2M}$.

Now, to complete the proof, it suffices to estimate the number of all
possible candidates for $(\d,\tG)$-flowers in our $(b,\eta)$-sparse
$m$-edge-coloured graph~$\tG$. Clearly, the vertex $v$ can be selected
in at most $n$ ways, there are at most ${m\choose 3}\le m^3$ possible
choices for the indices $w(1)$, $w(2)$ and $w(3)$ and, since
$|\tPi_{w(1)}|\leq K_0+1$ (cf.~Lemma~{\MultiSSz})
and~$g\leq(|\tPi_{w(1)}|-1)/2<K_0$, the number of possible choices
for the set of pairs $\{(X^{(i)},Y^{(i)})\:1\leq i\leq g\}$ can be
estimated very generously by $K_0\times K_0!\leq(K_0+1)!$. Thus, since
$M$ grows to infinity at least as fast as $ \sqrt n$, we have
$$
\P(\Cal B(\delta))\le nm^3(K_0+1)!\xi^{2M}\le \xi^M/2
$$
whenever $n$ is large enough. Thus~{\eqnoWotNot} holds and
Lemma~{\MainLemmaA} is proved.\qed 

As an almost immediate consequence of the above lemma and
Lemma~{\FlowerLemma}, we get the following result, which will be
crucial for the proof of Theorem~{\MainThmRM}.

Let~$\cR(n,M\cond b,\eta)$ denote the uniform probability space whose
elements are the $(b,\eta)$-sparse $M$-subsets~$R$ of~$[n]$. Clearly,
$\cR(n,M\cond b,\eta)$ may be obtained from~$\cR(n,M)$ by conditioning
on the event that~$G(n,R)$ should be~$(b,\eta)$-sparse.  Let the
associated probability space of the~$G(n,R)$ ($R\in\cR(n,M\cond
b,\eta)$) be denoted by~$\G(n,M\cond b,\eta)$.  Thus to pick an
element~$G$ from~$\G(n,M\cond b,\eta)$ we simply
generate~$R\in\cR(n,M\cond b,\eta)$ and let~$G=G(n,R)$. Suppose the
integer~$m$ divides~$M$.  Clearly, since all graphs from $\G(n,M\cond
b,\eta)$ are generated by $M$-subsets of $[n]$ and each such subset
can be decomposed into $m$ subsets of size $M_0=M/m$ in the same
number of ways, one can generate an element of $\G(n,M\cond b,\eta)$
by choosing a graph from $\tcG(n,m,M_0\cond b,\eta)$ and ignoring the
colouring of its edges.

Now our next result can be stated as follows. 

\proclaim{Lemma~\MainLemmaB} For every~$b\geq4$ and~$0<\xi\leq1$,
there exist constants~$0<\eta(b,\xi)\leq1$, $C=C(b,\xi)$,
and~$N=N(b,\xi)$ such that, for every~$n\ge N$ and~$C\sqrt n\leq
M=mM_0=mM_0(n)\leq n/(\log\log n)^2$, where~$m=m(b)$ is as given in
Lemma~{\FlowerLemma}, the probability that~$G\in\G(n,M\cond b,\eta)$
contains no spontaneous triangle is at most~$\xi^M$.
\endproclaim

\demo{Proof} Let~$b\geq4$ and~$0<\xi\leq1$ be given.
Choose~$m=m(b)\geq3$, $0<\delta=\delta(b)\leq1$ and~$k_0=k_0(b)\geq1$
as in Lemma~{\FlowerLemma}, and
let~$0<\epsilon=\epsilon(m,\xi,\delta)\leq1$ be as in
Lemma~{\MainLemmaA}.  Finally, let $0<\eta=\eta(b,\epsilon)\leq1$ be
as given by Lemma~{\FlowerLemma}, and let~$C=C(m,k_0,b,\xi,\delta)$ be
as given by Lemma~{\MainLemmaA}.  As always, we shall always assume
that~$n$ is sufficiently large whenever it is needed.

Let us now observe that, because of the choice of~$m$, $k_0$,
and~$\delta$, every element of $\tcG(n,m,M_0\cond b,\eta)$ contains a
$(\ue(m,b,\ep,k_0),k_0)$-flower and, because of Lemma~{\MainLemmaA},
with probability at least $1-\xi^M$ every such flower must contain a
spontaneous triangle. Thus the probability that an element of
$\tcG(n,m,M_0\cond b,\eta)$ should contain no spontaneous triangle is
smaller than $\xi^M$. As we have already mentioned, the graphs from
$\tcG(n,m,M_0 \cond b,\eta)$ naturally correspond to elements from
$\G(n,mM_0 \cond b,\eta)$, and hence Lemma~{\MainLemmaB}
follows.\qed

We may now finally prove Theorem~{\MainThmRM}. 

\demo{Proof of Theorem~\MainThmRM} Clearly, it suffices to prove that,
for any given~$0<\alpha\leq1$, there is a suitable choice
for~$C=C(\alpha)$ such that

\roster
\item"(\ddd)" {\sl if~$Cn^{1/2}\leq M=M(n)\leq n$,
  then~$\lim_{n\to\infty} \P(R\to_\alpha3)=1$, where \newline 
the limit is  taken along {\it odd\/} values of~$n$.\sl} 
\endroster

Thus henceforth we may and shall assume that~$n$ is odd.
Also, below we assume that~$n$ is sufficiently large whenever it is
needed.  For convenience, let us say that a property holds {\deffont
almost surely\/} if it holds with probability tending to~$1$ as~$n$
tends to infinity along odd integers.

Let a constant~$0<\alpha\leq1$ be given, and assume that~$1\leq
M=M(n)\leq n$.  Note that the Heath-Brown--Szemer\'edi result
mentioned in~\S0 implies that {\it any\/} set~$A\subset[n]$
with~$|A|\geq n/(\log\log n)^2$ contains a $3$-term arithmetic
progression provided~$n$ is sufficiently large.  Thus we may and shall
assume that~$\alpha M\leq n/(\log\log n)^2$, since
otherwise~$R\to_\alpha3$ for any set~$R\subseteq[n]$ with~$|R|=M$.

Let us put~$\alpha'=\alpha/2$.  Set~$b=6/\alpha'\geq4$
and~$0<\xi=\alpha'/4\leq1$, and let~$m=m(b)\geq3$ be as given in
Lemma~{\FlowerLemma}.  Moreover, let~$0<\eta=\eta(b,\xi)\leq1$
and~$C_1=C(b,\xi)$ be as given in Lemma~{\MainLemmaB}, and
let~$C_2=C(\eta)$ be as given in Fact~{\FactE}.  We
let~$C=C(\alpha')=\max\{(4/3\alpha')C_1,C_2\}$.  We shall now show
that~(\ddd) holds with this choice of~$C$.

Our first aim is to verify that~$R\in\cR(n,M)$ almost surely has the
property that any subset~$A'\subseteq R$ with at least~$\alpha'|R|$
elements contains an arithmetic triple. For simplicity, let us
write~$R\to_{\alpha'}'3$ if~$R$ has this property. 

Let us start by picking an integer multiple~$M'=M'(n)$ of~$m$ such
that~$(3\alpha'/4)M\leq M'\leq\alpha' M$ holds for any sufficiently
large~$n$. Put~$M_0=M_0(n)=M'/m$. We now consider the
spaces~$\cR(n,M'\cond b,\eta)$ and~$\G(n,M'\cond b,\eta)$. Note
that~$C_1n^{1/2}\leq M'=mM_0\leq n/(\log\log n)^2$, and hence that by
Lemma~{\MainLemmaB} the probability that~$G\in\G(n,M'\cond b,\eta)$
contains no spontaneous triangle is at most~$\xi^{M'}$.  Thus, the
probability that~$R\in\cR(n,M'\cond b,\eta)$ contains no arithmetic
triple is at most~$\xi^{M'}$ for all large enough~$n$. Therefore, the
number of $(b,\eta)$-sparse 
%%% I have just remove all $M'$-subsets
subsets~$A'$ of~$[n]$ with $M'$ elements that  do not
contain arithmetic triples is at most~$\xi^{M'}{n\choose M'}$.

Let~$\Cal D$ be the event that~$R\in\cR(n,M)$ should contain a
$(b,\eta)$-sparse subset~$A'$ with $M'$ elements which is 
free of arithmetic triples. Then
the probability that~$\Cal D$ holds is at most
$$
\xi^{M'}{n\choose M'}{n-M'\choose M-M'}{n\choose M}^{-1}
  \leq\(\e\xi n\over M'\)^{M'}\(M\over n\)^{M'}
  \leq\(4\e\xi\over3\alpha'\)^{M'}=o(1). 
$$ 
Let now~$\cS$ be the event that~$R\in\cR(n,M)$ should be
$(4,\eta)$-sparse. Then, by Fact~{\FactE}, we have that almost
surely~$\cS$ holds. We now note that if~$R$ is $(4,\eta)$-sparse, then
any subset~$A'\subseteq R$ with~$|A'|=M'$ is $(b,\eta)$-sparse.
Therefore, if~$\Cal D$ fails and~$\cS$ holds, then~$R\to_{\alpha'}'3$.
Since almost surely~$\Cal D$ does fail and~$\cS$ does hold, we conclude
that a random set~$R\in\cR(n,M)$ satisfies~$R\to_{\alpha'}'3$ almost
surely.

Now recall that~$n$ is odd, and write~$n=2k+1$. Observe that if~$A$ is
a subset of~$R$ with at least~$\al|R|$ elements, then at least one of
the subsets~$A_1=A\cap\{0,\dots,k\}$ and~$A_2=A\cap \{k,\dots,2k\}$
must have at least~$\alpha'|R|=\al|R|/2$ elements, and that~$A_i$
($i\in\{1,2\})$ contains an arithmetic triple if and only if it
contains an arithmetic progression of length three. Thus~(\ddd) does
hold and Theorem~{\MainThmRM} is proved.\qed

Corollary~{\SparseCor} may be deduced from Theorem~{\MainThmRM} in a
routine manner. 

\demo{Sketch of the Proof of Corollary~{\SparseCor}} Let~$s=s(n)$,
$g=g(n)$, and $\alpha$ be as in the statement of our corollary.
Pick~$C_0$ sufficiently large so that with~$p=p(n)=C_0n^{-1/2}$
and~$R=R_p\in\cR(n,p)$ we have~$R\to_{\alpha/2}3$ with
probability~$1-o(1)$ as~$n\to\infty$.

The probability that a fixed set as in~(i) of the corollary meets~$R$
in more than~$3$ elements is~$O(s^4n^{-2})$. Hence the expected number
of such sets is~$O(s^4)=o(\sqrt n)$.  The probability that a fixed set
as in~(ii) meets~$R$ in more than~$Cm/\sqrt n$ elements is at
most~$\exp\{-2m/\sqrt n\}$ for large enough~$C$. Therefore the
probability that such a set exists is~$o(1)$.
  Now, let~$G^{(3)}=G^{(3)}_n$ be the $3$-uniform hypergraph
on~$[n]$ whose hyperedges are the $3$-term arithmetic progressions
contained in~$[n]$. One can easily check that for every $\ell\ge 2$
the number of cycles of length~$\ell$ in~$G^{(3)}$
is at most~$(3n)^\ell$. For any such cycle of~$G^{(3)}$ the probability that
it appears in~$\cF=\cF(R)$ is~$p^{2\ell}$. Therefore the expected number
of cycles in~$\cF$ shorter than $g$ is 
at most~$\sum_{\ell=2}^g(3np^2)^\ell = o(\sqrt n)$. 

In view of the above remarks, with probability~$1-o(1)$
as~$n\to\infty$, there exists a set~$S\subseteq R$
with~$|S|\geq|R|/2$ satisfying~(i), (ii), and~(iii).
Finally, note that if~$R\to_{\alpha/2}3$, then~$S\to_\alpha3$.\qed 

\Refs

\ref
\no ADLRY~94
\by Alon, N., Duke, R.A., Lefmann, H., R\"odl, V. and Yuster, R. 
\paper The algorithmic aspects of the regularity lemma 
\jour J.~Algorithms
\vol 16
\yr 1994
\pages 80--109
\endref

\ref
\no EFR~86
\by Erd\H os, P., Frankl, P. and R\"odl, V.
\paper The asymptotic number of graphs not containing a fixed subgraph
       and a problem for hypergraphs having no exponent
\jour Graphs Combin.
\vol 2
\yr 1986
\pages 113--121
\endref

\ref
\no ET~36
\by Erd\H os, P. and Tur\'an, P.
\paper On some sequences of integers
\jour J. London Math. Soc.
\vol 11 %,2
\yr 1936
\pages 261--264
\endref

\ref
\no FRW~88
\by Frankl, P., R\"odl, V. and Wilson, R.
\paper The number of  submatrices of a given type 
in a Hadamard matrix and related results
\jour J. Combin. Th. B
\vol 44%,3
\yr 1988
\pages 317--328
\endref

\ref\no Fu~77
\by Furstenberg, H.
\paper Ergodic behaviour of diagonal measures and a theorem 
of Szemer\'edi on arithmetic progressions
\jour J. Analyse Math.
\vol 31
\yr1977
\pages204--256
\endref

\ref\no GN~86
\by Graham, R.L. and Ne\v set\v ril, J.
\paper Large minimal sets which force long arithmetic progressions 
\jour J. Combin. Th. A
\vol42
\yr1986
\pages270--276
\endref

\ref
\no GR~87
\by Graham, R.L. and R\"odl, V.
\paper Numbers in Ramsey theory
\inbook Surveys in Combinatorics 1987
\bookinfo (Whitehead, C., ed.), 
          London Mathematical Society Lecture Note Series 123 
\publ Cambridge University Press 
\publaddr Cambridge
\yr1987 
\pages111--153
\endref

\ref
\no HK\L~$\star\star$
\by Haxell, P.E., Kohayakawa, Y. and \L uczak, T. 
\paper The induced size-Ramsey number of cycles
\paperinfo Combin. Probab. Comput., to appear
\endref

\ref
\no H-B~87
\by Heath-Brown, D.R. 
\paper Integer sets containing no arithmetic progressions
\jour J. London Math. Soc.
\vol 35 %,2
\yr 1987
\pages 385--394
\endref

\ref\no J\L R~90
\by Janson, S., \L uczak, T. and Ruci\'nski, A.
\paper An exponential bound for the probability of nonexistence of a
       specified subgraph in a random graph
\inbook Random Graphs~'87
\bookinfo (Karo\'nski, M., Jaworski, J. and Ruci\'nski, A., eds)
\publ Wiley
\yr1990
\pages73--87
\endref

\ref\no McD~89
\by McDiarmid, C.J.H.
\paper On the method of bounded differences
\inbook Surveys in Combinatorics 1989
\bookinfo (Siemons, J., ed.), 
          London Mathematical Society Lecture Notes Series 141 
\publ Cambridge University Press
\publaddr Cambridge
\yr1989
\pages148--188
\endref

\ref\no NR~87
\by  Ne\v set\v ril, J. and R\"odl, V.
\paper Partite construction and Ramseyan theorems 
       for sets, numbers and spaces
\jour Comm.\ Math.\ Univ.\ Carol.
\vol 28  %(3) 
\yr 1987
\pages 569-580
\endref


\ref
\no PV~88
\by Pr\"omel, H.-J. and Voigt, B.
\paper A sparse Graham--Rothschild theorem
\jour Trans. Amer. Math. Soc. 
\vol309
\yr1988
\pages113--137
\endref

\ref
\no R\"o~90
\by R\"odl, V.
\paper On Ramsey families of sets
\jour Graphs Combin.
\vol6
\yr1990
\pages187--195
\endref

\ref
\no Ro~53
\by Roth, K.F.
\paper On certain  sets of integers
\jour J. London Math. Soc.
\vol 28
\yr 1953
\pages 104--109
\endref

\ref
\no RSz~78
\by Ruzsa, I.Z. and Szemer\'edi, E. 
\paper Triple systems with no six points carrying three triangles
\jour Colloq.\ Math.\ Soc.\ J.\ Bolyai
\vol 18
\yr 1978
\pages 939--945
\endref

\ref
\no Sp~75
\by Spencer, J.
\paper Restricted Ramsey configurations 
\jour J. Combin. Th. A
\vol19
\yr1975
\pages278--286
\endref

\ref
\no Sz~75
\by Szemer\'edi, E.
\paper On sets of integers containing no $k$
elements in arithmetic progression
\jour Acta Arith.
\vol 27
\yr1975
\pages299--345
\endref

\ref
\no Sz~78
\by Szemer\'edi, E.
\paper Regular partitions of graphs 
\inbook Probl\`emes Combinatoires et Th\'eorie des Graphes, %
        Proc. Colloque Inter. CNRS 
\publ  (Bermond, J.-C., Fournier, J.-C., Las Vergnas, 
        M., Sotteau, D., eds), CNRS
\publaddr Paris
\yr1978
\pages399--401
\endref

\ref
\no Th~87a
\by Thomason, A.
\paper Pseudo-random graphs
\inbook Random Graphs~'85
\bookinfo (Karo\'nski, M., Palka, Z., eds), 
          Annals of Discrete Math.~{\bf 33} 
\publ North-Holland
\publaddr Amsterdam
\yr1987 
\pages307--331
\endref

\ref
\no Th~87b
\by Thomason, A.
\paper Random graphs, strongly regular graphs and pseudo-random graphs
\inbook Surveys in Combinatorics 1987
\bookinfo (Whitehead, C., ed.), 
          London Mathematical Society Lecture Note Series 123 
\publ Cambridge University Press 
\publaddr Cambridge
\yr1987 
\pages173--195
\endref

\enddocument


