%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% AmSTeX file for the paper
%
% ON $K^4$-FREE SUBGRAPHS OF RANDOM GRAPHS
%
% by Y. Kohayakawa, T. \L uczak, and V. R\"odl
%
% Version of 29 August 1995
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\magnification=\magstephalf
\input amstex
\documentstyle{amsppt}
\refstyle{C}
%
% refdef
%
\newcount\refno\refno=1
\def\referencelabel{\number\refno} 
\def\newrefno{\advance\refno by1}
%
\edef\refnoBSS
{\referencelabel}\newrefno
\def\refBSS{{\bf[\refnoBSS]}}
\edef\refnoEGT
{\referencelabel}\newrefno
\def\refEGT{{\bf[\refnoEGT]}}
\edef\refnoBBrgs
{\referencelabel}\newrefno
\def\refBBrgs{{\bf[\refnoBBrgs]}}
\edef\refnoChung
{\referencelabel}\newrefno
\def\refChung{{\bf[\refnoChung]}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\edef\refnoErdos
%{\referencelabel}\newrefno
%\def\refErdos{{\bf[\refnoErdos]}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\edef\refnoFR
{\referencelabel}\newrefno
\def\refFR{{\bf[\refnoFR]}}
\edef\refnoFu
{\referencelabel}\newrefno
\def\refFu{{\bf[\refnoFu]}}
\edef\refnoHKL
{\referencelabel}\newrefno
\def\refHKL{{\bf[\refnoHKL]}}
\edef\refnoHKLodd
{\referencelabel}\newrefno
\def\refHKLodd{{\bf[\refnoHKLodd]}}
\def\refnbHKLodd{{\bf\refnoHKLodd}}
\edef\refnoHKLeven
{\referencelabel}\newrefno
\def\refHKLeven{{\bf[\refnoHKLeven]}}
\def\refnbHKLeven{{\bf\refnoHKLeven}}
\edef\refnoJanson
{\referencelabel}\newrefno
\def\refJanson{{\bf[\refnoJanson]}}
\edef\refnoKKS
{\referencelabel}\newrefno
\def\refKKS{{\bf[\refnoKKS]}}
\edef\refnoKLRap
{\referencelabel}\newrefno
\def\refKLRap{{\bf[\refnoKLRap]}}
\edef\refnoRRa
{\referencelabel}\newrefno
\def\refRRa{{\bf[\refnoRRa]}}
\def\refnbRRa{{\bf\refnoRRa}}
\edef\refnoRRb
{\referencelabel}\newrefno
\def\refRRb{{\bf[\refnoRRb]}}
\def\refnbRRb{{\bf\refnoRRb}}
\edef\refnoSz
{\referencelabel}\newrefno
\def\refSz{{\bf[\refnoSz]}}
%
% Journals
%
\def\BLMS{Bull. London Math. Soc.}
\def\BAMS{Bull. Amer. Math. Soc.}
\def\CPC{Combinatorics, Probability, and Computing}
\def\JAMS{J. Amer. Math. Soc.}
\def\JLMS{J. London Math. Soc.}
\def\PLMS{Proc. London Math. Soc.}
\def\JCT{J. Combinatorial Theory}
\def\JCTA{J. Combinatorial Theory, {\rm Series~A}}
\def\JCTB{J. Combinatorial Theory, {\rm Series~B}}
\def\JGT{J. Graph Theory}
\def\Comb{Combinatorica}
\def\AMASH{Acta Math. Acad. Sci. Hungar.}
\def\SSMH{Studia Sci. Math. Hung.}
\def\EJC{Europ. J. Combinatorics}
\def\GC{Graphs and Combinatorics}
\def\IJM{Israel J. Math.}
\def\DM{Discrete Math.}
\def\ADM{Ann. Discrete Math.}
\def\TAMS{Trans. Amer. Math. Soc.}
\def\PAMS{Proc. Amer. Math. Soc.}
\def\PMH{Periodica Math. Hungar.}
\def\PCPS{Proc. Cambridge Phil. Soc.}
\def\MPCPS{Math. Proc. Cambridge Phil. Soc.}
\def\RSA{Random Structures and Algorithms}
% Authors
\def\Aj{Ajtai, M.}
\def\Al{Alon, N.}
\def\Be{Beck, J.}
\def\BB{Bollob\'as, B.}
\def\Chung{Chung, F.R.K.}
\def\Er{Erd\H os, P.}
\def\Fr{Frankl, P.}
\def\Fu{F\"uredi, Z.}
\def\Gra{Graham, R.L.}
\def\Ka{Katona, G.O.H.}
\def\Kl{Kleitman, D.J.}
\def\Ko{Koml\'os, J.}
\def\Lo{Lov\'asz, L.}
\def\Ne{Ne\v set\v ril, J.}
\def\Po{P\'osa, L.}
\def\Ro{R\"odl, V.}
\def\Sey{Seymour, P.}
\def\Sh{Shearer, J.B.}
\def\Si{Simonovits, M.}
\def\So{S\'os, V.T.}
\def\Sp{Spencer, J.H.}
\def\Sz{Szemer\'edi, E.}
\def\Tur{Tur\'an, P.}
\def\Tutte{Tutte, W.T.}
\def\Tu{Tuza, Zs.}
%
% statems
%
\newcount\statemno\statemno=1
\def\newstatemno{\advance\statemno by1}
\def\statementlabel{\number\statemno} %new command
%
% intro
%
\edef\MainConj
{\statementlabel}\newstatemno
\edef\MainThm
{\statementlabel}\newstatemno
\edef\GnMversion
{\statementlabel}\newstatemno
%
% sec1
%
\edef\SSzp 
{\statementlabel}\newstatemno
\edef\MinDegree
{\statementlabel}\newstatemno
\edef\Hyper
{\statementlabel}\newstatemno
%
% sec21
%
\edef\CountLemma
{\statementlabel}\newstatemno
\edef\FaultyVx
{\statementlabel}\newstatemno
\edef\CountLemmaCor
{\statementlabel}\newstatemno
%
% sec22
%
\edef\TrigUpBd
{\statementlabel}\newstatemno
\edef\TUBa
{\statementlabel}\newstatemno
\edef\TUBYxy
{\statementlabel}\newstatemno
\edef\TUBXwdash
{\statementlabel}\newstatemno
\edef\TrigUpBdB
{\statementlabel}\newstatemno
%
% sec31
%
\edef\WeightedTu
{\statementlabel}\newstatemno
%
% sec32
%
\edef\MainLemma
{\statementlabel}\newstatemno
\edef\ProhiA
{\statementlabel}\newstatemno
%
% sec4
%
\edef\NearMainThm
{\statementlabel}\newstatemno
\edef\Monotone
{\statementlabel}\newstatemno
\edef\Equivalence
{\statementlabel}\newstatemno
%
% sec5
%
\edef\MainDetThm
{\statementlabel}\newstatemno
\edef\DetCor
{\statementlabel}\newstatemno
%
% sec6
%
\edef\TechConj
{\statementlabel}\newstatemno
%
% standard macros 
%
\hoffset=1.2truecm
\overfullrule=0pt
\def\({\left(}
\def\){\right)}  
\def\[{\left[}
\def\]{\right]}
\def\<{\langle}
\def\>{\rangle}
\def\e{{\text{\rm e}}}
\let\epsilon=\varepsilon
\let\phi=\varphi
\def\deffont{\it}
%
% equation label macros
%
\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})}
%
% further proclaim type macros
%
\def\endclaim{\egroup\par\ifdim\lastskip<\smallskipamount
                \removelastskip\penalty20\smallskip\fi}
\long\def\claim{\smallbreak\noindent  
  {\it Claim.\enspace}\ignorespaces\bgroup\sl}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\def\endassertion{\egroup\par\ifdim\lastskip<\smallskipamount
%                \removelastskip\penalty20\smallskip\fi}
%\def\endassertionsquare{{\unskip\nobreak\hfil\penalty50
%  \hskip2em\hbox{}\nobreak\hfil\square
%    \parfillskip0pt\finalhyphendemerits=0\par}%
%    \egroup\par\ifdim\lastskip<\smallskipamount
%                \removelastskip\penalty20\smallskip\fi}
\long\def\oldassertion(#1){\smallbreak\noindent 
  {\rm(}{#1}{\rm)}\enspace\ignorespaces\bgroup\sl}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\endassertion{\egroup\par\ifdim\lastskip<\smallskipamount
                \removelastskip\penalty20\smallskip\fi}
\def\endassertionsquare{{\unskip\nobreak\hfil\penalty50
  \hskip2em\hbox{}\nobreak\hfil\square
    \parfillskip0pt\finalhyphendemerits=0\par}%
    \egroup\par\ifdim\lastskip<\smallskipamount
                \removelastskip\penalty20\smallskip\fi}
\long\def\assertion(#1){\smallbreak\noindent 
  {\it Assertion~{#1}.\/}\ \ignorespaces\bgroup\sl}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\endcase{\par\ifdim\lastskip<\smallskipamount
  \removelastskip\penalty3000\smallskip\fi}
\def\case#1.{\smallbreak\noindent 
  {\sl Case\/} #1.\enspace\ignorespaces}
\def\casenodot#1 {\smallbreak\noindent 
  {\sl Case\/} #1\enspace\ignorespaces}
\def\endcasebody{\par\ifdim\lastskip<\smallskipamount
                \removelastskip\penalty-20\smallskip\fi}
\outer\def\endcasebodysquare{{\unskip\nobreak\hfil\penalty50
         \hskip2em\hbox{}\nobreak\hfil\square
         \parfillskip0pt\finalhyphendemerits=0\par}% TeXbook, p 106.
  {\ifdim\lastskip<\smallskipamount\removelastskip\penalty-10\smallskip\fi}}
\def\casebody{\noindent\ignorespaces}
\let\proofofassertion=\casebody
\let\endproofofassertion=\endcasebody
\let\endproofofassertionsquare=\endcasebodysquare
\def\proofoftheclaim{\proofofassertion{\it Proof of the Claim\/}.\enspace}
\let\endproofoftheclaim=\endproofofassertion
%
%
%
\def\gammaarrow{{\displaystyle
  \mathrel{\mathop{\longrightarrow}\limits^{\hbox{\sevenrm ind}}
                                          _\gamma}}}
%\def\indarrow{{\displaystyle
%  \mathrel{\mathop{\longrightarrow}\limits^{\hbox{\sevenrm ind}}}}}
\def\GammaJ{\Gamma_J}
\def\P{{\Bbb P}}
\def\Z{{\Bbb Z}}
%
% new macros
%
\def\:{{:}\;}
\def\cond{\,\big|\,}
\def\bigcond{\,\bigg|\,}
%\def\cond{{\mathrel{\mathop|}}}
\def\cG{{\Cal G}}
\def\cF{{\Cal F}}
\def\cB{{\Cal B}}
\def\cU{{\Cal U}}
\def\E{{\Bbb E}}
\def\ba{{\bold a}}
\def\bb{{\bold b}}
\def\bd{{\bold d}}
\def\ff{{\bold f}}
\def\bg{{\bold g}}
\def\tbf{\tilde{\bold f}}
\def\tbg{\tilde{\bold g}}
\def\bfG{{\bold G}}
\def\tW{{\widetilde W}}
\def\kp#1{k_{#1}^{\text{\rm p}}} 
\def\dY{d^Y}
\def\dGp{d_{G,p}}
\def\dHp{d_{H,p}}
\def\dJp{d_{J,p}}
\def\dFp{d_{F,p}}
\def\dHrp{d_{H_r,p}}
\def\dHr{d_{H_r}}
\def\dGnp{d_{G_p}}
\def\bfx{{\bold x}}
\def\GammaGp{\Gamma_{G_p}}
\def\Bi{\mathop{\text{\rm Bi}}\nolimits}
\def\ex{\mathop{\text{\rm ex}}\nolimits}
%\def\supp{\mathop{\text{\rm supp}}\nolimits}
\def\bS{{\bar S}}
\def\bV{{\bar V}}
\def\bU{{\bar U}}
\def\bZ{{\bar Z}}
\def\tm{{\widetilde m}}
\def\bH{{\bar H}}
\def\bF{F}
\def\Hstar{{H_*}}
\def\tV{{\widetilde V}}
\def\bfV{{\bold V}}
\def\bfm{{\bold m}}
\def\A{{\Cal A}}
\def\cS{{\Cal S}}
\def\cH{{\Cal H}}
\def\tS{{\widetilde S}}
\def\bepsilon{\bar\epsilon}
\def\bgamma{\bar\gamma}
\def\brho{{\bar\rho}}
\def\dgamma{d^{\gamma}}
\def\Ave{\mathop{\text{\rm Ave}}}
\def\Forb{\mathop{\text{\rm Forb}}}
\def\Gp#1#2{G_{p_{#1}}^{(#2)}}
\def\UU{E}
%
%
\topmatter
\title
On $K^4$-free subgraphs of random graphs 
\endtitle
\rightheadtext{$K^4$-FREE SUBGRAPHS OF RANDOM GRAPHS}
\author
Y.~Kohayakawa, T.~\L uczak, and V.~R\"odl
\endauthor
\address
\noindent
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
\endaddress
\email{\tt<yoshi\@ime.usp.br>}
\endemail
\address
\noindent%\hskip-\parindent
%Mathematical Institute of the Polish Academy of Sciences, Pozna\'n,
%Poland, {\it on leave from the\/} 
Department of Discrete Mathematics,
Adam Mickiewicz University, ul.~Matejki 48/49, 60--769~Pozna\'n,
Poland 
\endaddress
\email{\tt<tomasz\@math.amu.edu.pl>, <tomasz\@mathcs.emory.edu>} 
\endemail
\address
\noindent
Department of Mathematics and Computer Science, 
Emory University, 
Atlanta, Georgia 30322, 
USA
\endaddress
\email{\tt<rodl\@mathcs.emory.edu>}
\endemail
\keywords Tur\'an's extremal problem, forbidden subgraphs, extremal
subgraphs, cliques, random graphs
\endkeywords
\subjclass 
Primary 05C80, 05C35; Secondary 05D99 
\endsubjclass
%\date
%11 March 1995
%\enddate
\thanks The first author was partially supported by FAPESP
(Proc.~93/0603--1) and by CNPq (Proc. 300334/93--1 and ProTeM--CC--II
Project ProComb).  
%
%The second author was partially supported by~KBN grant 2~1087 91~01.
%
Part of this work was done while the second author was visiting the
University of S\~ao Paulo, supported by FAPESP (Proc.~94/4276--8). The
third author was partially supported by the~NSF grant DMS--9401559.
\endthanks
\abstract For~$0<\gamma\leq1$ and graphs~$G$ and~$H$,
write~$G\to_\gamma H$ if any $\gamma$-proportion of the edges of~$G$
span at least one copy of~$H$ in~$G$. As customary, write~$K^r$ for
the complete graph on~$r$ vertices.  We show that for every fixed
real~$\eta>0$ there exists a constant~$C=C(\eta)$ such that almost
every random graph~$G_{n,p}$ with~$p=p(n)\geq Cn^{-2/5}$
satisfies~$G_{n,p}\to_{2/3+\eta}K^4$. The proof makes use of a variant
of Szemer\'edi's regularity lemma for sparse graphs and is based on a
certain superexponential estimate for the number of pseudo-random
tripartite graphs whose triangles are not too well distributed.
Related results and a general conjecture concerning $H$-free subgraphs
of random graphs in the spirit of the Erd\H os--Stone--Simonovits
theorem are discussed.
\endabstract
\endtopmatter
\document
\head\S0. Introduction
\endhead
A classical area of extremal graph theory investigates numerical and
structural problems concerning {\deffont$H$-free graphs\/}, namely
graphs that do not contain a copy of a given fixed graph~$H$ as a
subgraph. Let~$\ex(n,H)$ be the maximal number of edges that an
$H$-free graph on $n$~vertices may have. A basic question is then to
determine or estimate~$\ex(n,H)$ for any given~$H$ and large~$n$.  A
solution to this problem is given by the celebrated Erd\H
os--Stone--Simonovits theorem, which states that, as~$n\to\infty$, we
have
$$
\ex(n,H)=\(1-{1\over\chi(H)-1}+o(1)\){n\choose2}, 
\slabel{ESS}
$$
where as usual~$\chi(H)$ is the chromatic number of~$H$.  Furthermore,
as proved independently by Erd\H os and Simonovits, every $H$-free
graph~$G=G^n$ that has as many edges as in~{\eqnoESS} is in fact `very 
close' (in a certain precise sense) to the densest $n$-vertex
$(\chi(H)-1)$-partite graph. For these and related results,
see, for instance, Bollob\'as~{\refEGT}. 

Here we are interested in a variant of the function~$\ex(n,H)$.
Let~$G$ and~$H$ be graphs, and write~$\ex(G,H)$ for the maximal number
of edges that an $H$-free subgraph of~$G$ may have. Formally,
$\ex(G,H)=\max\{e(J)\:H\not\subset J\subset G\}$, where~$e(J)$ stands
for the {\deffont size\/}~$|E(J)|$ of~$J$.
Clearly~$\ex(n,H)=\ex(K^n,H)$. As an example of a problem
involving~$\ex(G,H)$ with~$G\neq K^n$, let us recall that a
well-known conjecture of Erd\H os states
that~$\ex(Q^n,C^4)=(1/2+o(1))e(Q^n)$, where~$Q^n$ stands for the
$n$-dimensional hypercube and~$C^4$ is the $4$-cycle. (For several
results concerning this conjecture, see Chung~{\refChung}.)

Our aim here is to study~$\ex(G,H)$ when~$G$ is a `typical' graph, by
which we mean a {\it random graph\/}.  Let~$0<p=p(n)\leq1$
and~$0<M=M(n)\leq N={n\choose2}$ be given.  The standard binomial
random graph~$G_p=G_{n,p}$ has as vertex set a fixed set~$V(G_p)$ of
cardinality~$n$ and two such vertices are adjacent in~$G_p$ with
probability~$p$, with all such adjacencies independent.  The random
graph~$G_M=G_{n,M}$ is simply a graph on a fixed $n$-element vertex
set~$V(G_M)$ chosen uniformly at random from all the~${N\choose M}$
possible candidates. (For concepts and results concerning random graphs
not given in detail below, see {\it e.g.\/}~Bollob\'as~{\refBBrgs}.)
Here we wish to investigate the random variables~$\ex(G_{n,p},H)$
and~$\ex(G_{n,M},H)$.

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

\proclaim{Conjecture {\MainConj}} Let~$H$ be a non-empty graph of
order at least~$3$, and let~$0<p=p(n)\leq1$ be such
that~$pn^{1/d_2(H)}\to\infty$ as~$n\to\infty$. Then the following
assertions hold.  
\roster
\item"({\it i\/})"Almost every~$G_{n,p}$ satisfies 
$$
\ex(G_{n,p},H)=\(1-{1\over\chi(H)-1}+o(1)\)e(G_{n,p}).
\slabel{Conj}
$$
\item"({\it ii\/})"Suppose~$\chi(H)\geq3$. Then for any~$\epsilon>0$
  there is a~$\delta=\delta(\epsilon)>0$ such that almost
  every~$G_{n,p}$ has the property that any $H$-free
  subgraph~$J\subset G_{n,p}$ of~$G_{n,p}$
  with~$e(J)\geq(1-\delta)\ex(G_{n,p},H)$ is $\epsilon$-quasi
  $(\chi(H)-1)$-partite.
\endroster
\endproclaim

Recall that any graph~$G$ contains an $r$-partite subgraph~$J\subset
G$ with~$e(J)\geq(1-1/r)e(G)$. Thus the content of
Conjecture~{\MainConj}({\it i\/}) is that~$\ex(G_{n,p},H)$ is at most
as large as the right-hand side of~{\eqnoConj}, or, in other words,
that~$G_{n,p}\to_\gamma H$ holds almost surely for any
fixed~$\gamma>1-1/(\chi(H)-1)$.  There are a few results in support of
Conjecture~{\MainConj}({\it i\/}).

Any result concerning the tree-universality of expanding graphs or
else a simple application of Szemer\'edi's regularity lemma for sparse
graphs (see Lemma~{\SSzp} below) give Conjecture~{\MainConj}({\it
  i\/}) for forests.  The cases in which~$H=K^3$ and~$H=C^4$ are
essentially proved in Frankl and R\"odl~{\refFR} and
F\"uredi~{\refFu}, respectively, in connection with problems
concerning the existence of some graphs with certain extremal
properties.  The case in which~$H$ is a general cycle was settled by
Haxell, Kohayakawa, and \L uczak~{\bf[\refnbHKLodd, \refnbHKLeven]}
(see also Kohayakawa, Kreuter, and Steger~{\refKKS}).
Conjecture~{\MainConj}({\it ii\/}) in the case in which~$0<p<1$ is a
constant follows easily from Szemer\'edi's regularity lemma~{\refSz}.
A variant of this lemma for sparse graphs (cf.~Lemma~{\SSzp} below)
and a lemma from Kohayakawa, \L uczak, and R\"odl~{\refKLRap}
concerning induced subgraphs of bipartite graphs may be used to verify
Conjecture~{\MainConj} for~$H=K^3$ in full. (See comments following
Conjecture~{\TechConj} for further details.)  Still in the case in
which~$H=K^3$, for~$0<p<1$ sufficiently close to~$1/2$, a much
stronger result than Conjecture~{\MainConj}({\it ii\/}) was proved by
Babai, Simonovits, and Spencer~{\refBSS}. Finally, let us note that a
result concerning {\it Ramsey\/} properties of random graphs in the
spirit of Conjecture~{\MainConj} was proved by R\"odl and
Ruci\'nski~{\bf[\refnbRRa, \refnbRRb]}.

Here we prove Conjecture~{\MainConj}({\it i\/}) for~$H=K^4$. Our
results are as follows. 

\proclaim{Theorem {\MainThm}} For any constant~$0<\eta\leq1/3$, there
is a constant~$C=C(\eta)$ for which the following holds. If~$0\leq
p=p(n)\leq1$ is such that~$p\geq Cn^{-2/5}$ for all large enough~$n$,
then almost every~$G_p=G_{n,p}$ is such that~$G_p\to_{2/3+\eta}K^4$.
\endproclaim

\proclaim{Corollary {\GnMversion}} For any constant~$0<\eta\leq1/3$,
there is a constant~$C=C(\eta)$ for which the following holds.
If~$0\leq M=M(n)\leq{n\choose2}$ is such that~$M\geq Cn^{8/5}$ for all
large enough~$n$, then almost every~$G_M=G_{n,M}$ is such
that~$G_M\to_{2/3+\eta}K^4$.
\endproclaim

In~\S6 below, we formulate an auxiliary conjecture
(Conjecture~{\TechConj}) that, if proved, would imply
Conjecture~{\MainConj} in full for all graphs~$H$. 

Finally, let us mention that Conjecture~{\MainConj}, if true, would
immediately imply the existence of very `sparse' graphs~$G$ satisfying
the property that~$G\to_\gamma H$ for any~$\gamma>1-1/(\chi(H)-1)$.  A
simple corollary of Theorem~{\MainThm} is that, for any~$\eta>0$,
there is a graph~$G=G_\eta$ that contains no~$K^5$ but we
have~$G\to_{2/3+\eta}K^4$ (see~\S5).  Erd\H os and Ne\v set\v ril have
asked whether such graphs exist. %(cf.~Erd\H os~{\refErdos}).

This note is organised as follows.  In Section~1.1 we give a short
outline of the proof of our main result, Theorem~{\MainThm}, and in
Section~1.2, some preliminary results are given. In~\S2 the
distribution of triangles in random and pseudo-random graphs is
studied. In~\S3 we prove a key lemma in the proof of our main result,
Lemma~{\MainLemma}. Theorem~{\MainThm} is proved in~\S4. In~\S5 we
discuss a deterministic corollary to Theorem~{\MainThm} concerning the
Erd\H os--Ne\v set\v ril problem.  Our last paragraph contains
Conjecture~{\TechConj}.

\head\S1. Outline of Proof and Preliminaries
\endhead

\subhead1.1. Outline of the proof of Theorem~{\MainThm}
\endsubhead
The proof of our main result is somewhat long and hence, for
convenience, in this section we describe its main steps.  Here we try
to avoid being too technical. 

The proof of Theorem~{\MainThm} naturally splits into two parts.
Suppose~$p=p(n)\geq Cn^{-2/5}$, where~$C$ is some large constant, and
let~$H$ be a spanning subgraph of~$G_p=G_{n,p}$ with `relative
density'~$e(H)/e(G_p)\geq\lambda$. Let us say that two vertices~$x$,
$y\in G_p$ are {\deffont$K^4_-$-connected\/} by~$H$ if there are two
other vertices~$z_1$, $z_2\in H$ such that both~$\{x,z_1,z_2\}$
and~$\{z_1,z_2,y\}$ induce triangles in~$H$. Sometimes we also say
that such a pair~$xy$ is a {\deffont pivotal pair\/}. 

In the first part of our proof, we show that the number of pairs of
vertices~$x$, $y\in G_p$ that are $K^4_-$-connected by~$H$ is roughly
at least~$(2\lambda-1){n\choose2}$, as long as~$C$ is a large enough
constant. The precise statement of this result is given in
Section~3.2, Lemma~{\MainLemma}. The second part of the proof consists
of deducing our Theorem~{\MainThm} from Lemma~{\MainLemma}. This part
is less technical than the first, and is also considerably shorter.
The method used here was inspired by an argument in R\"odl and
Ruci\'nski~{\refRRb}, and a version of this technique was used in
Haxell, Kohayakawa, and \L uczak~{\refHKLodd}.  Let us give a brief
description of this method.

Thus let~$G_p=G_{n,p}$ be the binomial random graph with~$p=p(n)\geq
Cn^{-2/5}$, where~$C$ is some large constant, and let a
constant~$0<\eta\leq1/3$ be fixed.  For simplicity, let us also assume
that~$p=p(n)\to0$ as~$n\to\infty$. We may write~$G_p$ as the union
of~$k$ independent random graphs~$\Gp1j$ ($1\leq j\leq k$), where~$k$
is some large constant to be carefully chosen later.  Since~$p=o(1)$,
below we may ignore the edges of~$G_p=\Gp11\cup\dots\cup\Gp1k$ that
belong to more than one of the~$\Gp1j$. Let us now ask an `adversary'
to choose a subgraph~$H\subset G_p$ of~$G_p$ of size at least~$\lambda
e(G_p)$, where~$\lambda=2/3+\eta$, or, equivalently, let us ask our
adversary to choose a set of edges~$F\subset E(G_p)$
with~$|F|\geq\lambda e(G_p)$. Our aim is to show that such a set~$F$
must span a~$K^4$.

Instead of asking our adversary to pick~$F$ directly, we ask him to
pick~$F\cap E(\Gp1j)$ for all~$j$. For some~$j_0$, we must
have~$|F\cap E(\Gp1{j_0}))|\geq\lambda e(\Gp1{j_0})$.  We may in fact
ask our adversary to pick first~$j_0$ and~$F_{j_0}=F\cap
E(\Gp1{j_0})$, and leave the choice of~$F\cap E(\Gp1j)$ ($j\neq j_0$)
for later.  By Lemma~{\MainLemma}, we know that at
least~$\sim(2\lambda-1){n\choose2}=(1/3+2\eta){n\choose2}$ edges
of~$K^n$ join pairs of vertices that are $K^4_-$-connected
by~$F_{j_0}$. We now show~$G'=\bigcup_{j\neq j_0}\Gp1j$ to our
adversary, and ask him to pick~$F\cap E(G')$. Note that, with very
high probability, at least~$1/3+\eta$ of the edges of~$G'$ will be
formed by $K^4_-$-connected pairs, and if our adversary puts any of
these edges into~$F\cap E(G')$, then~$F$ will span a copy
of~$K^4$. However, since~$G'$ contains an extremely large proportion
of the edges of~$G_p$ (we choose~$k$ very large), our adversary is
forced to pick at least~$2/3$ of the edges of~$G'$, and hence he is
forced to `close' a~$K^4$ by picking a $K^4_-$-connected pair~$xy$ for
an edge of~$H$.

Let us close this section with a few words on the proof of
Lemma~{\MainLemma}. Recall that in that lemma we are concerned with
estimating the number of $K^4_-$-connected pairs induced by subgraphs
of random graphs. A very simple lower bound for the number of such
pairs induced by an arbitrary graph~$H_*$ is given in assertion~(*) in
Section~3.1. This estimate is far too weak to be of any use when
dealing with subgraphs of random graphs, but a weighted version of
this estimate, Lemma~{\WeightedTu}, is important in the proof of
Lemma~{\MainLemma}.  Another important and a much deeper ingredient in
the proof of Lemma~{\MainLemma} is a version of Szemer\'edi's
regularity lemma~{\refSz} for sparse graphs; see Lemma~{\SSzp} in
Section~1.2 below. A simple application of Lemmas~{\SSzp}
and~{\WeightedTu} allows us to focus our attention on certain
$\epsilon$-regular quadruples.  The key lemma concerning such
quadruples is Lemma~{\ProhiA} in Section~3.2. The proof of
Lemma~{\ProhiA} is based on certain results concerning the number and
the distribution of triangles in random and pseudo-random graphs.
Paragraph~2 is entirely devoted to those results. The main lemmas
in~\S2 are Lemmas~{\CountLemma} and~{\TrigUpBd}.

\subhead1.2. Preliminaries
\endsubhead
Let a graph~$H=H^n$ of order~$|H|=n$ be fixed.  For~$U$, $W\subset
V=V(H)$ with~$U\cap W=\emptyset$, we write~$E(U,W)=E_H(U,W)$ for the
set of edges of~$H$ that have one endvertex in~$U$ and the other
in~$W$. We set~$e(U,W)=e_H(U,W)=|E(U,W)|$.  

The following notion will be needed in what follows. 
Suppose~$0<\eta\leq1$ and~$0<p\leq1$.  We say that~$H$ is
{\deffont$\eta$-upper-uniform\/} with {\deffont density\/}~$p$ if, for
all~$U$, $W\subset V$ with~$U\cap W=\emptyset$ and~$|U|$, $|W|\geq\eta
n$, we have $e_H(U,W)\le(1+\eta)p|U||W|$.  Clearly, if~$H$ is
$\eta$-upper-uniform with density~$p$, then it is also
$\eta'$-upper-uniform with density~$p'$ for any~$\eta\leq\eta'\leq1$
and any~$p\leq p'\leq1$.  In the sequel, for any two disjoint
non-empty sets~$U$, $W\subset V$, let 
$$
\dHp(U,W)=e_H(U,W)/p|U||W|
$$ 
be the {\deffont$p$-relative density\/} or, for short, the
{\deffont$p$-density\/} of~$H$ between~$U$ and~$W$.  Now
suppose~$\epsilon>0$, $U$, $W\subset V$, and~$U\cap W=\emptyset$.  We
say that the pair~$(U,W)$ is {\deffont$(\epsilon,H,p)$-regular\/} if
for all~$U'\subset U$, $W'\subset W$ with~$|U'|\geq\epsilon|U|$
and~$|W'|\geq\epsilon|W|$ we have
$$
|\dHp(U',W')-\dHp(U,W)|\leq\epsilon.
$$
We say that a partition~$P=(V_i)_0^k$ of~$V=V(H)$ is
{\deffont$(\epsilon,k)$-equitable\/} if~$|V_0|\leq\epsilon n$,
and~$|V_1|=\ldots=|V_k|$. Also, we say that~$V_0$ is the {\deffont
  exceptional\/} class of~$P$.  When the value of~$\epsilon$ is not
relevant, we refer to an $(\epsilon,k)$-equitable partition as a
{\deffont$k$-equitable\/} partition. Similarly, $P$ is an {\deffont
  equitable\/} partition of~$V$ if it is a $k$-equitable partition for
some~$k$. Finally, we say that an $(\epsilon,k)$-equitable
partition~$P=(V_i)_0^k$ of~$V$ is {\deffont$(\epsilon,H,p)$-regular\/}
if at most~$\epsilon{k\choose2}$ pairs~$(V_i,V_j)$ with~$1\leq i<j\leq
k$ are not $(\epsilon,p)$-regular. We may now state an extension of
Szemer\'edi's lemma~{\refSz} to subgraphs of $\eta$-upper-uniform
graphs.

\proclaim {Lemma {\SSzp}} For any given~$\epsilon>0$ and~$k_0\geq1$,
there are constants~$\eta=\eta(\epsilon,k_0)>0$
and~$K_0=K_0(\epsilon,k_0)\geq k_0$ that depend only on~$\epsilon$
and~$k_0$ such that any $\eta$-upper-uniform graph~$H$ with
density~$0<p\leq1$ admits an $(\epsilon,H,p)$-regular
$(\epsilon,k)$-equitable partition of its vertex set with~$k_0\leq
k\leq K_0$.\qed
\endproclaim

Using standard estimates for tails of the binomial distribution, it is
easy to check that a.e.~$G_{n,p}$ is $\eta$-upper-uniform with
density~$p$ for any constant~$0<\eta\leq1$ if~$d=pn$ is larger than
some constant~$d_0=d_0(\eta)$. 

Let us introduce a piece of notation before we proceed.
If~$U_1,\dots,U_\ell\subset V(J)$ are pairwise disjoint sets of
vertices of a given graph~$J$, we write~$J[U_1,\dots,U_\ell]$ for the
$\ell$-partite subgraph of~$J$ naturally defined by the~$U_i$ ($1\leq
i\leq\ell$).  Thus, $J[U_1,\dots,U_\ell]$~has vertex
set~$\bigcup_1^\ell U_i$ and two of its vertices are adjacent if and
only if they are adjacent in~$J$ and, moreover, they belong to
distinct~$U_i$.

Now suppose we have real numbers~$0<p\leq1$, $0<\epsilon\leq1$,
$0<\gamma_0\leq1$ and an integer~$m\geq1$. Suppose the above~$U_i$
($1\leq i\leq\ell$) all have cardinality~$m$, and write~$\gamma_{ij}$
for the $p$-density~$\dJp(U_i,U_j)$ for all distinct~$i$ and~$j$.
Suppose~$L$ is a graph on~$[\ell]=\{1,\dots,\ell\}$ such that, for
any~$1\leq i<j\leq\ell$, the pair~$(U_i,U_j)$ is
$(\epsilon,J,p)$-regular and~$\gamma_{ij}\geq\gamma_0$ whenever~$ij\in
E(L)$.

We may now state our next lemma. In what follows, we write~$O_1(x)$
for any term~$y$ satisfying~$|y|\leq x$. Also, as usual, we
write~$\Delta=\Delta(L)$ for the maximal degree of~$L$ and we
write~$\Gamma_J(x)$ for the $J$-neighbourhood of a vertex~$x\in V(J)$.

\proclaim {Lemma {\MinDegree}} Let~$J$, $L$, and the sets~$U_i$
\rom($1\leq i\leq\ell$\rom) be as above and let~$\Delta=\Delta(L)$.
Suppose~$0<\epsilon\leq1/(2\Delta+1)$ and
put~$\rho=(2\Delta+1/\gamma_0)\epsilon$ and~$\mu=2\Delta\epsilon$.
Then there are sets~$\bU_i\subset U_i$ with~$|\bU_i|\geq(1-\mu)m$ for
all~$1\leq i\leq\ell$ such that, for all~$x\in\bU_i$ and any~$1\leq
i\leq\ell$, we have
$$
d_{ij}(x)=|\Gamma_J(x)\cap\bU_j|=(1+O_1(\rho))\gamma_{ij}pm
  \slabel{MinDegreeA} 
$$  
for any~$j$ with~$ij\in E(L)$.\qed
\endproclaim
%\demo{Proof}\qed
%\enddemo

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Now let~$J$ be a tripartite graph with tripartition~$V(J)=V_1\cup
%V_2\cup V_3$, where~$|V_i|=m$ for all~$i\in\{1,2,3\}$.  Suppose
%further that~$(V_1,V_2,V_3)$ is an $(\epsilon,J,p)$-regular triple for
%some~$0<\epsilon\leq1$ and~$0<p\leq1$.
%Let~$\gamma_i=\dJp(V_{i-1},V_{i+1})$ and assume
%that~$\gamma_i\geq\gamma_0$ for all~$i\in\{1,2,3\}$ and
%some~$\gamma_0>0$. When convenient, we often tacitly take our indices
%modulo~$3$. Also, in the sequel we write~$O_1(b)$ for any term~$a$
%with~$|a|\leq b$. 

%\proclaim {Lemma {\MinDegree}} Suppose~$0<\epsilon\leq1/5$ and
%put~$\rho=(4+1/\gamma_0)\epsilon$ and~$\mu=4\epsilon$.  Then there are
%sets~$\bV_i\subset V_i$ with~$|\bV_i|\geq(1-\mu)m$ for
%all~$i\in\{1,2,3\}$ such that, for all~$i\in\{1,2,3\}$
%and~$x\in\bV_i$, we have
%$$
%d_{ij}(x)=|\Gamma_J(x)\cap\bV_j|=(1+O_1(\rho))\gamma_kpm
%  \slabel{MinDegreeA} 
%$$  
%for both choices of~$j$ and~$k$ such that~$\{i,j,k\}=[3]$.  In
%particular, for any distinct~$i$, $j\in[3]$, we have
%$$
%e(J[\bV_i,\bV_j])\geq(1-\rho)(1-\mu)e(J[V_i,V_j]). 
%  \slabel{LostEdges}
%$$
%\endproclaim
%\demo{Proof} To obtain the sets~$\bV_i$, we simply successively remove
%`bad' vertices from the~$V_i$. A little more precisely, we start by
%setting~$\bV_i=V_i$ ($i\in\{1,2,3\}$), and at every stage we check
%whether, for all~$i\in\{1,2,3\}$ and for all~$x\in\bV_i$,
%relation~{\eqnoMinDegreeA} is satisfied for both choices of~$j$.  If
%this is the case, we stop the procedure. If this is not the case we
%remove the `bad' vertex~$x$ from~$\bV_i$ and carry on the procedure.
%Our task is to show that this process ends with the required
%sets~$\bV_i$ ($i\in\{1,2,3\}$). 

%Thus suppose that, while carrying out the process above, at some point
%we removed for the first time more than~$\mu m=4\epsilon m$ bad
%vertices from one of the~$V_i$, say~$V_{i_0}$. Let~$\tV_{i_0}\subset
%V_{i_0}$ be the set of vertices removed from~$V_{i_0}$.
%Thus~$|\tV_{i_0}|>\mu m=4\epsilon m$.  Then for some~$j_0$ we
%have~$\tV_{i_0j_0}\subset\tV_{i_0}$ with~$|\tV_{i_0j_0}|\geq2\epsilon
%m$ and with all~$x\in\tV_{i_0j_0}$ violating~{\eqnoMinDegreeA}
%with~$j=j_0$.  Now let
%$$
%\tV_+=\big\{x\in\tV_{i_0j_0}\:d_{i_0j_0}(x)>(1+\rho)\gamma_{k_0}pm, 
%         \text{ where }\{i_0,j_0,k_0\}=[3]\big\}, 
%$$
%and similarly for~$\tV_-$. Thus~$\tV_{i_0j_0}=\tV_-\cup\tV_+$. 

%\case1. $|\tV_+|\geq|\tV_{i_0j_0}|/2$
%\endcase
%\casebody Clearly, all the vertices in~$\tV_+\subset V_{i_0}$ have degree
%larger than~$(1+\rho)\gamma_{k_0}pm$ in the bipartite
%graph~$J[\tV_+,V_{j_0}]$. Since~$(V_{i_0},V_{j_0})$ is an
%$(\epsilon,J,p)$-regular pair and~$|\tV_+|\geq\epsilon m$, we have
%$$
%\dJp(\tV_+,V_{j_0})\leq\dJp(V_{i_0},V_{j_0})+\epsilon
%                      =\gamma_{k_0}+\epsilon, 
%$$
%and hence
%$$
%(1+\rho)\gamma_{k_0}pm|\tV_+|
%  < e_J(\tV_+,V_{j_0})
%  \leq(\gamma_{k_0}+\epsilon)pm|\tV_+|. 
%$$
%Thus~$(1+\rho)\gamma_{k_0}<\gamma_{k_0}+\epsilon$, which
%is a contradiction
%since~$\rho=(4+1/\gamma_0)\epsilon\geq\epsilon/\gamma_{k_0}$. 
%\endcasebody

%\case2. $|\tV_-|\geq|\tV_{i_0j_0}|/2$
%\endcase
%\casebody
%Suppose~$\bV_{j_0}\subset V_{j_0}$ is the set of vertices that we had
%just after adding the last bad vertex to~$\tV_{i_0}$. We know
%that~$|\bV_{j_0}|\geq(1-4\epsilon)m\geq\epsilon m$. By the
%$(\epsilon,J,p)$-regularity of the pair~$(V_{i_0},V_{j_0})$, we have
%that  
%$$
%\dJp(\tV_-,\bV_{j_0})\geq\dJp(V_{i_0},V_{j_0})-\epsilon
%                                           =\gamma_{k_0}-\epsilon, 
%$$
%and hence
%$$
%(\gamma_{k_0}-\epsilon)p(1-4\epsilon)m|\tV_-|
%  \leq e_J(\tV_-,\bV_{j_0})
%  <(1-\rho)\gamma_{k_0}pm|\tV_-|.
%$$
%Thus~$(\gamma_{k_0}-\epsilon)(1-4\epsilon)<(1-\rho)\gamma_{k_0}$,
%which is a contradiction since~$\rho\geq(4+1/\gamma_{k_0})\epsilon$.  
%\endcasebody

%Therefore the procedure described at the beginning of our proof does
%indeed produce the sets~$\bV_i$ ($i\in\{1,2,3\}$) as required. We now
%assume~$i$, $j\in[3]$ are distinct and observe that~{\eqnoLostEdges}
%follows easily from the first part above.  Suppose~$\{i,j,k\}=[3]$.
%Then
%$$
%\eqalign{
%e(J[\bV_i,\bV_j])&=\sum_{x\in\bV_i}d_{ij}(x)
%  =(1+O_1(\rho))\gamma_kpmm_i\cr
%  &\qquad\geq(1-\rho)(1-\mu)\gamma_kpm^2
%  =(1-\rho)(1-\mu)e(J[V_i,V_j]),\cr
%}
%$$
%as required.\qed 
%\enddemo
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Lemma~{\MinDegree} above is very similar to Lemma~2 in~{\refHKL}, and
hence its rather elementary proof is omitted.  We close this section
with a very simple large deviation inequality for the hypergeometric
distribution. This inequality will be used in Section~2.1 below.

\proclaim{Lemma {\Hyper}} Let~$1\leq a\leq n$ and~$1\leq t\leq r\leq
n$ be integers, and suppose~$R\subset[n]$ is an $r$-element subset
of~$[n]=\{1,\dots,n\}$ chosen uniformly at random. Then
$$
\P\big(|R\cap[a]|\geq t\big)\leq\(a\over n-r+1\)^t{r\choose t}.\qed 
$$
\endproclaim

\head\S2. Triangles in Pseudo-Random and Random Graphs
\endhead

\subhead2.1. The counting lemma
\endsubhead
Let~$m\geq1$ be an integer.  In this section we shall consider a fixed
triple~$\bfV=(\bV_1,\bV_2,\bV_3)$ of pairwise disjoint sets
with~$m/2\leq m_i=|\bV_i|\leq m$ for all~$i\in\{1,2,3\}$.  We shall
also suppose that~$0<p=p(m)\leq1$ satisfies~$pm\geq
m^{1/2+1/\log\log\log m}$ for all large enough~$m$ and, moreover,
that~$p=o(1)$ as~$m\to\infty$.  In this section, all the asymptotic
notation refers to~$m\to\infty$. Our aim is to estimate from above the
number of certain pseudo-random tripartite graphs~$\bF$ with
tripartition~$V(\bF)=\bV_1\cup\bV_2\cup\bV_3$ that contain
unexpectedly few triangles given the number of edges that they have,
or else whose triangles are not too regularly distributed.

Before we may describe precisely which graphs~$\bF$ are of interest to
us, we need to introduce a few definitions.  In what follows, indices
will be tacitly taken modulo~$3$ when convenient.  Let~$0<\delta\leq1$
be given.  Suppose~$e\in
E_\bF(\bV_{i-1},\bV_{i+1})=E(\bF[\bV_{i-1},\bV_{i+1}])$
($i\in\{1,2,3\}$) and let~$k_3(e)=k_3^\bF(e)$ be the number of
triangles of~$\bF$ that contain~$e$. We shall say that~$e$ is
{\deffont$(\delta,K^3)$-poor\/} if
$$
k_3(e)<(1-\delta)\dFp(\bV_i,\bV_{i-1})\dFp(\bV_i,\bV_{i+1})p^2m_i. 
$$ 
The graph~$\bF$ is {\deffont$(\delta,K^3)$-unbalanced\/} if, for
some~$i\in\{1,2,3\}$, the number of~$(\delta,K^3)$-poor edges
in~$E_\bF(\bV_{i-1},\bV_{i+1})$ is at least~$\delta
e_\bF(\bV_{i-1},\bV_{i+1})=\delta|E_\bF(\bV_{i-1},\bV_{i+1})|$. 
For simplicity, below we write~$\gamma_i=\dFp(\bV_{i-1},\bV_{i+1})$
($i\in\{1,2,3\}$) and, if~$x\in\bV_i$ and~$i\neq j\in\{1,2,3\}$, we
let~$d_{ij}(x)=|\Gamma_\bF(x)\cap\bV_j|$.

Now suppose integers~$m$ and~$T$ and real constants~$0<\bepsilon\leq1$,
$0<\bgamma_0\leq1$, and~$0<\brho\leq1$ are given, and
let~$\bfV=(\bV_1,\bV_2,\bV_3)$ and~$\bfm=(m_1,m_2,m_3)$ be as above.  Let
us write~$\cF_p(\bepsilon,\bgamma_0,\brho,T)
=\cF_p(\bepsilon,\bgamma_0,\brho;\bfV,T)$ for the set of tripartite
graphs~$\bF$ with tripartition~$V(\bF)=\bV_1\cup\bV_2\cup\bV_3$ that
satisfy the following properties:

\roster%\widestnumber\item{xxx}
\item"{({\it i\/})}"$(\bV_1,\bV_2,\bV_3)$ is an $(\bepsilon,\bF,p)$-regular
  triple, 
\item"{({\it
      ii\/})}"$\bgamma_0\leq\gamma_i=\dFp(\bV_{i-1},\bV_{i+1})\leq2$
  for all~$i\in\{1,2,3\}$,
\item"{({\it iii\/})}"$d_{ij}(x)=|\Gamma_\bF(x)\cap
  \bV_j|=(1+O_1(\brho))\gamma_kpm_j$ for all~$x\in\bV_i$ and any
  choice of~$i$, $j$, and~$k$ such that~$\{i,j,k\}=[3]$,
\item"{({\it iv\/})}"$\bF$ has size~$e(\bF)=|E(\bF)|=T$. 
\endroster

\noindent Moreover, for any given~$0<\delta\leq1$,
let~$\cF_p^\delta(\bepsilon,\bgamma_0,\brho,T)
=\cF_p^\delta(\bepsilon,\bgamma_0,\brho;\bfV,T)$ be the set of
$(\delta,K^3)$-unbalanced graphs~$\bF$
in~$\cF_p(\bepsilon,\bgamma_0,\brho,T)$.  Put
$$
f^\delta_p(\bepsilon,\bgamma_0,\brho;\bfm,T)
  =|\cF_p^\delta(\bepsilon,\bgamma_0,\brho;\bfV,T)|. 
$$
Sometimes the labelling of the vertices of the graphs
in~$\cF_p(\bepsilon,\bgamma_0,\brho;\bfV,T)$ or in
$\cF_p^\delta(\bepsilon,\bgamma_0,\brho;\bfV,T)$ is not relevant, and
in that case we may replace~$\bfV$ by~$\bfm$ in our notation.

Our crucial counting lemma is as follows.

\proclaim {Lemma {\CountLemma}} Let~$0<\alpha\leq1$,
$0<\bgamma_0\leq1$, and~$0<\delta\leq1$ be given.  Then there is a 
constant~$\epsilon_0=\epsilon_0(\alpha,\bgamma_0,\delta)>0$ that
depends only on~$\alpha$, $\bgamma_0$, and~$\delta$ for which the
following holds.  Suppose~$0<p=p(m)\leq1$ is such that~$p\geq
m^{-1/2+1/\log\log\log m}$ for all large enough~$m$ and, moreover,
$p=o(1)$ as~$m\to\infty$. Then, if~$\brho\leq\brho_0=\delta/27$,
$\bepsilon\leq\epsilon_0$, and~$m$ is sufficiently large, we have
$$
f^\delta_p(\bepsilon,\bgamma_0,\brho;\bfm,T)
  =|\cF_p^\delta(\bepsilon,\bgamma_0,\brho;\bfm,T)|
  \leq\alpha^T{3m^2\choose T}
$$
for all~$T$ and all~$\bfm=(m_1,m_2,m_3)$ with~$m/2\leq m_i\leq m$
\rom($i\in\{1,2,3\}$\rom).
\endproclaim

Most of the rest of Section~2.1 is dedicated to the proof of
Lemma~{\CountLemma} above.  Our general strategy in this proof is as
follows. We randomly generate a tripartite graph~$\bF$ with
tripartition~$V(F)=\bV_1\cup\bV_2\cup\bV_3$ and size~$e(F)=|E(F)|=T$,
and show that the probability that the graph we obtain will be a
member of~$\cF_p^\delta(\bepsilon,\bgamma_0,\brho,T)$ is suitably
small.  We generate~$\bF$ in steps: we first
generate~$\bF[\bV_2,\bV_3]$. We then generate~$\bF[\bV_1,\bV_3]$ and
analyse the structure of the
graph~$\bF[\bV_1,\bV_3]\cup\bF[\bV_2,\bV_3]$. We then finally
generate~$\bF[\bV_1,\bV_2]$ and show that the appropriate probability
is indeed small.

Let us now make precise the process by which we generate~$\bF$. We
first of all fix a partition~$T=T_1+T_2+T_3$ of~$T$ such that,
putting~$\gamma_i=T_i/pm_{i-1}m_{i+1}$, we
have~$\bgamma_0\leq\gamma_i\leq2$ for all~$i\in\{1,2,3\}$.  Note that,
because of condition~({\it ii\/}) above for~$F$, we may disregard
the~$T$ for which such a partition does not exist.  Let us suppose
that the bipartite graph~$\bF_{23}=\bF[\bV_2,\bV_3]$ has been fixed,
and that the following properties hold (cf.~({\it i\/})--({\it iv\/})
above): ({\it a\/})~the pair~$(\bV_2,\bV_3)$ is
$(\bepsilon,\bF_{23},p)$-regular, ({\it
  b\/})~$d_{ij}(x)=|\Gamma_{\bF_{23}}(x)\cap
\bV_j|=(1+O_1(\brho))\gamma_1pm_j$ for all~$x\in\bV_i$,
where~$\{i,j\}=\{2,3\}$, and ({\it c\/})~$e(\bF_{23})=T_1$.

We now fix the degree sequence for the vertices~$x\in\bV_1$ in the
bipartite graph $\bF[\bV_1,\bV_3]$, and generate this graph respecting
this sequence.  Thus let~$(d_{13}(x))_{x\in\bV_1}$
with~$\sum_{x\in\bV_1}d_{13}(x)=T_2$ and
$d_{13}(x)=(1+O_1(\brho))\gamma_2pm_3$ for all~$x\in\bV_1$ be fixed,
and generate the bipartite graph~$\bF_{13}=\bF[\bV_1,\bV_3]$ by
selecting the neighbourhoods $\Gamma_{\bF_{13}}(x)\subset\bV_3$
($x\in\bV_1$) randomly and independently for all~$x\in\bV_1$. Thus,
for every~$x\in\bV_1$, all the $d_{13}(x)$-element subsets of~$\bV_3$
are equally likely to be chosen as the neighbourhood of~$x$
within~$\bV_3$. We now analyse the structure
of~$\bF_{13}\cup\bF_{23}=\bF[\bV_1,\bV_3]\cup\bF[\bV_2,\bV_3]$.

For convenience, let us put~$d_{ij}=\Ave_{x\in
 \bV_i}d_{ij}(x)=T_k/m_i=\gamma_kpm_j$ for all~$i$, $j$, and~$k$
with~$\{i,j,k\}=[3]$ and~$k\neq3$. Put also~$d_{13}=\gamma_2pm_3$
and~$d_{23}=\gamma_1pm_3$.  Thus~$d_{13}(x)=(1+O_1(\brho))d_{13}$ for
all~$x\in\bV_1$, and~$d_{23}(y)=(1+O_1(\brho))d_{23}$ for all~$y\in
\bV_2$.

Let~$0<\beta_1\leq1$ be given. For all~$x\in\bV_1$, put
$$
\tV_2=\tV_2(x,\beta_1)
     =\{y\in\bV_2\:\sigma(x,y)\leq-\beta_1d_{13}d_{23}/m_3\},  
$$
where~$\sigma(x,y)=d(x,y)-d_{13}d_{23}/m_3
=|\Gamma_{\bF_{13}}(x)\cap\Gamma_{\bF_{23}}(y)|-d_{13}d_{23}/m_3$.
Note that the set~$\tV_2(x,\beta_1)$ is defined in such a way that the
following fact holds: if~$e=xy$ ($x\in\bV_1$, $y\in\bV_2$) is an edge
of~$\bF$, then~$e$ is a $(\beta_1,K^3)$-poor edge if and only
if~$y\in\tV_2(x,\beta_1)$.   

Now let~$0<\beta_2\leq1$ be given. Below we say that~$x\in\bV_1$ is
{\deffont$(\beta_1,\beta_2)$-faulty\/}
if~$|\tV_2(x,\beta_1)|\geq\beta_2m_2$. Note that, clearly, since we
are conditioning on~$\bF_{23}=\bF[\bV_2,\bV_3]$, the event that a
vertex~$x\in\bV_1$ should be $(\beta_1,\beta_2)$-faulty depends only
on the random set~$\Gamma_{\bF_{13}}(x)\subset\bV_3$ that is chosen as
the neighbourhood of~$x$ within~$\bV_3$. 

Our next lemma is the key technical result in the proof of the main
lemma in this section, Lemma~{\CountLemma}. 

\proclaim {Lemma {\FaultyVx}} Suppose the constants~$0<\beta_1\leq1$,
$0<\beta_2\leq1$, $0<\bgamma_0\leq1$, $0<\bepsilon\leq1$,
and~$0<\brho\leq1$ are such~$\beta_1\beta_2\geq27\bepsilon$,
$\beta_2\brho\leq\bepsilon$, and~$\beta_2\leq\bgamma_0$. Then, for all
sufficiently large~$m$, the probability that a given
vertex~$x\in\bV_1$ is $(\beta_1,\beta_2)$-faulty is at
most~$\big(5\bepsilon^{\bepsilon/\beta_2}\big)^{d_{13}}$.
\endproclaim
\demo{Proof} Let us fix~$x\in\bV_1$, and assume
that~$|\tV_2|=|\tV_2(x,\beta_1)|\geq\beta_2m_2$.
Let~$\tV_2^0\subset\tV_2$ be such
that~$\tm_2=|\tV_2^0|=\lceil\beta_2m_2\rceil$.  The following
assertion, whose proof we omit, is very similar to Lemma~{\MinDegree}. 

\assertion(1) There exist sets~$\bV_2'\subset\tV_2^0$
and~$\bV_3'\subset \bV_3$ for which we
have~$m_2'=|\bV_2'|\geq(1-2\bepsilon/\beta_2)\tm_2$
and~$m_3'=|\bV_3'|\geq(1-2\bepsilon)m_3$, and furthermore
$$
d'_{23}(y)=|\Gamma_{\bF_{23}}(y)\cap\bV_3'|
          =\(1+O_1\(3\bepsilon\over\beta_2\)\)d_{23}
\slabel{RegA}
$$ 
for all~$y\in\bV_2'$, and
$$
d'_{32}(z)=|\Gamma_{\bF_{23}}(z)\cap\bV_2'|
    =\(1+O_1\(3\bepsilon\over\beta_2\)\)\beta_2d_{32}
\slabel{RegB}
$$ 
for all~$z\in\bV_3'$. 
\endassertion

Using Assertion~1, we prove next that there exists a {\it small\/}
set~$Y$ of vertices from~$\tV_2$ whose $F_{23}$-neighbourhood
uniformly cover essentially all of~$\bV_3$. We need to introduce some
notation.  Let us set~$\omega=\omega(m)=m^{1/\log\log m}$, and
let~$\dY(z)=|\Gamma_{F_{23}}(z)\cap Y|$ for all~$Y\subset\bV_2$ and
all~$z\in\bV_3$. Put also
$$
\bV_3''=\bV_3''(Y)
  =\left\{z\in\bV_3\:
     \dY(z)=\(1+O_1\(4\bepsilon\over\beta_2\)\)\omega\right\}
$$
for all~$Y\subset\bV_2$. 

\assertion(2) There is a set~$Y\subset\tV_2$ of
cardinality~$q=|Y|=(1+O_1(3\bepsilon/\beta_2))\omega m_2/d_{32}$ such
that~$|\bV_3''|=|\bV_3''(Y)|\geq(1-2\bepsilon)m_3$, and such that
$$
d_{23}''(y)=|\Gamma_{F_{23}}(y)\cap\bV_3''|
           \geq\(1-{3\bepsilon\over\beta_2}\)d_{23}
\slabel{RegAb}
$$
for all~$y\in Y$. 
\endassertion
\proofofassertion Let~$\bV_2'$ and~$\bV_3'$ be as in Assertion~1.
To prove Assertion~2, we construct~$Y$ by randomly selecting its
elements from the set~$\bV_2'\subset\tV_2$.
Let~$p_Y=p_Y(m)=\omega/\beta_2d_{32}$.  Note that~$0<p_Y<1$
for all large enough~$m$.  Put the vertices of~$\bV_2'$ into~$Y$
randomly, each with probability~$p_Y$, and with all these events
independent. The expected cardinality of~$Y$ is then
$$
\E(|Y|)=
  \(1+O_1\(2\bepsilon\over\beta_2\)\){\omega m_2\over d_{32}}, 
$$
and the expected degree of a vertex~$z\in\bV_3'$ into~$Y$ is 
$$
\E(\dY(z))=\(1+O_1\(3\bepsilon\over\beta_2\)\)\omega.
$$
 From standard bounds for the tail of the binomial distribution, we
may 
deduce that there is a set~$Y\subset\bV_2'\subset\tV_2$ such
that~$q=|Y|$ is as required in Assertion~2, and such that
every~$z\in\bV_3'$
satisfies~$\dY(z)=(1+O_1(4\bepsilon/\beta_2))\omega$. Note that, for
such a set~$Y$, we have~$\bV_3'\subset\bV_3''=\bV_3''(Y)$, and
hence~$|\bV_3''|\geq|\bV_3'|\geq(1-2\bepsilon)m_3$. It now suffices to
notice that every~$y\in Y$ is such that
$$
d_{23}''(y)=|\Gamma_{F_{23}}(y)\cap\bV_3''|
  \geq|\Gamma_{F_{23}}(y)\cap\bV_3'|
  \geq\(1-{3\bepsilon\over\beta_2}\)d_{23}, 
$$
since~$y\in Y\subset\bV_2'$ and relation~{\eqnoRegA} in Assertion~1
holds. This completes the proof of Assertion~2.
\endproofofassertion

\assertion(3) The probability that our fixed vertex~$x\in\bV_1$ admits 
a set~$Y$ as in Assertion~2 is at
most~$\big(4\bepsilon^{\bepsilon/\beta_2}\big)^{d_{13}}$.
\endassertion
\proofofassertion Let us first sketch the idea in the proof of
Assertion~3. Roughly speaking, the set~$Y$ is such that the
neighbourhoods~$\Gamma_{F_{23}}(y)\cap\bV_3''$ of the vertices~$y\in
Y$ within~$\bV_3''$ are about of the same size, and the vertices
in~$\bV_3''$ are, by definition, covered by those sets quite uniformly.
Now, since the vertices in~$Y$ are all in~$\tV_2$, we have that the
neighbourhood~$\Gamma_{F_{13}}(x)$ of~$x$ within~$\bV_3$ intersects
all the neighbourhoods~$\Gamma_{F_{23}}(y)$ ($y\in Y$) too little.
Thus it intersects the sets~$\Gamma_{F_{23}}(y)\cap\bV_3''$ too little
as well, and this is possible only if it in fact intersects~$\bV_3''$
in an unexpectedly small set. It then suffices to estimate the
probability that~$\Gamma_{F_{13}}(x)\cap\bV_3''$ should be as small.
Let us now formalise the argument above.

Assume that a set~$Y$ as in Assertion~2 exists.  We consider the 
vectors~$\bg=\bg^x=(g_z)_{z\in\bV_3''}$
and~$\ff^y=(f_z^y)_{z\in\bV_3''}$ ($y\in Y$) with entries
$$
g_z=\cases 1         &\text{if }z\in\Gamma_{\bF_{13}}(x)\\
           -d_{13}/m_3  &\text{otherwise,}
    \endcases
$$
and
$$
f_z^y=\cases 1         &\text{if }z\in\Gamma_{\bF_{23}}(y)\\ 
             -d_{23}/m_3  &\text{otherwise.}
      \endcases
$$
We first estimate~$\xi_z=\sum_{y\in Y}f_z^y$ for~$z\in\bV_3''$. For
any fixed~$z\in\bV_3''$, we have 
$$
\eqalignno{
\xi_z=\sum_{y\in Y}f_z^y
     =\dY(z)-{d_{23}\over m_3}\big\{q-\dY(z)\big\}
     =\(1+{d_{23}\over m_3}\)\dY(z)-{d_{23}q\over m_3}\qquad&\cr
  =\(1+{d_{23}\over m_3}\)\(1+O_1\(4\bepsilon\over\beta_2\)\)
      \omega-{d_{23}q\over m_3}.&\cr
}
$$ 
We have~$d_{23}=\gamma_1pm_3=o(m_3)$, and,
since~$d_{23}/m_3=T_1/m_2m_3=d_{32}/m_2$, we
have~$d_{23}q/m_3=(1+O_1(3\bepsilon/\beta_2))\omega$. Therefore
$$
\xi_z\leq(1+o(1))
  \(1+{4\bepsilon\over\beta_2}\)\omega
   -\(1-{3\bepsilon\over\beta_2}\)\omega
 \leq{8\bepsilon\over\beta_2}\omega
$$ 
for large enough~$m$, and
similarly~$\xi_z\geq-(8\bepsilon/\beta_2)\omega$ if~$m$ is
sufficiently large.  Given two vectors~$\ba=(a_z)_{z\in\bV_3''}$
and~$\bb=(b_z)_{z\in\bV_3''}$,
let~$\<\ba,\bb\>=\sum_{z\in\bV_3''}a_zb_z$. We now
estimate~$\sum_{y\in Y}\<\ff^y,\bg\>$. We have
$$
\sum_{y\in Y}\<\ff^y,\bg\>
  =\left\<\sum_{y\in Y}\ff^y,\bg\right\>
  =\left\<(\xi_z)_{z\in\bV_3''},\bg\right\>
  =\sum_{z\in\bV_3''}\xi_zg_z.
$$
Therefore
$$
\Bigg|\sum_{y\in Y}\<\ff^y,\bg\>\Bigg|
    \leq\sum_{z\in\bV_3''}|\xi_zg_z|
    \leq{8\bepsilon\over\beta_2}\omega\sum_{z\in\bV_3''}|g_z|.  
$$
We have from our assumptions on our constants
that~$\brho\leq\bepsilon/\beta_2\leq\beta_1/27\leq1/27$. Hence 
$$
\sum_{z\in\bV_3''}|g_z|\leq\sum_{z\in\bV_3}|g_z|
  \leq(1+\brho)d_{13}+d_{13}\leq{9\over4}d_{13}, 
$$
with plenty to spare. Thus
$$
\Bigg|\sum_{y\in Y}\<\ff^y,\bg\>\Bigg|
            \leq{18\bepsilon\over\beta_2}\omega d_{13}. 
\slabel{FstEst}
$$ 
We now give a lower estimate for the left-hand side of~{\eqnoFstEst}
in terms of the~$\sigma(x,y)$ ($y\in Y$).  Let
$d_{13}''(x)=|\Gamma_{\bF_{13}}(x)\cap\bV_3''|$ and recall that we
let~$d_{23}''(y)=|\Gamma_{F_{23}}(y)\cap\bV_3''|$ for all~$y\in Y$.
Put~$m_3''=|\bV_3''|$ and~$d''(x,y)=|\Gamma_{\bF_{13}}(x)
\cap\Gamma_{\bF_{23}}(y)\cap\bV_3''|$ for all~$y\in Y$. Fix~$y\in Y$. 
Clearly~$d''(x,y)\leq
d(x,y)=|\Gamma_{\bF_{13}}(x)\cap\Gamma_{\bF_{23}}(y)|$. Thus 
$$
\eqalign{
\<\ff^y,\bg\>
 =d''(x,y)-{d_{13}\over m_3}&\big\{d_{23}''(y)-d''(x,y)\big\}
    -{d_{23}\over m_3}\big\{d_{13}''(x)-d''(x,y)\big\}\cr
&\qquad
 +{d_{13}d_{23}\over m_3^2}
  \bigg(m_3''-\big\{d_{13}''(x)+d_{23}''(y)-d''(x,y)\big\}\bigg).\cr  
}
$$
Write~$d_{13}''(x)=(1-\tau)d_{13}$. Recalling~{\eqnoRegAb}, we see that 
$$
\eqalignno{
\<\ff^y,\bg\>
  &\leq d(x,y)-2{d_{13}d_{23}\over m_3}
                    +{d_{13}d_{23}m_3''\over m_3^2}\cr 
  &\qquad\qquad
     +{3\bepsilon d_{13}d_{23}\over\beta_2m_3}
     +\tau{d_{13}d_{23}\over m_3}
     +{d_{13}d''(x,y)\over m_3}+{d_{23}d''(x,y)\over m_3}\cr
  &\qquad\qquad
     -{d_{13}d_{23}d_{13}''(x)\over m_3^2}
     -{d_{13}d_{23}d_{23}''(y)\over m_3^2} 
     +{d_{13}d_{23}d''(x,y)\over m_3^2}\cr
  &\leq\sigma(x,y)+{3\bepsilon d_{13}d_{23}\over\beta_2m_3}
         +\tau{d_{13}d_{23}\over m_3}
         +{d_{13}+d_{23}\over m_3}d''(x,y)
         +o\(d_{13}d_{23}\over m_3\),\cr 
}
$$
where we used that, trivially, $m_3''\leq m_3$, and that~$d_{13}(x)$,
$d_{23}(y)$, and~$d''(x,y)$ are all~$o(m_3)$, since by
assumption~$p=p(m)\to0$ as~$m\to\infty$. However, 
$$
\eqalign{
{d_{13}+d_{23}\over m_3}\sum_{y\in Y}d''(x,y)
  &={d_{13}+d_{23}\over m_3}\sum_{y\in Y}
    |\Gamma_{\bF_{13}}(x)\cap\Gamma_{\bF_{23}}(y)\cap\bV_3''|\cr 
  &\leq{d_{13}+d_{23}\over m_3}
    \sum\bigg\{\dY(z)\:z\in\Gamma_{F_{13}}(x)\cap\bV_3''\bigg\}\cr
  &\leq{d_{13}+d_{23}\over m_3}
     (1+\brho)\(1+{4\bepsilon\over\beta_2}\)\omega d_{13},\cr
}
$$
which is~$o(d_{13}d_{23}q/m_3)$. Therefore
$$
\sum_{y\in Y}\<\ff^y,\bg\>
  \leq-\(\beta_1-{4\bepsilon\over\beta_2}-\tau\){d_{13}d_{23}q\over m_3}. 
\slabel{ScdEst}
$$
Using that~$q=(1+O_1(3\bepsilon/\beta_2))\omega m_2/d_{32}$ and
that~$d_{23}/m_3=d_{32}/m_2$, we deduce from inequality~{\eqnoScdEst}
above that  
$$
\eqalignno{
\sum_{y\in Y}\<\ff^y,\bg\>
&\leq-\(\beta_1-{4\bepsilon\over\beta_2}-\tau\)
         \(1+O_1\(3\bepsilon\over\beta_2\)\)\omega d_{13}\cr
&\leq-\(\beta_1-{4\bepsilon\over\beta_2}-\tau
            +O_1\(3\bepsilon\over\beta_2\)\)\omega d_{13}.
&\alabel{ScdEstPrime}\cr
}
$$ 
We now claim that~$\tau\geq2\bepsilon/\beta_2$. Indeed, otherwise we
would have
that~$\beta_1-4\bepsilon/\beta_2-\tau+O_1(3\bepsilon/\beta_2)\geq0$,
and hence, comparing inequalities~{\eqnoFstEst}
and~{\eqnoScdEstPrime}, we would have
that~$\beta_1-4\bepsilon/\beta_2-\tau+O_1(3\bepsilon/\beta_2)
\leq18\bepsilon/\beta_2$, and consequently
that~$\tau\geq2\bepsilon/\beta_2$, which is a contradiction.

Recall
that~$d''_{13}(x)=|\Gamma_{\bF_{13}}(x)\cap\bV_3''|=(1-\tau)d_{13}$ and
that~$d_{13}(x)=|\Gamma_{\bF_{13}}(x)|=(1+O_1(\brho))d_{13}$.  Also,
$|\bV_3\setminus\bV_3''|\leq2\bepsilon|\bV_3|$.  Thus we deduce from
the existence of the set~$Y$ that at least~$(\tau-\brho)d_{13}\geq\tau
d_{13}/2$ elements of~$\Gamma_{\bF_{13}}(x)\subset\bV_3$ are confined to
a subset of~$\bV_3$ of cardinality at most~$2\bepsilon|\bV_3|$.  Thus,
by Lemma~{\Hyper}, the probability that such a set~$Y$ exists is at
most~$2^{(1+\brho)d_{13}}(3\bepsilon)^{\tau
  d_{13}/2}\leq2^{3d_{13}/2}(3\bepsilon)^{\bepsilon
  d_{13}/\beta_2}\leq\big(4\bepsilon^{\bepsilon/\beta_2}\big)^{d_{13}}$,
completing the proof of Assertion~3.
\endproofofassertion

We may now finish the proof of Lemma~{\FaultyVx} combining
Assertions~2 and~3 above. Indeed, writing~$\sum_q'$ for the sum over
all~$q$ satisfying~$q=(1+O_1(3\bepsilon/\beta_2))\omega m_2/d_{32}$,
we have from the above two assertions that probability that the
vertex~$x$ should be $(\beta_1,\beta_2)$-faulty is, for large
enough~$m$, at most 
$$
\eqalign{
\big(4\bepsilon^{\bepsilon/\beta_2}\big)^{d_{13}}
  \sum\nolimits_q'{m_2\choose q}
\leq{6\bepsilon\omega m_2\over\beta_2d_{32}}
  {m_2\choose2\omega m_2/d_{32}}
  \big(4\bepsilon^{\bepsilon/\beta_2}\big)^{d_{13}}\qquad\qquad&\cr
\leq{6\bepsilon\omega m_2\over\beta_2d_{32}}
  \(\e d_{32}\over2\omega\)^{2\omega m_2/d_{32}}
    \big(4\bepsilon^{\bepsilon/\beta_2}\big)^{d_{13}}
\leq\big(5\bepsilon^{\bepsilon/\beta_2}\big)^{d_{13}},&\cr
}
$$
where in the last inequality we used that~$\omega m_2(\log
m)/d_{32}=o(d_{13})$, which follows easily from our assumption
that~$pm\geq m^{1/2+1/\log\log\log m}$ for all sufficiently
large~$m$. Thus Lemma~{\FaultyVx} is proved.  \qed\enddemo

We are now in position to finish the proof of Lemma~{\CountLemma}. 

\demo{Proof of Lemma~{\CountLemma}} Let us first state a simple fact
concerning the~$T_i$.

\assertion(1) For all~$i\in\{1,2,3\}$ we have~$T_i\geq(\bgamma_0/24)T$. 
\endassertion
\proofofassertion
Indeed, $T\leq\sum_{i\in\{1,2,3\}}\gamma_ipm_{i-1}m_{i+1}\leq6pm^2$,
and therefore, for any~$i\in\{1,2,3\}$, we have
$$
T_i=\gamma_ipm_{i-1}m_{i+1}
  \geq{\bgamma_0\over4}pm^2
  \geq{\bgamma_0\over24}T, 
$$
as required.
\endproofofassertion

Our next observation is an immediate consequence of Lemma~{\FaultyVx}
and Assertion~1.

\assertion(2) Let~$0<\beta_3\leq1$ be given. The probability that at
least~$\beta_3m_1$ vertices in~$\bV_1$ are $(\beta_1,\beta_2)$-faulty is at
most~$\big(6\bepsilon^{\bepsilon/\beta_2}\big)^{\beta_3\bgamma_0T/24}$. 
\endassertion
\proofofassertion
Indeed, by Lemma~{\FaultyVx} and Assertion~1 above, the probability
in question is at most 
$$
2^{m_1}\big((5\bepsilon^{\bepsilon/\beta_2})^{d_{13}}\big)^{\beta_3m_1} 
 =2^{m_1}\big(5\bepsilon^{\bepsilon/\beta_2}\big)^{\beta_3T_1}
 \leq\big(6\bepsilon^{\bepsilon/\beta_2}\big)^{\beta_3\bgamma_0T/24}, 
$$
completing the proof of Assertion~2.
\endproofofassertion

We now describe the last step in the generation of~$\bF$. Recall that
we have
generated~$\bF_{13}\cup\bF_{23}=\bF[\bV_1,\bV_3]\cup\bF[\bV_2,\bV_3]$
so far.  Let~$K[\bV_1,\bV_2]$ be the complete bipartite graph with
bipartition~$\bV_1\cup\bV_2$. To generate~$\bF_{12}=\bF[\bV_1,\bV_2]$,
we randomly pick for~$E(\bF[\bV_1,\bV_2])$ a $T_3$-element subset
of~$E(K[\bV_1,\bV_2])$, uniformly chosen from all such sets.

\assertion(3) Suppose that fewer than~$\beta_3m_1$ vertices in~$\bV_1$
are $(\beta_1,\beta_2)$-faulty. Then the probability that at
least~$\delta T_3$ edges in~$\bF_{12}=\bF[\bV_1,\bV_2]$ are
$(\beta_1,K^3)$-poor is no larger than
$\big\{4(\beta_2+\beta_3)^{\delta\bgamma_0/24}\big\}^T$.
\endassertion
\proofofassertion Recall that an edge~$xy\in E(\bF[\bV_1,\bV_2])$
($x\in\bV_1$, $y\in\bV_2$) is $(\beta_1,K^3)$-poor if and only
if~$y\in\tV_2(x,\beta_1)$.  The probability in question~$P_0$ is the
probability that at least~$\delta T_3$ edges~$xy\in E(K[\bV_1,\bV_2])$
($x\in\bV_1$, $y\in\bV_2$) with~$y\in\tV_2(x,\beta_1)$ are selected to
be elements of~$\bF_{12}$.  The number of such `potentially poor'
edges~$xy$ in~$K[\bV_1,\bV_2]$ is at
most~$\beta_3m_1m_2+(1-\beta_3)\beta_2m_1m_2\leq(\beta_2+\beta_3)m_1m_2$,
and hence, by Lemma~{\Hyper} and Assertion~1, we have
$$
P_0\leq2^{T_3}\big\{2(\beta_2+\beta_3)\big\}^{\delta T_3}
  \leq\big\{4(\beta_2+\beta_3)^\delta\big\}^{\bgamma_0T/24}
  \leq\big\{4(\beta_2+\beta_3)^{\delta\bgamma_0/24}\big\}^T, 
$$
proving Assertion~3. 
\endproofofassertion

We may now finish the proof of Lemma~{\CountLemma}.  Let the
constants~$\alpha$, $\bgamma_0$, and~$\delta$ as in the statement of
our lemma be given. We then
let~$\epsilon_0=\epsilon_0(\alpha,\bgamma_0,\delta)$ be such
that~$0<\epsilon_0\leq\delta\bgamma_0/27$ and, moreover,
$$
\big(6\bepsilon^{\delta/27}\big)
  ^{\bgamma_0/24\log\log(1/\bepsilon)}\leq{1\over6}\alpha
$$
and
$$
4\({27\bepsilon\over\delta}
     +{1\over\log\log(1/\bepsilon)}\)^{\delta\bgamma_0/24}
      \leq{1\over6}\alpha
$$
for all~$0<\bepsilon\leq\epsilon_0$. 

We now apply Assertions~2 and~3 above with suitably chosen~$\beta_1$,
$\beta_2$, $\beta_3$, $\bepsilon$, and~$\brho$.
Let~$\beta_1=\delta$ and fix any~$0<\bepsilon\leq\epsilon_0$. 
Let~$\beta_2=27\bepsilon/\delta\leq\bgamma_0$
and~$\beta_3=1/\log\log(1/\bepsilon)$. Recall
that~$\brho_0=\delta/27$.  To complete the proof, we proceed as
follows: we suppose that~$\brho\leq\brho_0$ is given and that~$m$ is 
sufficiently large for the inequalities below to 
hold. Fix the partition~$T=T_1+T_2+T_3$ of~$T$, the bipartite
graph~$F_{23}=F[\bV_2,\bV_3]$, and the degree
sequence~$(d_{13}(x))_{x\in\bV_1}$ as above. Then
generate~$\bF_{13}=\bF[\bV_1,\bV_3]$. The probability that at
least~$\beta_3m_1$ vertices in~$\bV_1$ are $(\beta_1,\beta_2)$-faulty 
is, by Assertion~2, at most 
$$
\big(6\bepsilon^{\bepsilon/\beta_2}\big)^{\beta_3\bgamma_0T/24}
 =\big(6\bepsilon^{\delta/27}\big)^{\beta_3\bgamma_0T/24}
 \leq\(\alpha\over6\)^T\leq{1\over6}\alpha^T.
$$
Let us now assume that fewer than~$\beta_3m_1$ vertices in~$\bV_1$ are
$(\beta_1,\beta_2)$-faulty, and let us
generate~$\bF_{12}=\bF[\bV_1,\bV_2]$. Then the probability that~$\delta T_3$
edges in~$\bF_{12}=\bF[\bV_1,\bV_2]$ are $(\delta,K^3)$-poor is, by
Assertion~3, at most  
$$
\big\{4(\beta_2+\beta_3)^{\delta\bgamma_0/24}\big\}^T
 \leq\left\{4\({27\bepsilon\over\delta}
    +{1\over\log\log(1/\bepsilon)}\)^{\delta\bgamma_0/24}\right\}^T
 \leq\(\alpha\over6\)^T\leq{1\over6}\alpha^T. 
$$
We now note that the argument above is symmetric with respect to the
indices~$i\in\{1,2,3\}$ (note the factor~`$3$' below), and thus we may
conclude that 
$$
|\cF_p^\delta(\bepsilon,\bgamma_0,\brho;\bfV,T)|
  \leq3\times{2\over6}\alpha^T{3m^2\choose T} 
  \leq\alpha^T{3m^2\choose T}, 
$$
completing the proof of Lemma~{\CountLemma}.
\qed\enddemo

Recall that~$m$ and~$T$ are integers, $0<\bepsilon\leq1$,
$0<\bgamma_0\leq1$, $0<\delta\leq1$, and~$0<\brho\leq1$ are fixed reals,
$0<p=p(m)\leq1$ is such that~$pm\to\infty$ and~$p=o(1)$
as~$m\to\infty$, and~$\bfV=(\bV_1,\bV_2,\bV_3)$ and~$\bfm=(m_1,m_2,m_3)$,
where the~$\bV_i$ ($i\in\{1,2,3\}$) are pairwise disjoint sets with
cardinality~$|\bV_i|=m_i$ ($i\in\{1,2,3\}$).  Our next lemma concerns a
property of graphs~$\bF\in\cF_p(\bepsilon,\bgamma_0,\brho,T)
\setminus\cF_p^\delta(\bepsilon,\bgamma_0,\brho,T)$, namely, graphs~$\bF$
in~$\cF_p(\bepsilon,\bgamma_0,\brho,T)$ that are
{\deffont$(\delta,K^3)$-balanced\/}.  For a vertex~$x\in V(\bF)$,
let~$k_3(x)=k_3^\bF(x)$ denote the number of triangles of~$\bF$ that
contain~$x$.

\proclaim {Lemma {\CountLemmaCor}} Suppose~$\bF$ is a
$(\delta,K^3)$-balanced graph
in~$\cF_p(\bepsilon,\bgamma_0,\brho;\bfV,T)$.
Put~$\delta'=(2\delta)^{1/2}$.  Then, for any~$i\in\{1,2,3\}$, there are
at most~$\delta'm_i$ vertices~$x$ in~$\bV_i$ such that
$$
k_3(x)=k_3^\bF(x)<(1-\brho-\delta')\gamma_1\gamma_2\gamma_3p^3m_{i-1}m_{i+1}. 
$$
\endproclaim
\demo{Proof} By symmetry, it suffices to prove the statement
for~$i=1$. In the sequel we freely use the notation introduced before
Lemma~{\CountLemma}. Also, let us put~$d_{ij}=\Ave_{x\in
  \bV_i}d_{ij}(x)=\gamma_kpm_j$ for all~$i$, $j$, and~$k$
with~$\{i,j,k\}=[3]$.  Below we say that a vertex~$x\in\bV_1$ is {\it
  bad\/} if at least~$\delta d_{12}/\delta'=\delta'd_{12}/2$ edges
in~$E(\bF[\bV_1,\bV_2])$ incident to~$x$ are $(\delta,K^3)$-poor edges. The
number of such bad vertices~$x\in\bV_1$ is at most~$\delta'm_1$, as
otherwise the number of $(\delta,K^3)$-poor edges in~$E(\bF[\bV_1,\bV_2])$
would be more than~$\delta m_1d_{12}=\delta e(\bF[\bV_1,\bV_2])$,
contradicting the fact that~$\bF$ is $(\delta,K^3)$-balanced.

Note that an edge~$e=x_1x_2\in E(\bF[\bV_1,\bV_2])$ ($x_i\in\bV_i$,
$i\in\{1,2\}$) that is not $(\delta,K^3)$-poor `contributes' with at
least~$k_3(e)\geq(1-\delta)\gamma_1\gamma_2p^2m_3$ triangles
to~$k_3(x_1)$. Supposing that~$x_1\in\bV_1$ is not a bad vertex,
summing over all~$x_2\in\bV_2$ for which~$x_1x_2\in E(\bF[\bV_1,\bV_2])$ is
not a $(\delta,K^3)$-poor edge, we obtain that 
$$
\eqalignno{
k_3(x_1)
&\geq\((1-\brho)d_{12}-{\delta'\over2}d_{12}\)(1-\delta)
         \gamma_1\gamma_2p^2m_3\cr
&\qquad\geq\(1-\brho-\delta-{\delta'\over2}\)
              \gamma_1\gamma_2\gamma_3p^3m_2m_3
\geq(1-\brho-\delta')\gamma_1\gamma_2\gamma_3p^3m_2m_3.\cr
}
$$
Since, as we saw above, at most~$\delta'm_1$ vertices~$x_1\in\bV_1$ are
bad, the proof is complete. 
\qed
\enddemo

\subhead2.2. Distribution of triangles in random graphs
\endsubhead
In this section we look at the random graph~$G_p=G_{n,p}$ and study
the distribution of the triangles it contains. The aim will be to
prove that the triangles of~$G_{n,p}$ do not unduly concentrate on any
fixed set of edges and vertices. To be precise, let~$x$ be any given
vertex of~$G_p$ and let~$\UU$ be a set of {\it edges\/} of~$G_p$ taken
from the subgraph~$G_p[\GammaGp(x)]$ induced by the
neighbourhood~$\GammaGp(x)$ of~$x$ in~$G_p$. Also, let~$W$ be a subset
of {\it vertices\/} of~$G_p$ disjoint from~$\{x\}\cup V(\UU)$, where we
write~$V(\UU)$ for the set~$V(G_p[\UU])$ of vertices of~$G_p$ that are
incident to at least one edge from~$\UU$.  Our aim is to find an upper
bound for the number of triangles~$k_3(\UU,W)=k_3^{G_p}(\UU,W)$ of~$G_p$
that are determined by an edge from~$\UU$ and a vertex in~$W$.  Note
that the expected value of this number is~$p^2|\UU||W|$. We shall show
that this is an upper bound in probability up to~$1+\theta$ for any
fixed~$\theta>0$ as long as~$\UU$ and~$W$ are reasonably large
and~$p=p(n)$ does not tend to~$0$ too fast.

\proclaim {Lemma {\TrigUpBd}} Let~$c_1$, $c_2>0$ and~$0<\theta\leq1$
be given. Then there is a constant~$C_0=C_0(c_1,c_2,\theta)$ that
depends only on~$c_1$, $c_2$, and~$\theta$ for which the following
holds. Suppose~$p=p(n)=\omega n^{-2/5}$
where~$C_0\leq\omega=\omega(n)=o(n^{1/190})$. Then almost
every~$G_p=G_{n,p}$ is such that, if~$\UU\subset E(G_p[\GammaGp(x)])$
and~$W\subset\tW=V(G_p)\setminus\(\{x\}\cup V(\UU)\)$ for some~$x\in
V(G_p)$, then
$$
k_3(\UU,W)=k_3^{G_p}(\UU,W)\leq(1+\theta)p^2|\UU||W|
\slabel{TrigUpBdBd}
$$
as long as~$|\UU|\geq c_1p^3n^2$ and~$|W|\geq c_2n$. 
\endproclaim

Most of the remainder of this section is devoted to the proof of
Lemma~{\TrigUpBd}.  Unfortunately, our proof below is a little
indirect and is based on a few auxiliary lemmas; moreover, this proof
makes use of a technical condition that~$\omega$ should not be too
large. The obvious direct approaches based on simple large deviation
inequalities seem to fail to give Lemma~{\TrigUpBd}.  To see why this
might be expected, note that ({\it i\/})~for the sets~$\UU$ and~$W$ of
interest, the expected value~$\E(k_3(\UU,W))=p^2|\UU||W|$ of~$k_3(\UU,W)$ is
of order~$O(n)$ only, while the number of sets~$W$ that we have to
handle is~$\exp\{\Omega(n)\}$, and ({\it ii\/})~$k_3(\UU,W)$ is a sum of
{\it positively correlated\/} indicator variables and the most common
large deviation inequalities for such sums do not seem to be strong
enough for our purposes.

Let us turn to the proof of Lemma~{\TrigUpBd}. For the rest of this
section we assume that~$p=p(n)=\omega n^{-2/5}$,
where~$C_0\leq\omega=\omega(n)=o(n^{1/190})$ and~$C_0$ is some large
constant. (The main result for~$G_p$ with larger~$p$ will be deduced
from the small~$p$ case; cf.~Lemma~{\Monotone}.)

Let~$P^3$ be the path of length~$2$ and~$E^k$ the $k$-vertex graph
with no edges ($k\geq1$).  We write~$H_k$ for~$P^3\vee E^k$
($k\geq1$), the graph on~$k+3$ vertices we obtain from the disjoint
union of~$P^3$ and~$E^k$ by adding all the~$3k$ edges between~$V(P^3)$
and~$V(E^k)$. A little piece of arithmetic shows that almost
no~$G_{n,p}$ contains a copy of~$H_{12}$. Thus for the rest of this
section we may and shall assume that our~$G_{n,p}$ is $H_{12}$-free. 

We may clearly assume that the degree of any vertex of~$G_p=G_{n,p}$
is~$(1+o(1))pn$, and also that any vertex of~$G_p$ is contained in at
most~$p^3n^2$ triangles. Furthermore, the expected number of common
neighbours of any two fixed vertices of~$G_p$
is~$p^2(n-2)\leq\omega^2n^{1/5}$.  Thus, we may and shall condition on
our~$G_p$ being such
that~$\dGnp(x,y)=|\GammaGp(x)\cap\GammaGp(y)|\leq2\omega^2n^{1/5}$ for
any pair of distinct vertices~$x$, $y\in V(G_p)$. Finally, we may
assume that~$G_p$ is $o(1)$-upper-uniform.

Suppose~$x\in V(G_p)$ and~$\UU\subset E(G_p[\GammaGp(x)])$.  For a
vertex~$y\in\tW=V(G_p)\setminus(\{x\}\cup V(\UU))$, let~$\UU_y$ be the
set~$\UU\cap E(G_p[\GammaGp(y)])$ of edges of~$\UU$ that the neighbourhood
of~$y$ in~$G_p$ induces in~$G_p$.  Clearly,
$k_3(\UU,y)=k_3(\UU,\{y\})=|\UU_y|$.  We shall say that a vertex~$y\in\tW$
is {\deffont$(x,\UU)$-bad\/}, or simply {\deffont$\UU$-bad\/}, if~$\UU_y$ is
not an independent set of edges.

\proclaim {Lemma {\TUBa}} Almost every~$G_p$ is such that, for
any~$x\in V(G_p)$ and any~$\UU\subset E(G_p[\GammaGp(x)])$, 
at most~$10\e\omega^8n^{4/5}$ vertices are $\UU$-bad.
\endproclaim
\demo{Proof}
Fix a vertex~$x\in V(G_p)$. Let us generate~$G_p$ as follows: we first
choose the neighbourhood~$\GammaGp(x)$ of~$x$ in~$G_p$, and once this
set is fixed, we decide which edges within~$\GammaGp(x)$ should be
in~$G_p$. Put~$\UU^{(0)}=E(G_p[\GammaGp(x)])$, and
let~$V(\UU^{(0)})\subset\GammaGp(x)$ be the set of vertices
in~$\GammaGp(x)$ that are incident to at least one edge
in~$E(G_p[\GammaGp(x)])$.  For the rest of the proof, we assume that
the edges generated so far are fixed.

Let us now consider a vertex~$y\in
Y=V(G_p)\setminus(\{x\}\cup\GammaGp(x))$, and let us decide which
edges between~$y$ and~$V(\UU^{(0)})$ should be in our~$G_p$. Notice
that whether or not~$y$ is $\UU^{(0)}$-bad depends solely on these
$y$--$V(\UU^{(0)})$~edges. In particular, the events `$y$~is
$\UU^{(0)}$-bad' ($y\in Y$) are all independent. Let us estimate the
probability that a given vertex~$y\in Y$ turns out to be
$\UU^{(0)}$-bad.  We first observe that with probability~$1-o(1/n)$ we
have~$|V(\UU^{(0)})|\leq|\GammaGp(x)|\leq2pn$
and~$|\Delta(\UU^{(0)})|=|\Delta(G_p[\UU^{(0)}])|\leq2p^2n=2\omega^2n^{1/5}$.
In the sequel, we assume that these two inequalities hold.  In
particular, the number of copies of~$P^3$ spanned by~$\UU^{(0)}$ is,
crudely, at most~$|V(\UU^{(0)})|\Delta(\UU^{(0)})^2\leq8\omega^5n$.
Thus the probability that~$y$ is $\UU^{(0)}$-bad is
$$
\eqalignno{
\P(\Delta(\UU^{(0)}_y)\geq2)
  &=\P(G_p[\UU^{(0)}_y]\text{ contains a }P^3)\cr
  &\qquad\leq\E(\#\{P^3\subset G_p[\UU^{(0)}_y]\})
             \leq8\omega^5np^3=8\omega^8n^{-1/5},\cr
}
$$   
where~$\#\{P^3\subset G_p[\UU^{(0)}_y]\}$ denotes the number of copies
of~$P^3$ in~$G_p[\UU^{(0)}_y]$.  
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Therefore it follows that the expected number of $\UU^{(0)}$-bad
%vertices~$y\in Y$ is at most~$8\omega^8n^{4/5}$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Now, from the independence of the events `$y$~is $\UU^{(0)}$-bad'
($y\in Y$), we have that the probability~$P_k$ that at least~$k$ such
vertices~$y$ are $\UU^{(0)}$-bad satisfies
$$
P_k\leq{n\choose k}\big\{8\omega^8n^{-1/5}\big\}^k
  \leq\(8\e\omega^8n^{4/5}\over k\)^k.  \slabel{TUBeqA}
$$
Thus, if~$k=\lfloor9\e\omega^8n^{4/5}\rfloor$, we have~$P_k=o(1/n)$ 
with plenty to spare. 

The above argument proves our lemma with~`$\UU\subset
E(G_p[\GammaGp(x)])$' replaced by~`$\UU=E(G_p[\GammaGp(x)])$'. To
complete the proof, we make the following simple observation.
Suppose~$x\in V(G_p)$ is fixed, $\UU\subset
\UU^{(0)}=E(G_p[\GammaGp(x)])$, and~$y\in
Y=V(G_p)\setminus(\{x\}\cup\GammaGp(x))$. Then, $y$~is
necessarily~$\UU^{(0)}$-bad whenever it is $\UU$-bad. Thus, an
$\UU$-bad vertex~$y\in\tW=V(G_p)\setminus(V(\UU)\cup\{x\})$ is either
contained in~$\GammaGp(x)$ or else it is $\UU^{(0)}$-bad. Since we may
assume that~$\Delta(G_p)\leq2pn=2\omega n^{3/5}\leq\omega^8n^{4/5}$,
our lemma follows.  \qed
\enddemo

Lemma~{\TUBa} above tells us that, for any~$x$ and any~$\UU$, we
have~$\Delta(\UU_y)=\Delta(G_p[\UU_y])\leq1$ for
most~$y\in\tW=V(G_p)\setminus(\{x\}\cup V(\UU))$. Of course,
since~$G_p$ is supposed not to contain~$H_{12}$, we
have~$\Delta(\UU_y)\leq11$ for any vertex~$y\in\tW$.

For each vertex~$y\in\tW$, let~$X_y=|\UU_y|=k_3(\UU,y)$ and let~$X_y'$
be the cardinality~$\nu(\UU_y)=\nu(G_p[\UU_y])$ of a maximum matching
in~$G_p[\UU_y]$. Since~$\Delta(\UU_y)\leq11$, we have~$X_y'\geq
X_y/2\Delta(\UU_y)\geq X_y/22$ for any~$y\in\tW$. Moreover, for
any~$y\in\tW$ that is not $\UU$-bad, we clearly have~$X_y'=X_y$.

Let us now fix~$W\subset\tW$. Put
$$
X=X_W=\sum_{w\in W}X_w=\sum_{w\in W}k_3(\UU,w)=k_3(\UU,W), 
$$
and similarly~$X'=X_W'=\sum_{w\in W}X_w'$. Let us
write~$\sum_{\text{b}}$ for sum over all~$w\in W$ that are $\UU$-bad
and~$\sum_{\text{g}}$ for sum over all~$w\in W$ that are not $\UU$-bad.
Then
$$
\eqalignno{
k_3(\UU,W)=X_W&=\sum\nolimits_{\text{g}}X_w
                +\sum\nolimits_{\text{b}}X_w\cr
    &\quad\qquad=\sum\nolimits_{\text{g}}X_w'
                +\sum\nolimits_{\text{b}}X_w
    \leq X_W'+\sum\nolimits_{\text{b}}X_w.
         &\alabel{TUBeqSum}\cr
}
$$
Now our aim is to bound the last two summands in~{\eqnoTUBeqSum}. 

For any two distinct vertices ~$x$ and~$y\in V(G_p)$, let~$Y_{xy}$ be
the number of edges induced by the
set~$\GammaGp(x,y)=\GammaGp(x)\cap\GammaGp(y)$ in~$G_p$.
Thus~$Y_{xy}=|E(G_p[\GammaGp(x,y)])|$,
and~$\E(Y_{xy})={n-2\choose2}p^5=(1/2+o(1))\omega^5$.

\proclaim {Lemma {\TUBYxy}} For almost every~$G_p$ we
have~$Y_{xy}\leq22\e^2\max\{\log n,\omega^5\}$ for any pair of
distinct vertices~$x$, $y\in V(G_p)$.
\endproclaim  
\demo{Proof}
Let~$Y_{xy}'$ be the maximum cardinality~$\nu(G_p[\GammaGp(x,y)])$ of
a matching in $G_p[\GammaGp(x,y)]$.  We claim that
$$
\P\big\{Y_{xy}'\geq\e^2\max\{\log n,\omega^5\}\big\}
  \;\leq\,n^{-\e^2}=o(n^{-2}). 
\slabel{YxyClaim}
$$
For convenience, put~$\mu=\E(Y_{xy})\leq\omega^5$.  By Lemma~2 in
Janson~{\refJanson}, for any~$a\geq\e^2$, we have     
$$
\P(Y_{xy}'\geq a\mu)\leq\exp\{-\mu(a\log a+1-a)\}
  \leq\exp\left\{-{1\over2}a(\log a)\mu\right\}.
\slabel{YxyA}
$$
We now check that~{\eqnoYxyClaim} follows
from~{\eqnoYxyA}. Suppose~$\mu=\E(Y_{xy})\leq\log n$. Then 
we take~$a=\e^2\mu^{-1}\log n\geq\e^2$ in~{\eqnoYxyA} and note that
then 
$$
\P(Y_{xy}'\geq\e^2\log n)=\P(Y_{xy}'\geq a\mu)
  \leq\exp\{-\e^2\log n\}=n^{-\e^2}.
$$
Suppose now that~$\mu=\E(Y_{xy})>\log n$. Then we take~$a=\e^2$
in~{\eqnoYxyA} to obtain 
$$
\P(Y_{xy}'\geq\e^2\omega^5)\leq\P(Y_{xy}'\geq\e^2\mu)
  \leq\exp\{-\e^2\log n\}=n^{-\e^2}.
$$
Thus the claimed inequality~{\eqnoYxyClaim} does hold. In particular, 
almost surely~$Y_{xy}'\leq\e^2\max\{\log n,\omega^5\}$ for any
distinct~$x$, $y\in V(G_p)$.  Our lemma now follows,
since $\Delta(G_p[\GammaGp(x,y)])\leq11$, and hence~$Y_{xy}'\geq
Y_{xy}/22$.\qed
\enddemo

By Lemmas~{\TUBa} and~{\TUBYxy} above, an almost sure upper bound for
the last summand in~{\eqnoTUBeqSum} is~$220\e^3\max\{\log
n,\omega^5\}\omega^8n^{4/5}$.  Our aim now is to estimate~$X_W'$.
Fortunately, the method of proof of Lemma~2 in Janson~{\refJanson}
gives the following result immediately.

%The proof below is included for convenience.

\proclaim {Lemma {\TUBXwdash}} Suppose~$0\leq\epsilon\leq1/2$. Then
for any~$W\subset\tW=V(G_p)\setminus(\{x\}\cup V(E))$ we have 
$$
\P(X_W'\geq(1+\epsilon)p^2|\UU||W|)
  \leq\exp\left\{-{1\over3}\epsilon^2p^2|\UU||W|\right\}.
$$ 
\endproclaim
\demo{Proof} We follow an argument of Janson~{\refJanson} (cf.~the
proof of Lemma~2 in~{\refJanson}).
Fix~$W\subset\tW=V(G_p)\setminus(\{x\}\cup V(\UU))$ and let~$w\in W$.
Let~$\cF$ be the family of all copies~$J$ of~$P^3$ with middle
vertex~$w$ and endvertices coinciding with endvertices of edges in~$\UU$
in the complete graph on~$V(G_p)$.  Thus each such~$J$ corresponds to
a triangle determined by~$w$ and one edge from~$\UU$.  Let~$\cF_m$
($m\geq0$) be the collection of all $m$-tuples~$(J_1,\dots,J_m)$ of
pairwise edge-disjoint elements from~$\cF$. Let~$I_J$ be the indicator
variable of the event that a fixed~$J\in\cF$ should be present
in~$G_p$. Thus~$k_3(\UU,w)=X_w=\sum_{J\in\cF}I_J$. We have
$$
\eqalign{
&\E(\e^{tX_w'})=\E\Bigg\{\sum_{m\geq0}{X_w'\choose m}(\e^t-1)^m\Bigg\}
  \leq\E\Bigg\{\sum_{m\geq0}
    {1\over m!}\sum_{\cF_m}I_{J_1}\dots I_{J_m}\(\e^t-1\)^m\Bigg\}\cr
&\qquad=\sum_{m\geq0}{1\over m!}
    \sum_{\cF_m}p^{2m}\(\e^t-1\)^m
  \leq\sum_{m\geq0}{1\over m!}
    \Bigg\{\sum_{\cF}p^2\(\e^t-1\)\Bigg\}^m
  =\e^{\lambda(\e^t-1)}, \cr
}
$$
where~$\lambda=\E(X_w)$. Now, the~$X_w'$ ($w\in W$) are
independent and therefore
$$
\E(\e^{tX_W'})=\E(\e^{t\sum_{w\in W}X_w'})
  =\prod_{w\in W}\E(\e^{tX_w'})
  \leq\e^{\lambda|W|(\e^t-1)}. 
$$
Let~$a\geq1$. Note that then, by Markov's inequality, we have
$$
\eqalign{
&\P(X_W'\geq a\lambda|W|)
  =\P(\e^{tX_W'}\geq\e^{ta\lambda|W|})\cr
&\qquad\qquad\leq\E(\e^{tX_W'})\e^{-ta\lambda|W|}
     \leq\e^{\lambda|W|(\e^t-1)}\e^{-ta\lambda|W|}
     =\e^{\lambda|W|(\e^t-1-at)}.\cr
}
$$
Taking~$t=\log a$, we have
$$
\P(X_W'\geq a\lambda|W|)\leq\e^{\lambda|W|(a-1-a\log a)}
  =\e^{-\lambda|W|(a\log a-a+1)}. 
$$
Our lemma follows by setting~$a=1+\epsilon$ in this last inequality.   
\qed\enddemo

We are finally ready to prove Lemma~{\TrigUpBd}. 

\demo{Proof of Lemma~{\TrigUpBd}}
Take~$C_0=C_0(c_1,c_2,\theta)=\{12/(\theta^2c_1c_2)\}^{1/5}$. We
proceed to show that this choice for~$C_0$ will do.  Thus let~$x$,
$\UU$, and~$W$ as in the statement of our lemma be given. To
prove~{\eqnoTrigUpBdBd}, it suffices to put together~{\eqnoTUBeqSum}
and Lemmas~{\TUBa}, {\TUBYxy}, and~{\TUBXwdash}. Indeed, with the
notation as above, by Lemma~{\TUBXwdash} we have
$$
\P\(X_W'\geq\(1+{\theta\over2}\)p^2|\UU||W|\)
  \leq\exp\left\{-{1\over3}\(\theta\over2\)^2p^2|\UU||W|\right\}
  \leq\e^{-n}, 
$$
where in the last inequality we used that~$|\UU|\geq c_1p^3n^2$,
$|W|\geq c_2n$, and~$C_0=\{12/(\theta^2c_1c_2)\}^{1/5}$.  

The number of choices for the triple~$(x,\UU,W)$ is at
most~$n\exp\{2\omega^3n^{4/5}\log n\}2^n$. Indeed, it suffices to 
notice that we may assume that~$|\UU|\leq u_0=\lfloor
p^3n^2\rfloor=\lfloor\omega^3n^{4/5}\rfloor$, and hence  
the number of choices for~$\UU$ is at most
$$
\sum_{u\leq u_0}{n^2\choose u}\leq2{n^2\choose u_0}
  \leq\exp\{2\omega^3n^{4/5}\log n\}.
$$
Thus almost every~$G_p$ is such
that~$X_W'\leq(1+\theta/2)p^2|\UU||W|$. 

 From~{\eqnoTUBeqSum} and Lemmas~{\TUBa} and~{\TUBYxy}, we have, for
almost every~$G_p$,
$$
k_3(\UU,W)\leq\(1+{\theta\over2}\)p^2|\UU||W| 
      +220\e^3\max\{\log n,\omega^5\}\omega^8n^{4/5}, 
$$
which is at most~$(1+\theta)p^2|\UU||W|$, as required.\qed
\enddemo

In our next lemma we give a set of conditions that ensures
that~$k_3^{G_p}(\UU,W)$ ($\UU\subset E(G_p)$, $W\subset V(G_p)\setminus
V(\UU)$) concentrates around its mean.

\proclaim{Lemma {\TrigUpBdB}} Suppose~$\omega=\omega(n)\to\infty$
as~$n\to\infty$. Let~$0<p=p(n)\leq1$ with~$p\geq\omega n^{-1/2}\log n$
be given.  Then almost every~$G_p=G_{n,p}$ is such that, for
any~$\UU\subset E(G_p)$ and~$W\subset V(G_p)\setminus V(\UU)$
with~$|\UU|\geq\omega np^{-1}\log n$ and~$|W|\geq n/\log n$, we have
$$
k_3(\UU,W)=k_3^{G_p}(\UU,W)=(1+o(1))p^2|\UU||W|. 
\slabel{UWb}
$$
\endproclaim
\demo{Proof} Let~$\theta>0$ be fixed. Let~$M\subset E(K^n)$ be a
matching in the complete graph~$K^n$, and set~$\nu=|M|$. Suppose
that~$\nu p^2/\log n\to\infty$ as~$n\to\infty$. Let~$W\subset
V(G_p)\setminus V(M)$ be such that~$w=|W|\geq n/\log n$.  Let us
write~$k_3'(M,W)=k_3^{G_p\cup M}(M,W)$ for the number of triangles
in~$G_p\cup M$ that are determined by an edge of~$M$ and a vertex
of~$W$. Note that~$k_3'(M,W)$ has binomial distribution with
parameters~$\nu w=|M||W|$ and~$p^2$. Thus
$$
k_3'(M,W)=(1+O_1(\theta))p^2|M||W|
\slabel{kMW}
$$ 
with probability~$1-\exp\{-\Omega(p^2\nu w)\}$. The number of
matchings~$M\subset E(K^n)$ of cardinality~$\nu$ is no larger
than~${{n\choose2}\choose\nu}\leq n^{2\nu}$, and the number of
sets~$W$ as above is no larger than~${n\choose w}\leq n^w$.
Hence, we see that~{\eqnokMW} holds a.s.~for any matching~$M\subset 
E(K^n)$ with~$|M|\geq\nu_0=\omega(\log n)/4p^2$ and any~$W\subset
V(G_p)\setminus V(M)$ with~$|W|\geq n/\log n$, since 
$$
\eqalignno{
\sum_{\nu\geq\nu_0}\sum_{w\geq n\log n}n^{2\nu+w}\exp\{-p^2\nu w\} 
  &\leq\sum_{\nu\geq\nu_0}n^{2\nu}\sum_{w\geq n\log n}
     \(n\e^{-\Omega(p^2\nu)}\)^w\cr
  &\leq\sum_{\nu\geq\nu_0}n^{2\nu-\Omega(p^2\nu n/\log n)}\cr
  &=o(1).\cr
}
$$
Thus, let us assume that our~$G_p$ does have this property. Clearly,
we may also assume that~$\Delta(G_p)\leq2pn$.  We claim that under
these assumptions our~$G_p$ necessarily satisfies~{\eqnoUWb}
with~`$o(1)$' replaced by~`$O_1(\theta)$' for all~$\UU$ and~$W$ as in
the statement of our lemma. To see this, fix~$\UU\subset E(G_p)$
and~$W\subset V(G_p)\setminus V(\UU)$ as in the lemma. We shall now make
use of the following simple fact that may be easily deduced from
Vizing's theorem: if~$J$ is a graph of maximum degree~$\Delta(J)$,
then~$J$ admits a proper edge-colouring with at most~$\Delta(J)+1$
colours such that the cardinality of any two colour classes differ by
at most~$1$.  Note
that~$\Delta(\UU)=\Delta(G_p[\UU])\leq\Delta(G_p)\leq2pn$, and hence, by
the observation above, we may write~$\UU=\UU_1\cup\dots\cup \UU_q$ where
the~$\UU_i$ are matchings satisfying~$\big||\UU_i|-|\UU_j|\big|\leq1$ for
all~$i$ and~$j$, and moreover~$q\leq\Delta(\UU)+1\leq3pn$. In
particular, $|\UU_i|\geq|\UU|/4pn\geq\nu_0$ for
all~$i$. Therefore~{\eqnokMW} applies with~$M=\UU_i$ and,
since~$k_3(\UU,W)=\sum_{1\leq i\leq q}k_3(\UU_i,W)$, our claim does hold.
Lemma~{\TrigUpBdB} follows by letting~$\theta$ tend to~$0$.  \qed
\enddemo

\head\S3. Pivotal Pairs of Vertices
\endhead

\subhead3.1. A weighted Tur\'an type result
\endsubhead
Let~$\Hstar$ be a graph and~$r\geq3$ an integer. Let us write~$K^r_-$
for the graph with~$r$ vertices and~${r\choose2}-1$ edges, and let us
say that its two vertices of degree~$r-2$ are the {\deffont
endvertices\/} of~$K^r_-$.  Let us say that the unordered
pair~$xy=\{x,y\}$ of distinct vertices of~$\Hstar$ is a {\it
$K^r_-$-connected\/} pair if there is a copy of~$K^r_-$ in~$\Hstar$
with endvertices~$x$ and~$y$.  Hence, if~$xy$ is a $K^r_-$-connected
pair of non-adjacent vertices, then the addition of~$xy$ to~$\Hstar$
creates a new copy of~$K^r$ in~$\Hstar$.  Thus, we shall also say that
a $K^r_-$-connected pair is {\deffont$K^r$-pivotal\/}, or simply
{\deffont pivotal\/}.  For technical reasons, let us also say that the
vertex~$x\in V(\Hstar)$ is by itself a $K^r_-$-connected pair if~$x$
lies in a copy of~$K^{r-1}$ in~$\Hstar$.  The following is an
asymptotic version of Tur\'an's theorem for~$K^r$.

\oldassertion(*) Any graph~$\Hstar$ with~$k$ vertices and~$e(\Hstar)$
edges contains at least 
$$
(r-2)e(\Hstar)-(r-3){k+1\choose2}
$$ 
$K^r_-$-connected pairs of vertices.\qed
\endassertion

\noindent To check that~(*) is indeed an asymptotic form of Turan's
theorem, observe that
if~$\lambda=\lambda(\Hstar)=e(\Hstar){|\Hstar|\choose2}^{-1}$ is the
`density' of~$\Hstar=H_*^k$, then the lower bound in~(*) for the
number of $K^r_-$-connected pairs in~$\Hstar$ is, for large~$k$,
$$
\sim\big((r-2)\lambda-r+3\big){k\choose2}.
\slabel{RoughTuran}
$$ 
Note that~{\eqnoRoughTuran} is bigger than~$(1/(r-1)){k\choose2}$
for~$\lambda>1-1/(r-1)$.  Therefore we may deduce that any
(large)~$\Hstar$ with~$\lambda(\Hstar)>1-1/(r-1)$ necessarily contains
a~$K^r$, which is, of course, a weak form of Tur\'an's theorem.
Unfortunately, (*)~does not seem to imply Tur\'an's theorem for~$K^r$
in its precise form.

In the sequel we shall need, however, a weighted version of~(*)
for~$r=4$.  To describe this version we need some technical
definitions. Also, to simplify the notation we restrict ourselves to
the case~$r=4$.  (The general case does not present any further
difficulty.)  We start with a graph~$\Hstar=H_*^k$ of order~$k$ and
assume~$\gamma=(\gamma_e)_{e\in E(\Hstar)}$ is an assignment of {\it
  weights\/}~$\gamma_e\geq0$ to the edges~$e\in E(\Hstar)$ of~$\Hstar$.
Suppose~$\bfx=(x_1,\dots,x_k)$ is an ordering of the vertices of~$\Hstar$.
For any two not necessarily distinct vertices~$x$, $y\in V(\Hstar)$ that
form a $K^4_-$-connected pair in~$\Hstar$, we let
$$
\eqalign{
w_{\Hstar,\gamma}(x,y)
=\max\{\gamma_1\gamma_2\:\exists z_1,z_2\in V(\Hstar)
       \hbox{ with }
       \gamma_i=\gamma_{z_iy}\hbox{ ($i\in\{1,2\}$)}\qquad&\cr
       \hbox{and }
       xz_1,xz_2,z_1z_2,z_1y,z_2y\in E(\Hstar)\}.&\cr
       }
$$
For convenience, if~$x$, $y$ do not form a $K^4_-$-connected pair, we
put~$w_{\Hstar,\gamma}(x,y)=0$. Let 
$$
w(\Hstar,\gamma,\bfx)
  =\sum_{1\leq i\leq j\leq k}w_{\Hstar,\gamma}(x_i,x_j)
$$
and~$\gamma(\Hstar)=\sum_{e\in E(\Hstar)}\gamma_e$. Our weighted
version of~(*) for~$r=4$ is given in Lemma~{\WeightedTu} below. We
remark that to deduce the unweighted case~(*) for~$r=4$ from this
lemma, it suffices to take~$\bgamma=1$ and~$\gamma_e=1$ for all
edges~$e\in E(\Hstar)$. 

\proclaim {Lemma {\WeightedTu}} Let~$\Hstar=H_*^k$ be a graph of order~$k$
and edge weights~$\gamma=(\gamma_e)_{e\in E(\Hstar)}$
with~$0\leq\gamma_e\leq\bgamma$ for all~$e\in E(\Hstar)$,
where~$\bgamma\geq1$.  Then there is an
ordering~$\bfx=(x_1,\dots,x_k)$ of the vertices of~$\Hstar$ for which we
have
$$
w(\Hstar,\gamma,\bfx)\geq2\gamma(\Hstar)-\bgamma{k+1\choose2}.
\slabel{Weighted}
$$
\endproclaim
\demo{Proof} Our proof is by induction on~$k$. Since the case~$k\leq3$
is trivial, we assume that~$k\geq4$ and that our lemma holds for
graphs~$\Hstar$ with at most~$3$ vertices.  Note that
if~$\gamma(\Hstar)\leq\bgamma k^2/4$, then~{\eqnoWeighted} is
trivially true, as in this
case~$2\gamma(\Hstar)-\bgamma{k+1\choose2}\leq\bgamma(k^2/2-k(k+1)/2)
=-\bgamma k/2\leq0$. Thus we may assume that~$\gamma(\Hstar)>\bgamma
k^2/4$.  Since~$\gamma_e\leq\bgamma$ for all~$e\in E(\Hstar)$, we have
that~$\Hstar$ has more than~$k^2/4$ edges. Therefore, there are three
vertices~$y_1$, $y_2$, and~$y_3\in V(\Hstar)$ inducing a triangle
in~$\Hstar$.  For~$y\in V(\Hstar)$, let us
write~$\dgamma(y)=d^{\Hstar,\gamma}(y)
=\sum_{z\in\Gamma_\Hstar(y)}\gamma_{yz}$
for the {\deffont$\gamma$-degree\/} of~$y$. We may assume
that~$\dgamma(y_1)\leq\dgamma(y_2)\leq\dgamma(y_3)$. Put~$x_1=y_1$,
and by induction let~$\bfx'=(x_2,\dots,x_k)$ be an ordering of the
vertices of~$H_*'=\Hstar-x_1=\Hstar-y_1$ such that
$$
w(H_*',\gamma,\bfx')\geq2\gamma(H_*')-\bgamma{k\choose2}. 
$$ 
For simplicity, $\gamma$ above stands for the
restriction~$(\gamma_e)_{e\in E(H_*')}$
of~$\gamma=(\gamma_e)_{E(\Hstar)}$ to~$H_*'$.  Our aim now is to
estimate $\sum_{1\leq i\leq k}w_{\Hstar,\gamma}(x_1,x_i)$ from below.
For~$j\in\{2,3\}$, set~$\gamma_i(j)=\gamma_{y_jx_i}$ if~$y_jx_i\in
E(\Hstar)$ and set~$\gamma_i(j)=0$ otherwise. Now observe that,
since~$\bgamma\geq1$, for any reals~$0\leq\alpha\leq\bgamma$
and~$0\leq\beta\leq\bgamma$ we
have~$\alpha\beta\geq\alpha+\beta-\bgamma$. Therefore
$$
\eqalign{
\sum_{1\leq i\leq k}w_{\Hstar,\gamma}(x_1,x_i)
\geq\sum_{1\leq i\leq k}\gamma_i(2)\gamma_i(3)
  \geq\sum_{1\leq i\leq k}\big\{\gamma_i(2)
          +\gamma_i(3)-\bgamma\big\}\quad\qquad&\cr
  =\dgamma(y_2)+\dgamma(y_3)-\bgamma k
     \geq2\dgamma(y_1)-\bgamma k
  =2\dgamma(x_1)-\bgamma k.&\cr
}
$$
Hence, with~$\bfx=(x_1,x_2,\dots,x_k)$, we have
$$
\eqalignno{
&w(\Hstar,\gamma,\bfx)
  \geq\sum_{1\leq i\leq k}w_{\Hstar,\gamma}(x_1,x_i)
                 +w_{H_*',\gamma}(H_*',\gamma,\bfx')\cr
&\qquad\qquad
  \geq2\dgamma(x_1)-\bgamma k+2\gamma(H_*')-\bgamma{k\choose2}
   =2\gamma(\Hstar)-\bgamma{k+1\choose2}, 
}
$$
as required.\qed
\enddemo

\subhead3.2. Pivotal pairs in subgraphs of random graphs
\endsubhead
In this section we turn to the study of $K^4_-$-connected pairs in
subgraphs of random graphs. Recall that given a graph~$H$ and two
distinct vertices~$x$, $y\in V(H)$, we say that the unordered
pair~$xy=\{x,y\}$ is a $K^4_-$-connected pair if they are the
endvertices of a copy of~$K^4_-$ in~$H$, and that a single vertex by
itself forms a $K^4_-$-connected pair if it belongs to a triangle
of~$H$.  Our main aim here is to prove Lemma~{\MainLemma} below, which
roughly says that, if a subgraph~$H\subset G_p=G_{n,p}$ of~$G_p$ is
such that~$e(H)\geq\lambda e(G_p)$ for some fixed~$\lambda>0$
and~$p=p(n)$ is not too small, then the number of $K^4_-$-connected
pairs in~$H$ is, almost surely,
$$
\gtrsim(2\lambda-1){n\choose2}.
$$ 
This result is similar in spirit to assertion~(*) in Section~3.1, but
note that~(*) applied to~$H\subset G_p$ above gives nothing
if~$p=p(n)\to0$ as~$n\to\infty$.  Lemma~{\MainLemma} below remedies
this situation and recovers essentially the same lower bound for the
number of $K^4_-$-connected pairs.

In the sequel, for any given graph~$H$, it will be convenient to
define a graph~$\Pi=\Pi_H$ on~$V(H)$ by letting two distinct
vertices~$x$, $y\in V(H)=V(\Pi)$ be adjacent in~$\Pi$ if and only if
they form a $K^4_-$-connected in~$H$.

\proclaim {Lemma {\MainLemma}} Let a constant~$0<\sigma\leq1$ be given.
Then there is a constant~$C_0=C_0(\sigma)$ that depends only
on~$\sigma$ for which the following holds. If~$p=p(n)=\omega n^{-2/5}$
and~$C_0\leq\omega=\omega(n)=o(n^{1/190})$, then almost
every~$G_p=G_{n,p}$ is such that, for any subgraph~$H\subset
G_p$ of~$G_p$, we have
$$
e(\Pi_H)\geq(2\lambda-1-\sigma){n\choose2}, 
\slabel{MainLemmaEq}
$$
where~$\lambda=e(H)\left\{p{n\choose2}\right\}^{-1}$.
\endproclaim 

Before we proceed, let us remark that we shall apply
Lemma~{\MainLemma} above with~$\sigma$ much smaller than~$\lambda$. In
fact, we shall be interested in the case in which~$\lambda$ is a
little greater than~$2/3$ and~$\sigma$ is very small.

The proof of Lemma~{\MainLemma} is based on the results of the previous
three sections and on a further technical lemma, Lemma~{\ProhiA},
which we now describe.  The context in which Lemma~{\ProhiA} applies
is as follows.  Suppose~$0<\mu\leq1/2$, $0<\kappa\leq1$,
$0<\delta'\leq1$, $0<\bgamma_0\leq1$, and~$0<\brho\leq1/4$ are
constants, and let~$n$ and~$m\geq\kappa n$ be integers. Let
also~$0<p=p(n)\leq1$ be given.  Let~$\bV_1$, $\bV_2$, $\bZ_1$,
and~$\bZ_2$ be pairwise disjoint sets of cardinality~$(1-\mu)m\leq
m_j=|\bV_j|\leq m$ and~$(1-\mu)m\leq m_i'=|\bZ_i|\leq m$ ($i$,
$j\in\{1,2\}$).  Suppose~$\bF=\bF_1\cup\bF_2$ is a graph with~$\bF_j$
a tripartite graph with tripartition~$V(\bF_j)=\bV_j\cup\bZ_1\cup
\bZ_2$ ($j\in\{1,2\}$) and such
that~$E(\bF[\bZ_1,\bZ_2])=E(\bF_j[\bZ_1,\bZ_2])$ for
both~$j\in\{1,2\}$.  For simplicity, put~$\gamma_Z=\dFp(\bZ_1,\bZ_2)$
and let~$\gamma_{ij}=\dFp(\bZ_i,\bV_j)$ for~$i$, $j\in\{1,2\}$.
Suppose further that the following conditions hold:

\roster
\item"{({\it i\/})}"We have~$\gamma_Z\geq\bgamma_0$
  and~$\gamma_{ij}\geq\bgamma_0$ for all~$i$, $j\in\{1,2\}$.
\item"{({\it ii\/})}"At least~$(1-\delta')m_1$ vertices~$x$ in~$\bV_1$
  are such that
  $$
  k_3^\bF(x)
     \geq(1-\brho-\delta')\gamma_{11}\gamma_{21}\gamma_Zp^3m_1'm_2', 
  $$
  where~$k_3^\bF(x)$ is the number of triangles of~$\bF$ that contain~$x$. 
\item"{({\it iii\/})}"At least~$(1-\delta')e(\bF[\bZ_1,\bZ_2])$ edges~$e$
  in~$\bF[\bZ_1,\bZ_2]$ are such that
  $$
  k_3^\bF(e,\bV_2)\geq(1-\delta')\gamma_{12}\gamma_{22}p^2m_2, 
    \slabel{Hjbad}
  $$
  where~$k_3^\bF(e,\bV_2)$ denotes the number of triangles in~$\bF$
  determined by the edge~$e$ and some vertex in~$\bV_2$.
\item"{({\it iv\/})}"Let~$c=\bgamma_0^3\kappa^2/8$.  For any~$x\in\bV_1$,
  $\UU\subset E(\bF[\Gamma_\bF(x)])$, and~$W\subset\bV_2$ with~$|\UU|\geq
  cp^3n^2$ and~$|W|\geq cn$, we have
  $$
  k_3^\bF(\UU,W)\leq\(1+{\delta'\over4}\)p^2|\UU||W|.
  $$
\item"{({\it v\/})}"For all~$\UU\subset E(\bF[\bZ_1,\bZ_2])$
  with~$|\UU|\geq pn^2/\log n$ and~$W\subset\bV_1$ with~$|W|\geq n/\log
  n$, we have~$k_3^\bF(\UU,W)\leq2p^2|\UU||W|$.
\endroster

\noindent We may now state a key technical lemma in the proof of
Lemma~{\MainLemma}. 

\proclaim {Lemma {\ProhiA}} Let constants~$0<\bgamma_0\leq1$
and~$0<\sigma\leq1$ be given. Then, with the notation above,
if~$\delta'\leq\delta_0'=\delta_0'(\bgamma_0,\sigma)
=\sigma^2\bgamma_0/128$ and~$\mu\leq\mu_0=\mu_0(\sigma)=\sigma/8$,
then the number of $K^4_-$-connected pairs~$x_1x_2$ with~$x_j\in
\bV_j$ \rom($j\in\{1,2\}$\rom) is at
least~$(1-\sigma)\gamma_{12}\gamma_{22}m^2$.
\endproclaim 
\demo{Proof} Let us put~$\alpha=\mu_0=\sigma/8$ and note that
then~$\delta_0'=\sigma^2\bgamma_0/128=\alpha^2\bgamma_0^2/2$.
Let~$0<\delta'\leq\delta_0$ and~$0<\mu\leq\mu_0$ be given, and
suppose that~$\bF$ is as described before our lemma. 

In the sequel, an edge~$e\in E(\bF[\bZ_1,\bZ_2])$ will be said to be
{\deffont$(\delta',K^3;\bF_2)$-poor\/} if~{\eqnoHjbad} fails. For~$x\in
\bV_1$, let us write~$\kp3(x)$ for the number of
$(\delta',K^3;\bF_2)$-poor edges~$e\in E(\bF[\bZ_1,\bZ_2])$ induced by the
neighbourhood of~$x$ in~$\bF$.  Let us say that~$x\in\bV_1$ is {\deffont
  unusable\/}
if~$\kp3(x)\geq\alpha\gamma_{11}\gamma_{21}\gamma_Zp^3m_1'm_2'$.  The
proof is now split into a few claims.

\assertion(1) At most~$\alpha m_1$ vertices in~$\bV_1$ are unusable.
\endassertion
\proofofassertion 
Suppose the contrary. Let us consider the number~$N$ of pairs~$(x,e)$
with~$x$ a vertex in~$\bV_1$ and~$e$ a $(\delta',K^3;\bF_2)$-poor edge
in~$E(\bF[\bZ_1,\bZ_2])$ such that there is a triangle of~$\bF$ containing
both~$x$ and~$e$. Since we are assuming that more than~$\alpha m_1$
vertices~$x\in\bV_1$ are unusable, we have
$$
N>\alpha^2\gamma_{11}\gamma_{21}\gamma_Zp^3m_1'm_2'm_1
  \geq\alpha^2\bgamma_0^2\gamma_Zp^3m_1'm_2'm_1. 
  \slabel{Nlb}
$$
We now use condition~({\it v\/}) above to deduce that 
$$
N\leq2p^2m_1\delta'e(\bF[\bZ_1,\bZ_2])
  =2\delta'\gamma_Zp^3m_1'm_2'm_1
  \slabel{Nub}
$$
Comparing~{\eqnoNlb} and~{\eqnoNub}, we obtain
that~$\alpha^2\bgamma_0^2<2\delta'$, contradicting the fact
that~$\delta'\leq\delta_0'=\alpha^2\bgamma_0/2$.  Thus Assertion~1
holds.  
\endproofofassertion

We now observe that condition~({\it ii\/}) above immediately implies
the following.

\assertion(2) For at least~$(1-2\alpha)m_1$ vertices~$x$ in~$\bV_1$, we
have~$k_3^\bF(x)-\kp3(x)\geq c_1p^3n^2$,
where~$c_1=(1-\brho-2\alpha)(1-\mu)^2\kappa^2\bgamma_0^3\geq c$. 
\endassertion

Now let~$x\in\bV_1$ be given. Let~$\UU_x\subset E(\bF[\bZ_1,\bZ_2])$ be the set
of edges~$e$ induced by the neighbourhood of~$x$ in~$\bF$ that are {\it
  not\/} $(\delta',K^3;\bF_2)$-poor. Thus~$|\UU_x|=k_3^\bF(x)-\kp3(x)$. Let
$$
\eqalign{
W_x&=\{y\in\bV_2\:E(\bF[\Gamma_\bF(x)])\cap
                E(\bF[\Gamma_\bF(y)])\neq\emptyset\}\cr 
  &=\{y\in\bV_2\:xy\text{ is a $K^4_-$-connected pair}\}.\cr
}
$$

\assertion(3) For at least~$(1-2\alpha)m_1$ vertices~$x\in\bV_1$, we
have~$|W_x|\geq(1-\sigma/2)\gamma_{12}\gamma_{22}m_2$. 
\endassertion
\proofofassertion 
Let~$x\in\bV_1$ be such that~$|\UU_x|=k_3^\bF(x)-\kp3(x)\geq c_1p^3n^2$, and
suppose that~$|W_x|<(1-\sigma/2)\gamma_{12}\gamma_{22}m_2$. We now
use~({\it iv\/}) above to deduce that
$$
\eqalign{
(1-\delta')\gamma_{12}\gamma_{22}p^2m_2|\UU_x|
 &\leq k_3^\bF(\UU_x,W_x)
  \leq\(1+{\delta'\over4}\)p^2|\UU_x||W_x|\cr
 &\qquad\qquad\leq\(1+{\delta'\over4}\)
        \(1-{\sigma\over2}\)\gamma_{12}\gamma_{22}p^2m_2|\UU_x|, 
}
$$
which is a contradiction since~$1-\delta'>(1+\delta'/4)(1-\sigma/2)$.
Thus any~$x\in\bV_1$ with~$|\UU_x|=k_3^\bF(x)-\kp3(x)\geq c_1p^3n^2$
is such that~$|W_x|\geq(1-\sigma/2)\gamma_{12}\gamma_{22}m_2$, and
hence Assertion~3 follows from Assertion~2. 
\endproofofassertion

 From Assertion~3, we deduce that at least
$$
\eqalign{
(1-2\alpha)&\(1-{\sigma\over2}\)\gamma_{12}\gamma_{22}m_1m_2\cr
  &\quad\geq(1-2\alpha)(1-\mu)^2\(1-{\sigma\over2}\)
                        \gamma_{12}\gamma_{22}m^2
  \geq(1-\sigma)\gamma_{12}\gamma_{22}m^2\cr
}
$$
pairs~$x_1x_2$ ($x_j\in\bV_j$, $j\in\{1,2\}$) are $K^4_-$-connected with
respect to~$\bF$, thereby proving Lemma~{\ProhiA}. \qed
\enddemo

We are now ready to prove Lemma~{\MainLemma}. Our proof will make use
of several of our previous lemmas. 

\demo{Proof of Lemma~{\MainLemma}} Let~$0<\sigma\leq1$ be given. We
now define the many constants with which we shall apply
Lemmas~{\SSzp}, {\MinDegree}, {\CountLemma}, {\CountLemmaCor},
{\TrigUpBd}, {\TrigUpBdB}, {\WeightedTu}, and~{\ProhiA}.

Let~$\gamma_0=\sigma/100$, $\bgamma_0=\gamma_0/2$,
$\alpha=\gamma_0/24\e$ and~$k_0=\lceil100/\sigma\rceil$.
Let~$\delta=(\delta')^2/2$,
where~$\delta'=\sigma^3/2\times10^6\leq\delta_0'
=\delta_0'(\bgamma_0,\sigma/7)=\sigma^2\bgamma_0/6272$.  Note
that~$\delta_0'(\bgamma_0,\sigma/7)$ is as given in Lemma~{\ProhiA}.
We now let
$$
\epsilon=\min\left\{10^{-16}\sigma^6\gamma_0,
             {1\over2}\epsilon_0(\alpha,\bgamma_0,\delta)\right\},
$$
where~$\epsilon_0=\epsilon_0(\alpha,\bgamma_0,\delta)$ is as defined
in Lemma~{\CountLemma}. Put~$\bepsilon=2\epsilon$,
$\rho=2\epsilon/\gamma_0$ and~$\brho=5\epsilon/\gamma_0$.  For later
reference, note that 
$$
\brho={5\epsilon\over\gamma_0}
  \leq5\times10^{-16}\sigma^6
  \leq{\delta\over27}, 
\slabel{brho}
$$
and if~$k\geq k_0$, then, with plenty to spare, we have
$$
{2\sigma\over7(k-1)}+{6\over k-1}\leq{\sigma\over7}, 
\slabel{ineqA}
$$
and
$$
{3\epsilon\over\gamma_0}+{1\over k}\leq{2\over7}\sigma.
\slabel{ineqB}
$$
Set~$\mu=6\epsilon\leq\mu_0(\sigma/7)$,
where~$\mu_0(\sigma/7)=\sigma/56$ is as given in Lemma~{\ProhiA}. Now
let~$K_0=K_0(\epsilon,k_0)$ and~$\eta=\eta(\epsilon,k_0)$ be as given
by Lemma~{\SSzp}. We may assume
that~$\eta\leq\min\{\sigma/7,\epsilon/2K_0$\}.  Put~$\kappa=1/2K_0$,
and let~$c=\bgamma_0^3\kappa^2/8$. Finally,
let~$C_0=C_0(c,c,\delta'/4)$, where~$C_0(c,c,\delta'/4)$ is as given
by Lemma~{\TrigUpBd}. We claim that this choice of~$C_0=C_0(\sigma)$
will do in Lemma~{\MainLemma}, and proceed to prove this assertion.

Let~$p=p(n)=\omega n^{-2/5}$,
where~$C_0\leq\omega=\omega(n)=o(n^{1/190})$. Let us consider the
following conditions for~$G_p=G_{n,p}$. 
\roster
\item"{({\it a\/})}"$G_p$ is $\eta$-upper-uniform and has
  size~$e(G_p)=(1+o(1))p{n\choose2}$. 
\item"{({\it b\/})}"Suppose~$m\geq\kappa n$. Then, for
  any~$T\geq(3/4)\bgamma_0pm^2$ and any~$\bfm=(m_1,m_2,m_3)$
  with~$m/2\leq m_i\leq m$ ($i\in\{1,2,3\}$), our~$G_p$ contains no
  copy of any
  graph~$\bF\in\cF_p^\delta(\bepsilon,\bgamma_0,\brho;\bfm,T)$ as a
  subgraph.
\item"{({\it c\/})}"Inequality~{\eqnoTrigUpBdBd} in Lemma~{\TrigUpBd}
  holds for all~$\UU$ and~$W$ as in the statement of that lemma
  with~$c_1=c_2=c$ and~$\theta=\delta'/4$. 
\item"{({\it d\/})}"Relation~{\eqnoUWb} in Lemma~{\TrigUpBdB} holds
  for all~$\UU\subset E(G_p)$ and~$W\subset V(G_p)\setminus V(\UU)$
  with~$|\UU|\geq pn^2/\log n$ and~$|W|\geq n/\log n$.
\endroster

\claim Conditions~{\rm({\it a\/})--({\it d\/})\/} hold for almost
every~$G_p$.  
\endclaim
\proofoftheclaim Condition~({\it a\/}) clearly holds almost surely.
We use Lemma~{\CountLemma} to prove that~({\it b\/}) holds almost
surely as well.  Let~$\bfm$, $m$, and~$T$ be as in~({\it b\/}). Note
that the number of choices for~$\bfm$ and~$m$ is trivially at
most~$n^4$.  The number of copies of a fixed
graph~$\bF\in\cF_p^\delta(\bepsilon,\bgamma_0,\brho;\bfm,T)$ that the
complete graph~$K^n$ on~$n$ vertices contains is clearly at
most~$n^n$.  Thus, since~$\brho\leq\delta/27$ (see~{\eqnobrho})
and~$\bepsilon=2\epsilon\leq\epsilon_0(\alpha,\bgamma_0,\delta)$,
Lemma~{\CountLemma} applies to give that the expected number of copies
of elements from~$\cF_p^\delta(\bepsilon,\bgamma_0,\brho;\bfm,T)$
that~$G_p$ contains is, for sufficiently large~$n$, at most 
$$
n^{4+n}\big|\cF_p^\delta(\bepsilon,\bgamma_0,\brho;\bfm,T)\big|p^T
  \leq n^{4+n}\alpha^T{3m^2\choose T}p^T
  \leq n^{4+n}\(3\e\alpha pm^2\over T\)^T, 
$$
which, since~$T\geq(3/4)\bgamma_0pm^2$, is at most
$$
n^{4+n}\(8\e\alpha\over\gamma_0\)^T\leq n^{4+n}3^{-T}\leq2^{-T}. 
$$
Summing over all~$T\geq(3/4)\bgamma_0pm^2$, we obtain that~({\it b\/})
holds almost always.  Condition~({\it c\/}) holds almost surely
for~$G_p$ by Lemma~{\TrigUpBd} and the choice of~$C_0$. To check
that~({\it d\/}) holds for a.e.~$G_p$, by Lemma~{\TrigUpBdB} it
suffices to see that~$pn^{1/2}/\log n\to\infty$ and that~$(pn^2/\log
n)\big/np^{-1}\log n\to\infty$ as~$n\to\infty$. This completes the
proof of our claim.
\endproofoftheclaim

In the remainder of the proof, we show that~{\eqnoMainLemmaEq} holds
for any subgraph~$H\subset G_p$ whenever~$G_p$ satisfies
conditions~({\it a\/})--({\it d\/}) above. This clearly proves our
lemma.  Thus let us assume that~$H\subset G_p$ is given and that~$G_p$
satisfies~({\it a\/})--({\it d\/}). We may clearly assume that~$H$ is
a spanning subgraph of~$G_p$.

Let us apply Lemma~{\SSzp} to the $\eta$-upper-uniform graph~$H$,
with parameters~$\epsilon$ and~$k_0$. Let~$V(H)=V_0\cup\dots\cup V_k$
be the $(\epsilon,H,p)$-regular $(\epsilon,k)$-equitable partition we
obtain in this way. Let~$H'$ be the subgraph of~$H$ on~$\bigcup_{1\leq
  i\leq k}V_i$ with~$e\in E(H)$ an edge of~$H'$ if and only if~$e$
joins two vertices that belong to distinct classes of our regular
partition, say, $V_i$ and~$V_j$ ($1\leq i<j\leq k$), with~$(V_i,V_j)$
an $(\epsilon,H,p)$-regular pair and~$\dHp(V_i,V_j)\geq\gamma_0$.  In
the sequel, we let~$m$ stand for the common cardinality of the
sets~$V_i$ ($1\leq i\leq k$).  Recall
that~$\lambda=e(H)\left\{p{n\choose2}\right\}^{-1}$.  We now check the
following simple fact.

\assertion(1) We have~$e(H')\geq(\lambda-\sigma/7)p{n\choose2}$
provided~$n$ is sufficiently large. 
\endassertion
\proofofassertion From the $\eta$-upper-uniformity of~$H$ it
follows that if~$W\subset V=V(H)$, $|W|\geq2\eta n$
then~$e(H[W])\leq(1+\eta)p{|W|\choose2}$.
Hence~$e(H[V_0])\leq(3/5)\epsilon^2pn^2$.  Also, $e_H(V_0,V\setminus
V_0)$ is at most~$(1+\eta)p|V_0||V\setminus V_0|\leq(6/5)\epsilon
pn^2$. Thus the number of edges of~$H$ incident to~$V_0$ is at
most~$4\epsilon p{n\choose2}$ for large enough~$n$.  Now note
that~$\sum e_H(V_i,V_j)$ with the sum over all~$1\leq i<j\leq k$ such
that~$(V_i,V_j)$ is {\it not\/} $(\epsilon,H,p)$-regular is at
most~$\epsilon{k\choose2}(1+\eta)pm^2\leq2\epsilon p{n\choose2}$.
Also, $\sum e_H(V_i,V_j)$ with the sum extended over all~$1\leq
i<j\leq k$ such that~$\dHp(V_i,V_j)\leq\gamma_0$ is at
most~$(1+\eta)\gamma_0{k\choose2}pm^2\leq2\gamma_0 p{n\choose2}$.
Finally, we have that $\sum_{1\leq i\leq k}e(H[V_i])\leq
k(1+\eta)p{m\choose2}\leq(2p/k){n\choose2}$.
Therefore~$|E(H)\setminus
E(H')|\leq(6\epsilon+2/k+2/\gamma_0)p{n\choose2}
\leq(\sigma/7)p{n\choose2}$ if~$n$ is sufficiently large, as required.
\endproofofassertion

We now define a graph~$\Hstar$ on~$[k]=\{1,\dots,k\}$ by letting~$ij$
($1\leq i<j\leq k$) be an edge of~$\Hstar$ if and only if~$(V_i,V_j)$
is an $(\epsilon,H,p)$-regular pair and~$\dHp(V_i,V_j)\geq\gamma_0$.
We write~$\gamma_{ij}$ for~$\dHp(V_i,V_j)$ for all~$ij\in E(\Hstar)$,
and put~$\gamma=(\gamma_e)_{e\in E(\Hstar)}$. Now
put~$\bgamma=1+\sigma/7$, and notice that then the definition
of~$\eta$ and~({\it a\/}) above gives
that~$\gamma_e\leq1+\eta\leq\bgamma$ for all~$e\in E(H_*)$.  

Lemma~{\WeightedTu} now tells us that, suitably adjusting the
notation, the ordering~$\bfx=(1,\dots,k)$ of the vertices of~$\Hstar$
is such that  
$$
w(\Hstar,\gamma,\bfx)=\sum_{1\leq i\leq j\leq k}w_{\Hstar,\gamma}(i,j)
  \geq2\gamma(\Hstar)-\bgamma{k+1\choose2}. 
\slabel{ConsLWTu}
$$
In our next assertion we bound~$\gamma(\Hstar)$. 

\assertion(2) We have~$\gamma(\Hstar)=\sum_{e\in E(\Hstar)}\gamma_e 
\geq(\lambda-\sigma/7){k\choose2}$.
\endassertion
\proofofassertion
Indeed, we have~$e(H')=\sum_{e\in
  E(\Hstar)}\gamma_epm^2=\gamma(\Hstar)pm^2$, and hence, by
Assertion~1, 
$$
\gamma(\Hstar)\geq{1\over m^2}\(\lambda-{\sigma\over7}\){n\choose2}
  \geq\(\lambda-{\sigma\over7}\){n\choose2}\left/{k^2\over n^2}\right.
  \geq\(\lambda-{\sigma\over7}\){k\choose2}.
$$
\endproofofassertion

Our next step relates the number of $K^4_-$-connected pairs meeting
two fixed classes~$V_i$ and~$V_j$ ($1\leq i<j\leq k$) with the
summand~$w_{\Hstar,\gamma}(i,j)$ appearing in~{\eqnoConsLWTu}.

\assertion(3) Suppose~$\iota_1$, $\iota_2\in[k]$ are two distinct
vertices of~$\Hstar$.  Then the number of
$K^4_-$-connected pairs~$x_1x_2$ with~$x_j\in V_{\iota_j}$
$(j\in\{1,2\})$ is at least
$$
(1-\sigma/7-2\epsilon/\gamma_0)w_{\Hstar,\gamma}(\iota_1,\iota_2)m^2. 
$$
\endassertion
\proofofassertion The above assertion is an easy consequence of
Lemma~{\ProhiA}, although we shall have to work a little to check that
that lemma does apply here. 

Let us start by observing that, trivially, if~$\iota_1$ and~$\iota_2$
are not $K^4_-$-connected in~$\Hstar$, then by
definition~$w_{\Hstar,\gamma}(\iota_1,\iota_2)=0$, and hence there is
nothing to prove. Thus let us assume that this is not the case, and
let~$\iota_3$, $\iota_4\in[k]$ be two vertices of~$\Hstar$ such
that~$\iota_1\iota_3$, $\iota_1\iota_4$, $\iota_3\iota_4$,
$\iota_2\iota_3$, $\iota_2\iota_4\in E(\Hstar)$. Choosing~$\iota_3$
and~$\iota_4$ suitably, we may further assume
that~$w_{\Hstar,\gamma}(\iota_1,\iota_2)
=\gamma_{\iota_2\iota_3}\gamma_{\iota_2\iota_4}$.  We may now restrict
our attention to the $4$-partite subgraph of~$H$ induced by
the~$V_{\iota_a}$ ($1\leq a\leq4$).

Let~$J=H[V_{\iota_1},V_{\iota_2},V_{\iota_3},V_{\iota_4}]$ and
write~$L$ for the graph on~$[4]=\{1,2,3,4\}$ isomorphic to~$K^4_-$,
with~$1$ and~$2$ as the endvertices.  We first apply
Lemma~{\MinDegree} to~$J$ to obtain~$\bU_{\iota_a}\subset V_{\iota_a}$
($1\leq a\leq4$) such that the following holds.
Putting~$m_a=|\bU_{\iota_a}|$, we have~$(1-\mu)m\leq m_a\leq m$ for
all~$1\leq a\leq4$ and, furthermore, if~$ab\in E(L)$
and~$x\in\bU_{\iota_a}$, then
$$
d_{ab}(x)=|\Gamma_J(x)\cap\bU_{\iota_b}|
  =(1+O_1(\rho))\dJp(V_{\iota_a},V_{\iota_b})pm. 
\slabel{dab}
$$
Let~$F=J[\bU_{\iota_1},\bU_{\iota_2},\bU_{\iota_3},\bU_{\iota_4}]$.
Since~$\dJp(V_{\iota_a},V_{\iota_b})
=\dFp(\bU_{\iota_a},\bU_{\iota_b})+O_1(\epsilon)$
and $\dFp(\bU_{\iota_a},\bU_{\iota_b})
\geq\gamma_0-\epsilon\geq\bgamma_0=\gamma_0/2$, we
have
$$
\dJp(V_{\iota_a},V_{\iota_b})
  =(1+O_1(2\epsilon/\gamma_0))\dFp(\bU_{\iota_a},\bU_{\iota_b}). 
$$
Moreover, as~$(1-\mu)m\leq m_b\leq m$, we have~$m=(1+O_1(2\mu))m_b$.
Thus, relation~{\eqnodab} gives that, for any~$x\in\bU_{\iota_a}$, 
$$
d_{ab}(x)=(1+O_1(\brho))\dFp(\bU_{\iota_a},\bU_{\iota_b})pm_b, 
$$
where, as defined above, $\brho=5\epsilon/\gamma_0$.  Note also
that~$\bgamma_0\leq\dFp(\bU_{\iota_a},\bU_{\iota_b})
\leq\bgamma=1+\sigma/7$ (cf.~condition~({\it a\/}) above).  

Our immediate aim now is to apply Lemma~{\ProhiA}. To make our current
notation the same as the one used in that lemma, let us
put~$\bV_j=\bU_{\iota_j}$ and~$\bZ_j=\bU_{2+j}$ for~$j\in\{1,2\}$
and~$F_j=J[\bV_j,\bZ_1,\bZ_2]$ ($j\in\{1,2\}$).  Clearly,
$F=J[\bV_1,\bV_2,\bZ_1,\bZ_2]=F_1\cup F_2$
and~$F[\bZ_1,\bZ_2]=F_1[\bZ_1,\bZ_2]=F_2[\bZ_1,\bZ_2]$.
Also, let~$m_j=|\bV_j|$ and~$m_i'=|\bZ_i|$ ($i$, $j\in\{1,2\}$).

Let~$\bfm_j=(m_j,m_1',m_2')$ and~$T_j=e(F_j)\geq(3/4)\bgamma_0pm^2$
($j\in\{1,2\}$). Observe that by~({\it b\/}) above we may
conclude that
$$
F_j=H[\bV_j,\bZ_1,\bZ_2]
 \in\cF_p(\bepsilon,\bgamma_0,\brho;\bfm_j,T_j)
     \setminus\cF_p^\delta(\bepsilon,\bgamma_0,\brho;\bfm_j,T_j)
$$
for both~$j\in\{1,2\}$.  We shall now invoke Lemma~{\ProhiA}, but to
see that that lemma does apply we verify the following claim. 

\claim Conditions~{\rm({\it i\/})--({\it v\/})} given before the
statement of Lemma~{\ProhiA} hold.
\endclaim
\proofoftheclaim Condition~({\it i\/}) has already been seen to hold.
To see that~({\it ii\/}) holds, we simply apply Lemma~{\CountLemmaCor}
to the $(\delta,K^3)$-balanced graph~$F_1$. Now, condition~({\it
iii\/}) clearly holds as~$F_2$ is $(\delta,K^3)$-balanced.  Finally,
condition~({\it iv\/}) is equivalent to~({\it c\/}), while
condition~({\it v\/}) follows from~({\it d\/}). This finishes the
proof of our claim.
\endproofoftheclaim

In view of the above claim and the definitions
of~$\delta_0'=\delta_0'(\bgamma_0,\sigma/7)$
and~$\mu_0=\mu_0(\sigma/7)$, we see that we may indeed apply
Lemma~{\ProhiA} to deduce that the number of $K^4_-$-connected
pairs~$x_1x_2$ with~$x_j\in V_{\iota_j}$ $(j\in\{1,2\})$ is at least
$$
\(1-{\sigma\over7}\)\dFp(\bZ_1,\bV_2)\dFp(\bZ_2,\bV_2)m^2. 
\slabel{NumberPivPairs}
$$
We now use that, for~$i\in\{1,2\}$, we have 
$$
\dFp(\bZ_i,\bV_2)\geq\dHp(V_{\iota_2},V_{\iota_{i+2}})-\epsilon
  \geq\(1-{\epsilon\over\gamma_0}\)
       \dHp(V_{\iota_2},V_{\iota_{i+2}}), 
$$ 
since~$\dHp(V_{\iota_2},V_{\iota_{i+2}})\geq\gamma_0$. Thus the
quantity in~{\eqnoNumberPivPairs} is at least
$$
\eqalign{
\(1-{\sigma\over7}\)\(1-{\epsilon\over\gamma_0}\)^2
  \dHp(V_{\iota_2},V_{\iota_3})\dHp(V_{\iota_2},V_{\iota_4})m^2
   \qquad\qquad\qquad&\cr
\geq\(1-{\sigma\over7}-{2\epsilon\over\gamma_0}\)
    \gamma_{\iota_2\iota_3}\gamma_{\iota_2\iota_4}m^2,&\cr  
}
$$
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%$$
%\eqalign{
%&\(1-{\sigma\over7}\)
%    \dFp(\bZ_1,\bV_2)\dFp(\bZ_2,\bV_2)m^2\cr
%  &\qquad\qquad\qquad\geq\(1-{\sigma\over7}\)\(1-{\epsilon\over\gamma_0}\)^2
%    \dHp(V_{\iota_2},V_{\iota_3})\dHp(V_{\iota_2},V_{\iota_4})m^2\cr
%  &\qquad\qquad\qquad\geq\(1-{\sigma\over7}-{2\epsilon\over\gamma_0}\)
%    \gamma_{\iota_2\iota_3}\gamma_{\iota_2\iota_4}m^2,\cr
%%  &\qquad\qquad\qquad\geq\(1-{\sigma\over7}-{2\epsilon\over\gamma_0}\) 
%%    w_{\Hstar,\gamma}(\iota_1,\iota_2)m^2,\cr
%}
%$$
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
which concludes the proof Assertion~3, since~$\iota_3$ and~$\iota_4$
were chosen so as to have $w_{\Hstar,\gamma}(\iota_1,\iota_2) 
=\gamma_{\iota_2\iota_3}\gamma_{\iota_2\iota_4}$. 
\endproofofassertion

The proof of our lemma is completed in the next assertion.  Recall
that~$\Pi_H$ stands for the graph on~$V(H)$ with two vertices of~$H$
adjacent in~$\Pi_H$ if and only if they are $K^4_-$-connected in~$H$.

\assertion(4) We have~$e(\Pi_H)\geq(2\lambda-1-\sigma){n\choose2}$.  
\endassertion
\proofofassertion 
By Assertion~3 we have that 
$$
e(\Pi_H)
  \geq\sum_{1\leq i<j\leq k}e(\Pi_H[V_i,V_j])
  \geq\sum_{1\leq i<j\leq k}
     \(1-{\sigma\over7}-{2\epsilon\over\gamma_0}\)  
       w_{\Hstar,\gamma}(i,j)m^2.
\slabel{SizePiH}
$$
Now, clearly, we have
$$
\eqalign{
\sum_{1\leq i<j\leq k}w_{\Hstar,\gamma}(i,j)
  &=w(\Hstar,\gamma,\bfx)
   -\sum_{1\leq i\leq k}w_{\Hstar,\gamma}(i,i)\cr
  &\qquad\qquad\geq w(\Hstar,\gamma,\bfx)-\bgamma^2k
   \geq w(\Hstar,\gamma,\bfx)-2k,\cr
}
$$
since~$\bgamma^2=(1+\sigma/7)^2\leq2$. Thus, recalling~{\eqnoConsLWTu}
and using that~$m\geq(1-\epsilon)n/k$, we have from~{\eqnoSizePiH}
that~$e(\Pi_H)$ is at least  
$$
\eqalignno{
&\(1-{\sigma\over7}-{2\epsilon\over\gamma_0}\)
  (1-\epsilon)^2{n^2\over k^2}
    \bigg(w(\Hstar,\gamma,\bfx)-2k\bigg)\cr 
&\qquad\qquad\qquad\geq\(1-{\sigma\over7}-{3\epsilon\over\gamma_0}\) 
     {n^2\over k^2}\(2\gamma(\Hstar)-\bgamma{k+1\choose2}-2k\),\cr
}
$$
which, by Assertion~2, is at least
$$
\(1-{\sigma\over7}-{3\epsilon\over\gamma_0}\)\(1-{1\over k}\)
  \bigg(2\(\lambda-{\sigma\over7}\)- 
        \(1+{\sigma\over7}\){k+1\choose2}{k\choose2}^{-1} 
                              -2k{k\choose2}^{-1}\bigg){n\choose2},
$$
which is, as one may check using~{\eqnoineqA} and~{\eqnoineqB}, at
least 
$$
\(1-{\sigma\over7}-{3\epsilon\over\gamma_0}-{1\over k}\)
     \(2\lambda-1-{4\sigma\over7}\){n\choose2}
  \geq(2\lambda-1-\sigma){n\choose2},
$$
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%$$
%\eqalignno{
%&\(1-{\sigma\over7}-{2\epsilon\over\gamma_0}\)
%  (1-\epsilon)^2{n^2\over k^2}
%    \bigg(w(\Hstar,\gamma,\bfx)-\bgamma^2k\bigg)\cr 
%&\quad\qquad\geq\(1-{\sigma\over7}-{3\epsilon\over\gamma_0}\)
%     {n^2\over k^2}\(2\gamma(\Hstar)-\bgamma{k+1\choose2}-2k\)\cr
%&\quad\qquad
%  \geq\(1-{\sigma\over7}-{3\epsilon\over\gamma_0}\)\(1-{1\over k}\)\cr    
%  &\qquad\qquad\qquad\times\bigg(2\(\lambda-{\sigma\over7}\)-
%        \(1+{\sigma\over7}\){k+1\choose2}{k\choose2}^{-1} 
%                              -2k{k\choose2}^{-1}\bigg){n\choose2}\cr
%&\quad\qquad
%   \geq\(1-{\sigma\over7}-{3\epsilon\over\gamma_0}-{1\over k}\)
%     \(2\lambda-1-{4\sigma\over7}\){n\choose2}\cr
%&\quad\qquad\geq(2\lambda-1-\sigma){n\choose2},\cr
%}
%$$
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
proving Assertion~4. 
\endproofofassertion
The proof of Lemma~{\MainLemma} is complete. 
\qed
\enddemo

\head\S4. Proof of the Main Result
\endhead

%\subhead4.1. 
%\endsubhead

We first prove Theorem~{\MainThm} under the extra hypothesis
that~$p=p(n)$ should not be too large.  More precisely, we prove the
following result. Recall that we write~$G\to_\gamma H$ if any
subgraph~$J$ of~$G$ with~$e(J)\geq\gamma e(G)$ contains a copy of~$H$. 

\proclaim{Lemma {\NearMainThm}} Let a constant~$\eta>0$ be given.
Then there is a constant~$C=C(\eta)$ that depends only on~$\eta$ for
which the following holds. If~$0\leq p=p(n)=\omega n^{-2/5}\leq1$
and~$C\leq\omega=\omega(n)=o(n^{1/190})$, then almost
every~$G_p=G_{n,p}$ is such that~$G_p\to_{2/3+\eta}K^4$.
\endproclaim
\demo{Proof} Let~$\epsilon=\sigma=\eta/10$
and~$k=\lceil1+24(\log2)\eta^{-2}\rceil$.  Let~$C=kC_0(\sigma)$,
where~$C_0(\sigma)$ is as given in Lemma~{\MainLemma}. We shall show
that this choice of~$C=C(\eta)$ will do in our result.  Thus
let~$p=p(n)$ be as in the statement of Theorem~{\MainThm}, and
consider the space~$\cG(n,p)$ of the random graphs~$G_{n,p}=G_p$.  In
this proof, we shall write~$G_p$ as a union of sparser, independent
random graphs.

Let~$p_1$ be such that~$1-p=(1-p_1)^k$, and note that then~$p/k\leq
p_1=(1+o(1))p/k$.  Put~$\Omega=\prod_{1\leq j\leq k}\cG(n,p_1)$.  We
shall write~$\bfG=(\Gp11,\dots,\Gp1k)$ for a general random element
of~$\Omega$.  Thus the~$G_{p_1}^{(j)}$ ($1\leq j\leq k$) are
independent random graphs, each taken from~$\cG(n,p_1)$.  For any
given~$\bfG=(\Gp11,\dots,\Gp1k)\in\Omega$, let us
put~$G_p=G_p(\bfG)=\Gp11\cup\dots\cup\Gp1k$, and note that then the
map~$\bfG=(\Gp1j)_{1\leq j\leq k}\in\Omega\mapsto
G_p=G_p(\bfG)\in\cG(n,p)$ is measure-preserving.  We may thus
study~$\cG(n,p)$ investigating the random elements~$\bfG\in\Omega$.
Let us define~$\Omega'\subset\Omega$ by letting~$\bfG=(\Gp1j)_{1\leq
  j\leq k}\in\Omega$ belong to~$\Omega'$ if and only if ({\it
  i\/})~$e(G_p)=(1+O_1(\epsilon))p{n\choose2}$, ({\it
  ii\/})~$e(\Gp1j)=(1+O_1(\epsilon))(p/k){n\choose2}$ for all~$1\leq
j\leq k$ and, finally, ({\it iii\/})~for all~$1\leq j\leq k$, the
graph~$\Gp1j$ has the property that if~$E\subset E(\Gp1j)$
and~$\lambda=|E|\left\{p_1{n\choose2}\right\}^{-1}$, then
$$
e(\Pi_E)\geq(2\lambda-1-\sigma){n\choose2}.
\slabel{PiE} 
$$
For simplicity, $\Pi_E$ above stands for~$\Pi_H$, where~$H=H(E)$ is
the graph on~$V(G_p)$ with edge set~$E$.

Elementary facts concerning random graphs and Lemma~{\MainLemma} gives
that~$\P(\Omega')=1-o(1)$. In the sequel, we shall often condition
on~$\Omega'$ and we shall write~$\P'(A)$ for the conditional
probability~$\P(A\cond\Omega')$ for any event~$A\subset\Omega$.

Let~$\cB\subset\Omega$ be the set of~$\bfG=(\Gp11,\dots,\Gp1k)$ that
admit a set~$F\subset E(G_p)$ with~$|F|\geq(2/3+\eta)e(G_p)$
but~$G_p[F]\not\supset K^4$.  We need to show that~$\P(\cB)=o(1)$,
or, equivalently, that~$\P'(\cB)=o(1)$.  Let us
put~$\cB'=\cB\cap\Omega'$. For each~$\bfG\in\cB$, let us fix once and
for all a set~$F=F(\bfG)\subset E(G_p)$ as required in the definition
of~$\cB$.  Let us also put~$F^{(j)}=F^{(j)}(\bfG)=F\cap E(\Gp1j)$
($1\leq j\leq k$) and set~$f=f(\bfG)=|F|$
and~$f^{(j)}=f^{(j)}(\bfG)=|F^{(j)}|$ ($1\leq j\leq k$).  

Now let~$\gamma^{(j)}=\gamma^{(j)}(\bfG)=f^{(j)}/p_1{n\choose2}$, and
note that then we have~$f\leq f^{(1)}+\dots+f^{(k)}$, and hence that
$$
{2\over3}+\eta
  \leq\gamma^{(1)}{p_1{n\choose2}\over e(G_p)}
      +\dots+\gamma^{(k)}{p_1{n\choose2}\over e(G_p)}
  \leq{1\over k}\(1+\epsilon\over1-\epsilon\)
      \(\gamma^{(1)}+\dots+\gamma^{(k)}\),
$$
from which we conclude that
$$
\gamma^*=\gamma^*(\bfG)=\max_{1\leq j\leq k}\gamma^{(j)}
  \geq\Ave_{1\leq j\leq k}\gamma^{(j)}
  \geq{1-\epsilon\over1+\epsilon}\({2\over3}+\eta\)
  \geq{2\over3}(1+\eta), 
\slabel{LowerBdGammaStar}
$$
where the last inequality follows from the choice of~$\epsilon$. Let
us also note that 
$$
\gamma^*\leq1+\epsilon, \slabel{UpBdGammaStar}
$$
since we are assuming that~({\it ii\/}) above holds. For
each~$1\leq j\leq k$, let 
$$
\cB_j'=\{\bfG\in\cB'\:\gamma^{(j)}(\bfG)=\gamma^*(\bfG)\}. 
$$
Clearly~$\cB'=\bigcup_{1\leq j\leq k}\cB_j'$, and hence it suffices to
show that~$\P'(\cB_j')=o(1)$ for all~$j$.  Thus we now {\it
  fix\/}~$j\in[k]$ and proceed to show that~$\cB_j'$ almost
surely does not hold. We have
$$
\eqalignno{
\P'(\cB_j')
  &=\sum_{G_0}\P'(\cB_j'\cap\{\bfG\in\Omega:\Gp1j=G_0\})\cr 
  &=\sum_{G_0}\P'(\cB_j'\cond\Gp1j=G_0)\P'(\Gp1j=G_0)\cr
  &\leq\max_{G_0}\P'(\cB_j'\cond\Gp1j=G_0),&\alabel{CondProb}\cr
}
$$
where~$G_0$ ranges over all graphs on~$V(G_p)$
with~$e(G_0)=(1+O_1(\epsilon))(p/k){n\choose2}$ and such
that~{\eqnoPiE} holds for all~$E\subset E(G_0)$
with~$\lambda=|E|/p_1{n\choose2}$.  We now {\it fix\/}
one such~$G_0$ and proceed to show an upper bound for~{\eqnoCondProb}.
For each~$F_0\subset E(G_0)$, let
$$
P'(j,G_0,F_0)=\P'(\bfG\in\cB_j'\text{, }F^{(j)}=F_0\cond\Gp1j=G_0). 
\slabel{PjGFdef}
$$
Then
$$
\P'(\cB_j'\cond\Gp1j=G_0)=\sum_{F_0\subset E(G_0)}P'(j,G_0,F_0)
  \leq2^{(1+\epsilon){p\over k}{n\choose2}}
     \max_{F_0\subset E(G_0)}P'(j,G_0,F_0). 
\slabel{PjGF}
$$ 
We now {\it fix\/}~$F_0$ and estimate the last term in~{\eqnoPjGF}
from above.  We may of course assume that~$P'(j,G_0,F_0)>0$ for the
fixed triple~$(j,G_0,F_0)$ under consideration, as otherwise there is
nothing to prove.  Thus we may in particular assume
that~$|F_0|/p_1{n\choose2}\geq(2/3)(1+\eta)$.  Let us
write~$\cB'(j,G_0,F_0)$ for the set of~$\bfG\in\cB_j'$ such
that~$\Gp1j=G_0$ and~$F^{(j)}=F_0$.  To show that~$P'(j,G_0,F_0)$ is
small, we argue that if~$\bfG=(\Gp1i)_{1\leq i\leq
  k}\in\cB'(j,G_0,F_0)$, then the edges of the graphs~$\Gp1i$ ($i\neq
j$, $1\leq i\leq k$) are distributed in a rather unlikely way.

Let~$p_2$ be such that~$1-p_2=(1-p_1)^{k-1}$, and note that
then~$p_2/(k-1)\leq p_1=(1+o(1))p_2/(k-1)$. For any
given~$\bfG=(\Gp1i)_{1\leq i\leq k}\in\Omega$, we write~$\Gp2{\neg j}$
for~$\bigcup_i\Gp1i$, where the union is taken over all~$i\neq j$
($1\leq i\leq k$).  Thus~$\Gp2{\neg j}$ is a random element
from~$\cG(n,p_2)$, and~$G_p=\Gp1j\cup\Gp2{\neg j}$.  Note also that
if~$\bfG\in\Omega'$, then~$e(\Gp2{\neg
  j})\leq(1+2\epsilon)p_2{n\choose2}$. 

For any~$\bfG=(\Gp1i)_{1\leq i\leq k}\in\Omega$,
let~$F'=F'(\bfG)=E(\Gp2{\neg j})\cap E(\Pi_{F_0})$.  Also,
let~$f'=f'(\bfG)=|F'|$ for any~$\bfG\in\Omega$.  Clearly,
$f'=f'(\bfG)$ ($\bfG\in\Omega$) is binomially distributed with
parameters~$e(\Pi_{F_0})$ and~$p_2$.  In fact, it is clear
that~$f'=f'(\bfG)$ has this distribution even if we condition
on~$\bfG$ being such that~$\Gp1j=G_0$. We now verify the following
claim, from which we shall deduce an exponential upper estimate
for~$P'(j,G_0,F_0)$.  In the sequel, we write~$\E_{G_0}$ for the
expectation in the space~$\Omega\cap\{\bfG\:\Gp1j=G_0\}$.

\claim If~$\bfG\in\cB'(j,G_0,F_0)$ then~$f'\leq(1-\eta)\E_{G_0}(f')$.
\endclaim
\proofoftheclaim
Let us fix~$\bfG=(\Gp1j)_{1\leq j\leq k}\in\cB'(j,G_0,F_0)$. 
Let~$F^{(\neg j)}=F^{(\neg j)}(\bfG)=F\cap E(\Gp2{\neg j})$, and
put~$f^{(\neg j)}=f^{(\neg j)}(\bfG)=|F^{(\neg
  j)}|$. Clearly~$F^{(\neg j)}\cup F'\subset E(\Gp2{\neg j})$ and, 
since~$F$ spans no~$K^4$, we have~$F^{(\neg j)}\cap F'=\emptyset$.
Thus we have~$f^{(\neg j)}+f'\leq e(\Gp2{\neg
  j})\leq(1+2\epsilon)p_2{n\choose2}$, and hence
$$
f'\leq(1+2\epsilon-\gamma^{(\neg j)})p_2{n\choose2}, 
\slabel{PreUpBd}
$$
where~$\gamma^{(\neg j)}=\gamma^{(\neg j)}(\bfG)=f^{(\neg
  j)}/p_2{n\choose2}$.  We now show that~$\gamma^{(\neg j)}$ is
suitably large.  We have~$f=|F|\leq f^{(j)}+f^{(\neg j)}$, and hence 
$$
{2\over3}+\eta
  \leq\gamma^{(j)}{p_1{n\choose2}\over e(G_p)}
      +\gamma^{(\neg j)}{p_2{n\choose2}\over e(G_p)}
  \leq{1\over k}\(1+\epsilon\over1-\epsilon\)
      \(\gamma^{(j)}+(k-1)\gamma^{(\neg j)}\).
$$
Therefore
$$
{2\over3}(1+\eta)
  \leq{1\over k}\gamma^{(j)}+{k-1\over k}\gamma^{(\neg j)}
  \leq{1\over k}\gamma^*+{k-1\over k}\gamma^{(\neg j)}
  \leq{1\over k}(1+\epsilon)+\gamma^{(\neg j)}, 
$$
where the last inequality follows from~{\eqnoUpBdGammaStar}.  
Thus we conclude that~$\gamma^{(\neg j)}\geq2/3$.  We now note
that~$\mu=\E_{G_0}(f')=p_2e(\Pi_{F_0})
\geq(2\gamma^*-1-\sigma)p_2{n\choose2}$. Note that, in particular, 
by~{\eqnoLowerBdGammaStar} and the choice of~$\sigma$, we 
have~$(1/3)p_2{n\choose2}\leq\mu\leq p_2{n\choose2}$.  Let~$b$ denote  
the right-hand side of~{\eqnoPreUpBd}.  Then 
$$
\eqalign{
\mu-b
  \geq\(2\gamma^*-1-\sigma-1-2\epsilon+\gamma^{(\neg j)}\)
    p_2{n\choose2}\qquad\qquad\qquad\qquad&\cr 
  \geq\({4\eta\over3}-2\epsilon-\sigma\)p_2{n\choose2}
  \geq\eta p_2{n\choose2}\geq\eta\mu,&\cr
}
$$
and therefore~$f'\leq b\leq(1-\eta)\mu$, as claimed.
\endproofoftheclaim

We now use our claim to bound~$P'(j,G_0,F_0)$, which, we recall, is
defined in~{\eqnoPjGFdef} above. Recall also
that~$f'\sim\Bi(e(\Pi_{F_0}),p_2)$.  We have
$$
P'(j,G_0,F_0)
  \leq\P\left\{f'\leq(1-\eta)\E_{G_0}(f')\bigcond\Gp1j=G_0\right\}
  \leq\exp\left\{-{1\over2}\eta^2\mu\right\}, 
$$
where, as remarked before,
$\mu=\E_{G_0}(f')=e(\Pi_{F_0})p_2\geq(1/3)p_2{n\choose2}$. Thus,
from~{\eqnoPjGF} we deduce that
$$
\eqalign{
\P'(\cB_j'\cond\Gp1j=G_0)
  &\leq2^{(1+\epsilon){p\over k}{n\choose2}}
     \exp\left\{-{1\over6}\eta^2\(1-{1\over
       k}\)p{n\choose2}\right\}\cr 
  &=\exp\left\{\((1+\epsilon)(\log2)
     -{k-1\over6}\eta^2\){p\over k}{n\choose2}\right\}\cr 
  &\leq\exp\left\{-{1\over12}\(1-{1\over
    k}\)\eta^2p{n\choose2}\right\}\cr 
  &\leq\exp\left\{-{1\over30}\eta^2pn^2\right\}.
}
$$
We now recall~{\eqnoCondProb} to deduce
that~$\P'(\cB_j')\leq\exp\{\eta^2pn^2/30\}=o(1)$, completing the proof
of Lemma~{\NearMainThm}. 
\qed\enddemo

We next show that, loosely speaking, the
quantity~$\ex(G_{n,p},H)\big\{p{n\choose2}\big\}^{-1}$ is
non-increasing in probability for any fixed graph~$H$. In particular,
this shows that Lemma~{\NearMainThm} implies Theorem~{\MainThm}.

\proclaim{Lemma~{\Monotone}} Suppose~$0\leq p=p(n)\leq1$,
$0<\gamma=\gamma(n)\leq1$, and~$0<\epsilon=\epsilon(n)\leq1$ are such
that~$\epsilon^2\gamma pn^2\to\infty$ as~$n\to\infty$. Suppose also
that~$G_{n,p}\to_\gamma H$ holds almost surely for some graph~$H$. Then, 
if~$0\leq p'=p'(n)\leq1$ is such that~$p'\geq p$ for all large
enough~$n$, we almost surely have~$G_{n,p'}\to_{\gamma(1+\epsilon)}H$.
\endproclaim
\demo{Proof} Write~$\gamma'=\gamma'(n)=\gamma(1+\epsilon)$.
Let~$p'=p'(n)$ be as in the statement of our lemma.  Suppose for a
contradiction that~$G_{n,p'}\to_{\gamma'}H$ fails with probability at
least~$\theta>0$ for arbitrarily large values of~$n$, where~$\theta$
is some positive absolute constant.
Put~$\lambda=\lambda(n)=p(n)/p'(n)\leq1$.  Note that we may
generate~$G_{n,p}$ by first generating~$G_{n,p'}$ and then randomly
removing its edges, each with probability~$1-\lambda$, and with all
these deletions independent. Looking at this method for
generating~$G_{n,p}$, we shall deduce below that the probability that
(*)~$G_{n,p}\to_\gamma H$ fails is at least~$\theta/3$ for arbitrarily
large~$n$, which is a contradiction.

Let~$\delta=\epsilon/4$. For arbitrarily large~$n$, with probability
at least~$2\theta/3$ we have that (\dag)~$G_{n,p'}\to_{\gamma'}H$
fails and~$e(G_{n,p'})=(1+O_1(\delta))p'{n\choose2}$. Suppose that,
when generating~$G_{n,p}$ by the above method, we first generated
a~$G_{n,p'}$ satisfying~(\dag) above. Let~$J=J(G_{n,p'})\subset
G_{n,p'}$ be an $H$-free subgraph of~$G_{n,p'}$
with~$e(J)\geq\gamma'e(G_{n,p'})$.  Clearly, the $H$-free
subgraph~$J_\lambda=J\cap G_{n,p}$ of~$J$ is a subgraph of
our~$G_{n,p}$. We have~$e(J_\lambda)=(1+O_1(\delta))\lambda e(J)$
and~$e(G_{n,p})=(1+O_1(\delta))\lambda e(G_{n,p'})$ with
probability~$1-o(1)$, and hence we have~$e(J_\lambda)\geq\gamma
e(G_{n,p})$ with probability~$1-o(1)$. Therefore, given
that~$G_{n,p'}$ satisfies~(\dag) above, the probability that we
generate a~$G_{n,p}$ for which~(*) fails is~$1-o(1)$. Since the
probability that we generate~$G_{n,p}$ satisfying~(\dag) is at
least~$2\theta/3$ for arbitrarily large~$n$, we conclude that
our~$G_{n,p}$ will fail to satisfy~(*) with probability at
least~$\theta/3$ for arbitrarily large~$n$, which is the contradiction
we were after.  \qed\enddemo

\demo{Proof of Theorem~{\MainThm}} Theorem~{\MainThm} follows at once
from Lemmas~{\NearMainThm} and~{\Monotone}. 
\qed\enddemo

A simple variant of the method used in the proof of Lemma~{\Monotone}
gives the following `equivalence result' between the binomial and the
uniform models of random graphs with respect to the
property~$G\to_\gamma H$.

\proclaim{Lemma {\Equivalence}} Let~$H$ be a graph.  Consider the
following two assertions.  
\roster
\item""\hskip-1.5\parindent$S_{\text{\rm
      bin}}(\gamma,p)\:G_{n,p}\to_\gamma H$ holds almost surely,
\item""\hskip-1.5\parindent$S_{\text{\rm
      unif}}(\gamma,M)\:G_{n,M}\to_\gamma H$ holds almost surely,
\endroster
where~$0<\gamma=\gamma(n)\leq1$, $0<p=p(n)\leq1$,
and~$0<M=M(n)\leq{n\choose2}$ are arbitrary functions.
Suppose~$\omega=\omega(n)\to\infty$ as~$n\to\infty$. Then the
following holds.  
\roster
\item"({\it i\/})"Suppose~$pn^2\to\infty$, $\omega=o(np^{1/2})$,
  and~$h=h(n)=\omega np^{1/2}$.  Let~$\gamma'=\gamma'(n)=\gamma+2h/M'$
  and~$M'=M'(n)=\lceil p{n\choose2}+h\rceil$. Then~$S_{\text{\rm
      bin}}(\gamma,p)$ implies~$S_{\text{\rm unif}}(\gamma',M')$.
\item"({\it ii\/})"Suppose~$M=M(n)\to\infty$, $\omega=o(M^{1/2})$,
  and~$h=h(n)=\omega M^{1/2}$.  Let~$\gamma'=\gamma'(n)=\gamma+2h/M$,
  and~$p'=p'(n)=(M+h){n\choose2}^{-1}$. Then~$S_{\text{\rm
      unif}}(\gamma,M)$ implies~$S_{\text{\rm bin}}(\gamma',p')$.
\endroster
\endproclaim
\demo{Proof} Let us prove~({\it i\/}).  Assume~$S_{\text{\rm
    bin}}(\gamma,p)$ holds. We may generate~$G_{n,M'}$ by first
generating~$G_{n,p}$ conditioned on the event~$E=\{e(G_{n,p})\leq
M'\}$, and then randomly adding~$M'-e(G_{n,p})$ edges to it so as to
have a graph with~$M'$ edges.  For clarity, let us write~$G_{n,p}^E$
for our binomial random graph~$G_{n,p}$ conditioned on~$E$.  Note
that~$\P(E)=1-o(1)$, and hence the effect of conditioning on~$E$ is,
so to speak, negligible.  We now claim that~$G_{n,M'}\to_{\gamma'}H$
holds with probability~$1-o(1)$.

Suppose our claim fails, and hence, for arbitrarily large~$n$, there
exists with probability at least~$\theta>0$ an $H$-free
subgraph~$J\subset G_{n,M'}$ of~$G_{n,M'}$
with~$e(J)\geq\gamma'e(G_{n,M'})$, where~$\theta$ is some positive
absolute constant. Observe that if~$J\subset G_{n,M'}$ is an $H$-free
subgraph of~$G_{n,M'}$, then, obviously, $J'=J\cap G_{n,p}^E\subset
G_{n,p}^E$ is an $H$-free subgraph of~$G_{n,p}^E$.  Now note that
almost surely we have~$M'-e(G_{n,p}^E)\leq 2h$, and hence almost
surely~$\ex(G_{n,p}^E,H)\geq\ex(G_{n,M'},H)-2h$. Since we are assuming
that~$\ex(G_{n,M'},H)\geq\gamma'e(G_{n,M'})$ with
probability~$\theta>0$ for arbitrarily large~$n$, we have
$$
\ex(G_{n,p}^E,H)\geq\gamma'e(G_{n,M'})-2h
             \geq\gamma'M'-2h\geq\gamma e(G_{n,p}^E)
$$ 
with probability~$\theta/2$ for arbitrarily large~$n$.
Since~$G_{n,p}^E$ is the binomial random graph~$G_{n,p}$ conditioned
on the almost sure event~$E$, we deduce that~$\ex(G_{n,p},H)\geq\gamma
e(G_{n,p})$ with probability at least~$\theta/3$ for arbitrarily
large~$n$, contradicting~$S_{\text{\rm bin}}(\gamma,p)$.
Thus~$S_{\text{\rm unif}}(\gamma',M')$ follows. The proof of~({\it
  ii\/}) is similar.  \qed\enddemo

\demo{Proof of Corollary~{\GnMversion}} Corollary~{\GnMversion}
follows easily from Theorem~{\MainThm} and Lemma~{\Equivalence}.
\qed\enddemo

\head\S5. Deterministic Consequences
\endhead

In this section we give a few results concerning the existence of very
sparse graphs~$G=G_\eta$ that satisfy~$G\to_{2/3+\eta}K^4$ for any
fixed~$\eta>0$.

If~$H$ is a graph of order~$|H|\geq3$ and size~$e(H)\geq1$, recall
that its $2$-density is~$d_2(H)=(e(H)-1)/(|H|-2)$.  For an
integer~$k\geq3$, let~$\cH_k$ be the family of all graphs~$H$
with~$3\leq|H|\leq k$, $e(H)\geq1$, and~$d_2(H)>d_2(K^4)$.  Also,
let~$\Forb(\cH_k)$ be the collection of all graphs~$G$ that are
$H$-free for all~$H\in\cH_k$. The following result may be proved by
the so called `deletion method'. (For details, see~{\bf[\refnbHKLodd,
\refnbHKLeven]}.)

\proclaim {Theorem {\MainDetThm}} Let~$0<\eta\leq1/3$
and~$k\geq3$ be fixed. Then there exists a
graph~$G=G_{\eta,k}\in\Forb(\cH_k)$ such that~$G\to_{2/3+\eta}K^4$.
\qed\endproclaim
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% From odd:
%
%\demo{Proof}
%Put~$\eta=\epsilon/2$ and let~$C=C(\ell,\eta/2)$ be as given in
%Theorem~{\MainOddThm}. Let~$p=p(n)=Cn^{-1+1/2\ell}$, and
%consider~$G_p\in\G(n,p)$. Theorem~{\MainOddThm} then tells us
%that~$G_p\to_{1/2+\eta}C^{2\ell+1}$ almost surely, and it is a 
%standard matter to check that a.e.~$G_p$ contains, very generously, at 
%most~$(\epsilon/2)e(G_p)$ copies of elements of~$\cH_{k,\ell}$ as
%subgraphs. Fix a~$G_p$ satisfying both conditions above, and
%let~$G\subset G_p$ be a spanning subgraph of~$G_p$ obtained from~$G_p$
%by the removal of at least one edge from each subgraph of~$G_p$ that
%is a copy of an element of~$\cH_{k,\ell}$, and such
%that~$e(G)\geq(1-\epsilon/2)e(G_p)$. Then
%clearly~$G\in\Forb(\cH_{k,\ell})$. Moreover, we have
%that~$G\to_{1/2+\epsilon}C^{2\ell+1}$. To see this, suppose~$J\subset
%G$ is a subgraph of~$G$ with~$e(J)\geq(1/2+\epsilon)e(G)$.
%Then~$e(J)\geq(1/2)(1+2\epsilon)(1-\epsilon/2)e(G_p)
%\geq(1/2)(1+\epsilon)e(G_p)$. As~$G_p\to_{(1+\epsilon)/2}C^{2\ell+1}$,
%the graph~$J$ must contain a $(2\ell+1)$-cycle and we are done.\qed
%\enddemo
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

We now single out a corollary to Theorem~{\MainDetThm}.  In
Corollary~{\DetCor} below, the property that~$G$ belongs
to~$\Forb(\cH_k)$ in Theorem~{\MainDetThm} is replaced by a collection
of simpler and more concrete conditions. For instance, one of these
conditions is that~$G$ should not contain a copy of~$K^5$.  To state
another condition that appears in Corollary~{\DetCor}, we need to
introduce a definition.

Let~$G$ be a graph.  Suppose~$K_1,\dots,K_h$ ($h\geq2$) are distinct
copies of~$K^4$ in~$G$, and~$e_1\in E(K_1),\dots,e_{h-1}\in
E(K_{h-1})$ are~$h-1$ edges of~$G$ such that~$E(K_i)\cap\bigcup_{1\leq
  j<i}E(K_j)=\{e_{i-1}\}$ and~$V(K_i)\cap\bigcup_{1\leq
  j<i}V(K_j)=V(e_i)$ for all~$2\leq i\leq h$.  Then we say
that~$(K_1,\dots,K_h)$ is an {\deffont$(h,K^4)$-path\/} in~$G$.  Now
assume that~$(K_1,\dots,K_h)$ is an $(h,K^4)$-path in~$G$ and that the
edge~$e\in E(G)$ joins a vertex in~$V(K_1)\setminus\bigcup_{1<j\leq
  h}V(K_j)$ to a vertex in~$V(K_h)\setminus\bigcup_{1\leq i<h}V(K_i)$.
Then, $(K_1,\dots,K_h;e)$ is said to be an
{\deffont$(h,K^4)$-quasi-cycle\/} in~$G$.

It is immediate to check that if~$(K_1,\dots,K_h)$ is an
$(h,K^4)$-path, then~$H=\bigcup_{1\leq j\leq h}K_j$ has
$2$-density~$d_2(H)=d_2(K^4)$. Also, if~$(K_1,\dots,K_h;e)$ is an
$(h,K^4)$-quasi-cycle, then~$H'=H+e$ has
$2$-density~$d_2(H')>d_2(K^4)$.

\proclaim {Corollary {\DetCor}} For any~$0<\eta\leq1/3$ and~$k\geq1$,
there is a graph~$G=G_{\eta,k}$ such that \rom({\it i\/}\rom)~$G$
contains no~$K^5$, \rom({\it ii\/}\rom)~any two copies of~$K^4$ in~$G$
share at most two vertices, \rom({\it iii\/}\rom)~$G$ contains no
$(h,K^4)$-quasi-cycles for any~$2\leq h\leq k$, and \rom({\it
iv\/}\rom)~$G\to_{2/3+\eta}K^4$.\qed
\endproclaim

We remark that Erd\H os and Ne\v set\v ril % (cf.~\refErdos) 
have raised the question as to whether the graphs~$G_{\eta,k}$ as in
Corollary~{\DetCor} exist.

\head\S6. A Conjecture 
\endhead
In this short paragraph we state a conjecture from which, if true, one
may deduce Conjecture~{\MainConj}.  Let~$H=H^h$ be a graph of
order~$|H|=h\geq3$ and suppose~$H$ has vertices~$v_1,\dots,v_h$.
Let~$0<p=p(m)\leq1$ be given.  Let also~$\bfV=(V_i)_{i=1}^h$ be a
family of~$h$ pairwise disjoint sets, each of cardinality~$m$. Suppose
reals~$0<\epsilon\leq1$ and~$0<\gamma\leq1$ and an integer~$T$ are
given. We say that an $h$-partite graph~$F$ with
$h$-partition~$V(F)=V_1\cup\dots\cup V_h$ and size~$e(F)=|F|=T$ is an
{\it$(\epsilon,\gamma,H;\bfV,T)$-graph\/} if the pair~$(V_i,V_j)$ is
$(\epsilon,F,p)$-regular and has
$p$-density~$\gamma\leq\dFp(V_i,V_j)\leq2$ whenever~$v_iv_j\in E(H)$. 

\proclaim{Conjecture {\TechConj}} Let constants~$0<\alpha\leq1$
and~$0<\gamma\leq1$ be given. Then there are
constants~$\epsilon=\epsilon(\alpha,\gamma)>0$ 
and~$C=C(\alpha,\gamma)$ such that, if~$p=p(m)\geq Cm^{-1/d_{23}(H)}$,
the number of $H$-free $(\epsilon,\gamma,H;\bfV,T)$-graphs is
at most
$$
\alpha^T{{h\choose2}m^2\choose T}
$$
for all~$T$ and all sufficiently large~$m$. 
\endproclaim

If~$H$ above is a forest, Conjecture~{\TechConj} holds trivially,
since, in this case, all $(\epsilon,\gamma,H;\bfV,T)$-graphs contain a
copy of~$H$.  A lemma in Kohayakawa, \L uczak, and R\"odl~{\refKLRap}
may be used to show that Conjecture~{\TechConj} holds for the case in
which~$H=K^3$. In fact, this lemma from~{\refKLRap} is similar in
spirit to Lemma~{\FaultyVx} above, although much simpler. 

\head Acknowledgements
\endhead
We are indebted to B.~Kreuter for a careful reading of the manuscript. 

\Refs
\ref\key\refnoBSS
\by Babai, L., \Si, \Sp
\paper Extremal subgraphs of random graphs
\jour\JGT
\vol14
\yr1990
\pages 599--622
\endref

\ref\key\refnoEGT
\by\BB
\book Extremal Graph Theory
\publ Academic Press 
\publaddr London 
\yr1978 
%${\it xx}+488$pp
\endref

\ref\key\refnoBBrgs
\bysame
\book Random Graphs
\publ Academic Press 
\publaddr London 
\yr1985
%${\it xvi}+447$pp
\endref

\ref\key\refnoChung
\by\Chung
\paper Subgraphs of a hypercube containing no small even cycles 
\jour\JGT
\vol16
\yr1992
\pages273--286
\endref

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\ref\key\refnoErdos
%\by\Er
%\paper On some of my conjectures in number theory and combinatorics 
%\jour Congr. Numerantium
%\vol39
%\yr1983
%\pages3--19
%\endref
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\ref\key\refnoErSt 
%\by\Er, Stone, A.H.
%\paper On the structure of linear graphs
%\jour\BAMS
%\vol52
%\yr1946
%\pages1089--1091
%\endref

\ref\key\refnoFR
\by \Fr, \Ro
\paper Large triangle-free subgraphs in graphs without $K_4$
\jour\GC
\vol2
\yr1986
\pages 135--244
\endref

\ref\key\refnoFu
\by\Fu
\paper Random Ramsey graphs for the four-cycle
\jour\DM
\vol126
\yr1994
\pages407--410
\endref

\ref\key\refnoHKL
\by Haxell, P.E., Kohayakawa, Y., \L uczak, T.
\paper The induced size-Ramsey number of cycles
\jour\CPC
\toappear
\endref

\ref\key\refnoHKLodd
\bysame %Haxell, P.E., Kohayakawa, Y., \L uczak, T.
\paper Tur\'an's extremal problem in random graphs: forbidding odd
cycles 
\jour\Comb
\toappear
\endref

\ref\key\refnoHKLeven
\bysame %Haxell, P.E., Kohayakawa, Y., \L uczak, T.
\paper Tur\'an's extremal problem in random graphs: forbidding even
cycles 
\jour\JCTB
\vol64
\yr1995
\pages273--287
\endref

\ref\key\refnoJanson
\by Janson, S.
\paper Poisson approximation for large deviations
\jour\RSA\vol1
\yr1990
\pages221--230
\endref

%\ref\key\refnoKW
%\by Kleitman, D.J., Winston, K.J.
%\paper On the number of graphs without $4$-cycles
%\jour\DM\vol41
%\yr1982
%\pages167--172
%\endref

%\ref\key\refnoKo
%\by Kohayakawa, Y. 
%\paper The regularity lemma of Szemer\'edi for sparse graphs
%\finalinfo manuscript, 1993
%\endref

\ref\key\refnoKKS
\by Kohayakawa, Y., Kreuter, B., Steger, A. 
\paper An extremal problem for random graphs and the number of graphs
with large even-girth  
\finalinfo submitted
\yr1995
\endref

\ref\key\refnoKLRap
\by Kohayakawa, Y., \L uczak, T., \Ro
\paper Arithmetic progressions of length three 
in subsets of a random set
\jour Acta Arithmetica
\toappear
\endref

%\ref\key\refnoLRV
%\by\L uczak, T., Ruci\'nski, A., Voigt, B.
%\paper Ramsey properties of random graphs 
%\jour\JCTB
%\vol56
%\yr1992
%\pages 55--68
%\endref

%\ref\key\refnoRoSzL
%\by \Ro
%\finalinfo Personal communication, July~1993
%\endref

\ref\key\refnoRRa 
\by \Ro, Ruci\'nski, A.
\paper Lower bounds on probability thresholds for Ramsey properties   
\inbook Comb\-in\-ator\-ics---Paul Erd\H os is Eighty (Volume~1) 
\eds Mikl\'os, D., S\'os, V.T., Sz\H onyi, T. 
\publaddr Budapest
\publ Bolyai Soc.\ Math.\ Studies 
\yr1993 
\pages317--346
\endref

%\ref\key\refnoRRab 
%\bysame
%\paper Random graphs with monochromatic triangles in every
%edge colouring
%\jour\RSA
%%\yr1994
%\toappear
%\endref

\ref\key\refnoRRb
\bysame %\Ro, Ruci\'nski, A.
\paper Threshold functions for Ramsey properties 
\jour\JAMS
\toappear
\endref

\ref\key\refnoSz
\by\Sz
\paper Regular partitions of graphs 
\inbook Probl\`emes Combinatoires et Th\'eorie des Gra\-phes, %
        Proc. Colloque Inter. CNRS 
\eds Bermond, J.-C., Fournier, J.-C., Las Vergnas, M., Sotteau, D.
\publ CNRS
\publaddr Paris
\yr1978
\pages399--401
\endref

\endRefs

\enddocument
