k) < \left(\frac{epn}{k}\right)^k < e^{-k}. \leqno{(b)}$$
\end{lemma}
%$$
%\Pr(X\le k) \le
% \left({pn\over k}\right )^k \left({n-pn \over n-k}\right)^{n-k}
%$$
%for $k\le pn$, and
%$$
%\Pr(X\ge k) \le
% \left({pn\over k}\right )^k \left({n-pn \over n-k}\right)^{n-k}
%$$
%for $k\ge pn$.
%\eproof
The main tool in the proofs of Theorems~\ref{upperC4} and~\ref{upperK4} will
be the `step by step' approach of~\cite{moncol}, making use of up-sets and
down-sets.
An {\em up-set} $\U$ on a set $W$ is a collection of subsets of $W$ such that
$A\in \U$ and $A\ss B\ss W$ imply $B\in \U$. A {\em down-set} $\D$ is one where
$A\in \D$ and $B\ss A$ imply $B\in \D$.
In the graph context, $W$ is just the set $V^{(2)}$ of possible edges.
We wish to check that $G_p$ satisfies a certain rather complicated condition
with very high probability.
We do this by considering a (completely impractical) algorithm which checks
whether $G_p$ satisfies this condition `a bit at a time'.
At each stage the algorithm tests whether the edges in a certain set $E$
are all present in $G_p$, basing its subsequent behaviour on the yes/no answer.
We design the algorithm so that the event $\eventA$ that the algorithm reaches
any particular state has the form $\eventA=\U\cap \D$, where $\U$ is a very
simple
up-set, and $\D$ is some down-set. We can then bound the probability
that $E\ss G_p$ given~$\eventA$ using the following lemma from~\cite{moncol},
itself a simple consequence of Kleitman's Lemma~\cite{Kleitman}, which states
that up-sets are positively correlated (see also~\cite{whitebook}, \S 19).
\begin{lemma}\label{quotedCi}
Let ${\bf p}=(p_1,\ldots,p_N)$, where each $p_i$ lies between 0 and 1.
Let $Q_{\bf p}$ be the weighted cube, i.e., the probability space with
underlying set ${\mathcal P}([N])$ where a random subset
$X\subset W=[N]$ is obtained by selecting elements of $W$
independently, with $\Pr(i\in X)=p_i$, $i=1,\ldots,N$. Let
$\U_1$ and $\U_2$ be up-sets with
$\Pr(\U_1\cap\U_2)=\Pr(\U_1)\Pr(\U_2)$ and let $\D$ be a down-set.
Then
$$\Pr(\U_1\cap\U_2\cap\D) \le \Pr(\U_1)\Pr(\U_2\cap\D).$$
\end{lemma}
For the rest of the paper we work with the probability space $\G(n,p)$
of graphs on a fixed vertex set $V$.
In this context an up-set (down-set) is just a monotone increasing (decreasing)
property of graphs on $V$.
Note that we shall not distinguish sets $\eventA$ of graphs on $V$ from
the corresponding events $\{G_p\in \eventA\}$.
With this notation the most convenient form of Lemma~\ref{quotedCi}
is the following.
\begin{lemma}\label{convlem}
Let $G_p$ be a random graph from $\G(n,p)$, let $A$, $B$ be fixed graphs
on $V$ and let $\D$ be a down-set.
Then
$$
\Pr(G_p\sps B \mid \{G_p\sps A\} \cap \D) \le p^{e(B\bs A)}.
$$
\end{lemma}
\bproof
We identify $\G(n,p)$ with the weighted cube $Q_{\bf p}$, where $W=[N]$,
$N=\binom{n}{2}$, and all $p_i$ are equal to $p$.
Let $\U_1=\{G_p\sps B\bs A\}$, $\U_2=\{G_p\sps A\}$, so $\U_1$, $\U_2$
are independent up-sets.
{From} Lemma~\ref{quotedCi} we have
\begin{eqnarray*}
\Pr(G_p\sps B \mid \{G_p\sps A\}\cap \D) &=&
\Pr(G_p\sps B\bs A \mid \{G_p\sps A\}\cap \D) \\
&\le& \Pr(G_p\sps B\bs A) = p^{e(B\bs A)},
\end{eqnarray*}
as required.
\eproof
In the next section we present
an application of this lemma common to the cases $H=C_4$
and $H=K_4$, and in fact much more general.
\section{Subgraphs containing a given edge}\label{mainlem}
In this section
we shall show that if $H$ is edge-balanced, then copies of $H$ containing
a particular edge of $G_p$ arise `more or less independently'.
For $x,y\in V(G_p)$, let $\CH(x,y)$ be the set of graphs $S$ on $V$ such that
$xy\notin S$ and $S\cup\{xy\}$ is isomorphic to $H$.
Let $U_H(G_p,x,y)$ be the union of all subgraphs
$S$ of $G_p$ with $S\in \CH(x,y)$, and let $X_H(G_p,x,y)$
be the number of such subgraphs~$S$.
Thus for $H=C_4$, the graph $U_H(G_p,x,y)$ is the union of all $x$-$y$
paths of length three in $G_p$, and $X_H(G_p,x,y)$ is the number
of such paths;
if the edge $xy$ is present in $G_p$, then $U_H(G_p,x,y)$ is the union
of all $C_4$s in $G_p$ containing $xy$, and $X_H(G_p,x,y)$ the number
of such $C_4$s.
As before we write $X_H(G_p)$ for the total number of copies of $H$ in $G_p$,
and $N$ for $\binom{n}{2}$.
\begin{lemma}\label{Hlem}
Let $H$ be a fixed edge-balanced graph.
Suppose that $p=p(n)$ is chosen such that
$$\E(X_H(G_p)) =\lambda p N,$$
with $\lambda=\lambda(n)$ bounded as $n$ tends to infinity.
Then with probability $1-o(n^{-2})$ we have
(i) $e(U_H(G_p,x,y))\le \log n$ for all $x,y\in V(G_p)$, and
(ii) $X_H(G_p,x,y)\le \log n$ for all $x,y\in V(G_p)$.
\end{lemma}
\bproof
Fix distinct vertices $x$, $y\in V$, and consider $\CH=\CH(x,y)$.
Note that we shall never consider graphs with isolated vertices, so
we may identify a graph $S$ with the set $E$ of its edges.
The idea of the proof is as follows. It is easy to bound the maximum
number $X_0$ of disjoint $E\in\CH$ present in $G_p$.
We consider an algorithm for finding $U_H(G_p,x,y)$ that proceeds
as follows.
First find $\RH{0}\ss G_p$, where $\RH{0}$ is a union of $X_0$ disjoint
$E\in\CH$, $E\ss G_p$.
We will define a random variable $\RM{t}\ss G_p$, the set of `marked
edges', starting with $\RM{0}=\RH{0}$. The variable $\RM{t}$ will
represent the set of edges known to be present in $G_p$ after
$t$ steps of the algorithm. At each step the algorithm considers an
$E\in\CH$ not yet considered, and tests whether $E\ss G_p$. If so,
the edges of $E$ are also marked. Thus $U_H(G_p,x,y)$ is the set of
edges marked when we have considered all $E\in\CH$.
The key point is that the event that the algorithm reaches a particular
state will be such that we can apply Lemma~\ref{convlem}.
This will give an upper bound on the conditional probability that $E\ss G_p$
at each stage.
Note that we expect $\RH{0}$ to be almost all
of $U_H(G_p,x,y)$. The reason is that $H$ is edge-balanced. This means
that the increase in the conditional probability that $E\ss G_p$
due to $E$ containing marked edges is outweighed by the reduction in the
number of choices for such $E\in \CH$---such $E$ must share at least
three vertices (including $x$ and $y$) with the marked edges.
In what follows we often consider both a random subgraph of $G_p$,
and possible values of this subgraph. We shall use bold type for the former,
and italics for the latter. Thus $\RH{0}\ss G_p$ will be a random variable,
and $H_0$ will represent any possible value of this random variable.
We now turn to the proof itself.
As described above we first consider disjoint sets $E\in \CH$.
For each $E\in \CH$ the probability that $E\ss G_p$ is $p^{e(H)-1}$.
Thus, counting the expectation of $e(H)X_H(G_p)$ in two different ways,
we have $e(H)\lambda pN=e(H)\E X_H(G_p)=pN|\CH|p^{e(H)-1}$.
Writing $X_0=X_0(G_p,x,y)$ for the maximum number of disjoint $E\in \CH$
contained in $G_p$, we have
\begin{eqnarray*}
\Pr(X_0\ge C) &\le& \binom{|\CH|}{C} p^{C(e(H)-1)} \\
&\le& \left(\frac{e|\CH|p^{e(H)-1}}{C}\right)^C
= \left(\frac{e\lambda e(H)}{C}\right)^C = o(n^{-4}),
\end{eqnarray*}
if $C\ge \log n/2e(H)$, since then $e\lambda e(H)/C\le e^{-9e(H)}$, for $n$
large. We thus have
\begin{equation}\label{X0small}
\Pr(X_0\ge \log n/2e(H)) = o(n^{-4}).
\end{equation}
In order to start the algorithm described above we need an event to condition
on which is in a suitable form for Lemma~\ref{convlem}.
Let $A_1,A_2,\ldots,A_k=\emptyset$ be all edge sets that are disjoint unions
of sets $E\in \CH$. We order the $A_i$ so that their sizes decrease,
but otherwise arbitrarily.
Let $\RH{0}=\RH{0}(G_p)$ be the subgraph of $G_p$ defined by
$E(\RH{0})=A_i$ for $i=\min\{j:A_j\ss G_p\}$.
Then $E(\RH{0})$ is the union of a largest collection of disjoint $E\in \CH$,
$E\ss G_p$, so $e(\RH{0})=X_0(e(H)-1)$. Thus, from~\r{X0small},
\begin{equation}\label{H0smallb}
\Pr(|\RH{0}| > \log n) = o(n^{-4}).
\end{equation}
Note that the event $\{\RH{0}=A_i\}$ is of the form $\{A_i\ss G_p\}\cap\D$,
where $\D=\bigcap_{j*\alpha_H(2)$ for $2 0$ depending on $H$.
Also, the probability that $e(U_H(G_p,x,y))$ exceeds its expectation by
a factor $C$ can be bounded by $2\bfrac{e}{C}^C$ for $C$ up to
$n^\epsilon$.
Thus copies of $H$ containing $xy$ do arise `almost independently'
in a rather strong sense.
\medskip\noindent
(iii)
Essentially the same proof can be applied to copies of $H\ss G_p$ containing
a particular set of $k$ vertices, with $0\le k < |H|$.
The edge-balanced condition must be replaced by $\alpha_H(v)>\alpha_H(k)$
for $|H|>v>k$. A weak form of the special case $H=K_r$ was Lemma~13
of~\cite{moncol}. Note that the condition on $\alpha_H$ is necessary,
otherwise once we find a suitable $K_{k+1}$ in $G_p$ we find many more
copies of $H$ than expected.
\section{The upper bound for $C_4$-free graphs}\label{uC4}
In this section we prove Theorem~\ref{upperC4}.
Throughout the section we take $p=\frac12n^{-2/3}$,
$m=\floor{n^{1/3}(\log n)^3}$,
and $G_p$ a random graph from $\G(n,p)$.
As before, the graph $G_p'$ is formed from $G_p$ by deleting any edge contained
in a $C_4$ in $G_p$.
Recall that we shall always assume that $n$ is larger than some
very large fixed $n_0$, even when this is not explicitly stated.
The result we shall actually prove is the following.
\begin{lemma}\label{max}
With probability $1-o(n^{-2})$ the graph $G_p$ is such that
every $C_4$-free graph $G''\sps G_p'$ has maximum degree at most $13m$.
\end{lemma}
This implies Theorem~\ref{upperC4} since, using the coupling described
in the introduction, $G_\infty$ is a $C_4$-free graph containing $G_p'$.
The condition described in Lemma~\ref{max} is rather complicated
when we express it in terms of $G_p$,
which we need to do in order to calculate.
We start by establishing some global properties of $G_p$
that hold almost surely.
Then we shall finish with the `step by step' approach
described in \secref{plems}.
Most of the time we shall work with $G_p$ itself, rather than with
$G_p'$. Thus, any graph theoretic notation we use, such as $\Gamma(x)$
for the set of neighbours of $x$, or $d(x)$ for the degree of $x$,
will refer to the graph $G_p$ unless explicitly stated otherwise.
As before, we write $V$ for $V(G_p)$, a fixed set of $n$ vertices.
Let $\B_1$ be the event that some set $X\ss V$ with $100\le k=|X|\le n^{2/5}$
spans at least
$3k$ edges of $G_p$. Then we have
\begin{eqnarray*}
\Pr(\B_1)
&\le& \sum_{k=100}^{n^{2/5}} \binom{n}{k} \binom{\binom{k}{2}}{3k} p^{3k} \\
&\le& \sum_{k=100}^{n^{2/5}} \bfrac{ne}{k}^k \bfrac{ke}{6}^{3k}p^{3k} \\
&\le& \sum_{k=100}^{n^{2/5}} (e^4nk^2p^3)^k.
\end{eqnarray*}
For $k\le n^{2/5}$ we have $nk^2p^3=O(n^{1+4/5-6/3})=O(n^{-1/5})$,
so $\Pr(\B_1)=o(n^{-2})$.
For a set $X\ss V$ let $\Gamma_2(X)$ be the set of vertices $y\notin X$ with
$|\Gamma(y)\cap X|\ge 2$, recalling that $\Gamma(y)$ is the set of neighbours
of $y$ in the graph $G_p$.
For $X\ss V$ with $|X|=2m$, each $y\notin X$ has probability
$p_0\le \binom{2m}{2}p^2\le 2m^2p^2$ of sending at least two edges to $X$.
These events are independent, so
$$ |\Gamma_2(X)|\sim \Bi(n-2m,p_0) $$
with mean at most $np_0\le 2m^2p^2n=O^*(m).$
Thus by Lemma~\ref{Bi}(b) we have
$$ \Pr(|\Gamma_2(X)| > mn^{1/100})\le e^{-mn^{1/100}}. $$
Let $\B_2$ be the event that some set $X\ss V$ with $|X|=2m$ has
$|\Gamma_2(X)| > mn^{1/100}$. Then
$$ \Pr(\B_2)\le \binom{n}{2m}e^{-mn^{1/100}}
\le e^{2m\log n-mn^{1/100}} = o(n^{-2}).
$$
If neither $\B_1$ nor $B_2$ holds, then every set $X$ with $|X|=13m$ contains
a set of $m$ vertices that is rather well behaved.
To formulate this precisely call a set $X\ss V$ {\em good}
if it is an independent set (in $G_p$), and every $x\in X$ sends at
most $n^{1/50}$ edges (of $G_p$) to $\Gamma_2(X)$.
\begin{lemma}\label{b12}
Suppose that neither $\B_1$ nor $\B_2$ holds,
$X_0\ss V$ and $|X_0|=13m$. Then $X_0$ contains a good set $X$ with $|X|=m$.
\end{lemma}
\bproof
As $\B_1$ does not hold, every $Y\ss X_0$ with $100\le |Y|\le n^{2/5}$
induces a graph $G_p[Y]$ with minimum degree less than 6.
We may thus number the vertices of $X_0$ as $x_1,x_2,\ldots$ so that each
of the
first $13m-100\ge 12m$ vertices $x_i$ sends at most $5$ edges to later $x_j$.
We can properly colour $G_p[X_0]$ as follows: colour the last $m$ vertices
arbitrarily, and proceed backwards,
colouring $x_i$ with one of the colours 1 to 6
which does not appear among its later neighbours.
One of the colour classes 1 to 6
in this colouring has at least $12m/6=2m$ vertices,
so we have found $X_1\ss X_0$ spanning no edges of $G_p$,
with $|X_1|=2m$.
We claim that there is a set $X\ss X_1$ with $|X|=m$, such that each
$x\in X$ sends at most $n^{1/50}$ edges to $\Gamma_2(X)$. Such an $X$ would
be a suitable good set.
Suppose that the claim is false.
For any $X\ss X_1$ we have $\Gamma_2(X)\ss Z=X_1\cup \Gamma_2(X_1)$.
More than $m$ vertices of $X_1$ must have degree at least $n^{1/50}$ in
$G_p[Z]$,
as we could otherwise take $m$ other vertices of $X_1$ to form $X$.
Thus $Z$ spans at least $\frac12mn^{1/50}$ edges of $G_p$.
As $\B_2$ does not hold, we have $|Z|\le 2m+mn^{1/100}\le 2mn^{1/100}$.
But then $Z$ spans more than $3|Z|$ edges, while $100\le 2m\le |Z|\le n^{2/5}$,
contradicting the assumption that $\B_1$ does not hold, and proving the claim,
and hence the lemma.
\eproof
We shall define two further `bad' events, $\B_3$ and $\B_4$.
Let $\B_3$ be the event that for some edge $e=xy\in E(G_p)$ the graph
$U_{C_4}(G_p,x,y)$ defined in \secref{plems} has more than $\log n$ edges.
Then by Lemma~\ref{Hlem} we have $\Pr(\B_3)=o(n^{-2})$.
Given $X\ss V$ we shall consider paths $xyz\ss G_p$ with $x,z\in X$,
$y\notin X$.
We shall need these paths not to share more vertices than necessary; we say
that a set $A$ of such paths is {\em independent} (with respect to~$X$)
if any two paths in $A$ have distinct midpoints,
and share at most one endpoint. We write $a(X)$ for the maximum number of paths
in such a set $A$.
Let $X$ have size $m$. We can find a set $A$ as above in the following way:
start with $A=\emptyset$ and consider each $y\notin X$ in turn.
If~$y$ is joined to
exactly two vertices $x,z$ of $X$, and $x,z$ are not the endpoints of a path
in~$A$, add $xyz$ to $A$ and continue to the next $y\notin X$.
Otherwise just continue.
Having found $a$ paths,
for each vertex $y$ considered the probability of
adding a new path is exactly
$$ \left(\binom{m}{2}-a\right) p^2 (1-p)^{m-2}. $$
If $a<\cc=nm^2p^2/8$ then $a\ll\binom{m}{2}$, and as $mp=o(1)$
this probability is at least $m^2p^2/3$.
As we have $n-m$ vertices to consider, the probability that $a(X)<\cc$
is at most the probability that a $\Bi(n-m,m^2p^2/3)$ random variable
is less than $\cc$. By Lemma~\ref{Bi}(a) this is at most $e^{-nm^2p^2/32}$.
Let $\B_4$ be the event that some set $X\ss V$ with $|X|=m$ has $a(X) <\cc$.
Then
$$ \Pr(\B_4)\le \binom{n}{m}e^{-nm^2p^2/32} \le e^{m\log n-nm^2p^2/32}
=o(n^{-2}),
$$
as $nmp^2 \gg\log n$.
The significance of the paths counted by $a(X)$
is shown by the next definition.
We say that a set $X\ss V$ is {\em unusable} if $G_p'$ contains two paths
$x_1y_1z_1$, $x_2y_2z_2$ with $x_i,z_i\in X$ and $y_1\ne y_2$.
We say that $X$ is {\em usable} if it is not unusable.
If $G''\sps G_p'$ is $C_4$-free and $x\in V$, then $X=\Gamma_{G''}(x)$ must
be usable---otherwise there are paths as above in $G_p'\ss G''$
with at least one $y_i$ distinct from $x$.
But then $xx_iy_iz_i$ is a $C_4$ in $G''$.
To prove Lemma~\ref{max} it thus suffices to show that,
with high probability, every set
of $13m$ vertices is unusable.
Recall that a set $X\ss V$ is {\em good} if $X$ spans no edges of $G_p$, and
every $x\in X$ sends at most $n^{1/50}$ edges to $\Gamma_2(X)$.
We shall show that for a fixed $X\ss V$, $|X|=m$, we have
\begin{equation}\label{Xaim}
\Pr(X\hbox{ is good and usable}, \bigcap_{i=1}^4 \B_i^c)
= o(n^{-m}).
\end{equation}
The events $\B_i^c$, $1\le i\le 3$, and the event that $X$ is good
are all down-sets, so we are happy
to condition on these events. The event $\B_4^c$ is not a down-set, however,
so we must treat this event differently.
In particular, instead of~\r{Xaim} we prove the stronger statement
\begin{equation}\label{Xaim'}
\Pr(X\hbox{ is usable}, \B_4^c \mid
X\hbox{ is good} \cap \bigcap_{i=1}^3 \B_i^c)
= o(n^{-m}).
\end{equation}
Before turning to the proof of~\r{Xaim'} we show that~\r{Xaim},
and hence~\r{Xaim'}, does indeed imply Lemma~\ref{max}.
Suppose that~\r{Xaim} holds, and
let $\B_5$ be the event that there is some
$X\ss V$ with $|X|=m$ which is good and usable.
Then~\r{Xaim} implies
that $\Pr(\B_5\bs(\bigcup_{i=1}^4\B_i))=o(\binom{n}{m}n^{-m})=o(n^{-2})$.
We have already shown that $\Pr(\B_i)=o(n^{-2})$ for $i=1,\ldots,4$,
so we have $\Pr(\bigcup_{i=1}^5\B_i)=o(n^{-2})$.
Suppose now that no $\B_i$ holds. If $X_0$ is a set of $13m$ vertices,
then $X_0$ contains a good set $X$ with $|X|=m$ by Lemma~\ref{b12}.
If $X_0$ is usable, then $X$ is good and usable, contradicting the
assumption that $\B_5$ does not hold.
Hence, if no $\B_i$ holds, no set of $13m$ vertices is usable.
As described above, if $G''\sps G_p'$ is $C_4$-free, then the
neighbourhood in $G''$ of any vertex $x$ is usable.
In summary, if~\r{Xaim'} holds, so does~\r{Xaim}. Then
$\Pr(\bigcup_{i=1}^5\B_i)=o(n^{-2})$, and with probability $1-o(n^{-2})$
any $C_4$-free graph $G''\sps G_p'$ has maximum degree less than $13m$.
To prove Lemma~\ref{max}, and hence Theorem~\ref{upperC4},
it thus suffices to prove~\r{Xaim'}.
\proofof{Lemma~\ref{max}}
Fix $X\ss V$ with $|X|=m$. We consider all possible sets $A\ss X\times(V\bs X)$
that are unions of independent paths as described in the definition
of $a(X)$.
Let $A_1,A_2,\ldots$ be these sets listed in decreasing order of size,
and define a random variable $\RA$ by $\RA=A_i$ where $i=\min\{j:A_j\ss G_p\}$.
Then $\RA$ is a largest such set present in $G_p$,
and by definition $\RA$ consists
of $a(X)$ independent paths.
Our goal is to prove~\r{Xaim'}; since
the event that $X$ is good and $\bigcap_{i=1}^3\B_i^c$ holds is a
disjoint union of events $\event$ of the form
$$
\event=\{\RA=A, X\hbox{ is good}, \bigcap_{i=1}^3\B_i^c\},
$$
it suffices to show that
\begin{equation}\label{Eaim}
\Pr(X\hbox{ is usable}, \B_4^c \mid \event)=o(n^{-m})
\end{equation}
separately for each $\event$.
Note that as
$$\{\RA=A\}=\{A\ss G_p\}\cap\bigcap_{j*