%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% LaTeX2e file for 
%
% `` Length of Random Subsets of  Boolean Lattices''
%  
% 
% by  Y. Kohayakawa,  B. Kreuter, and D. Osthus
%
%
%
% last update : 7. September 1998
% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%\NeedsTeXFormat{LaTeX2e}
\documentclass[11pt]{article}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{latexsym}
\usepackage{a4}
%\usepackage{parskip}
\usepackage{amssymb}
\usepackage{amsmath}
%\outer\def\endproof{{\unskip\nobreak\hfil\penalty50
%         \hskip2em\hbox{}\nobreak\hfil$\Box$
%         \parfillskip0pt\finalhyphendemerits=0\par}% TeXbook, p 106.
%    {\ifdim\lastskip<\bigskipamount\removelastskip\penalty-10\bigskip\fi}} 

% Definition of the cases command from Plain TeX.
\catcode`@=11 % borrow the private macros of PLAIN (with care)
\def\cases#1{\left\{\,\vcenter{\normalbaselines\m@th
    \ialign{$##\hfil$&\quad##\hfil\crcr#1\crcr}}\right.}
\catcode`@=12 % at signs are no longer letters

% These define the macros \proof and \proofof
\outer\def\proof{%
   \ifdim\lastskip<\medskipamount\removelastskip\penalty1000\medskip\fi
   \noindent{\it Proof.\enspace}\ignorespaces}
\outer\def\proofof#1.{%
   \ifdim\lastskip<\medskipamount\removelastskip\penalty60\medskip\fi
   \noindent{\it Proof of {#1}\/}.\enspace\ignorespaces}

\newtheorem{lem}       {Lemma}
\newtheorem{thm} [lem] {Theorem}
\newtheorem{cor} [lem] {Corollary}
\newtheorem{prp} [lem] {Proposition}


\begin{document}

\setlength{\parindent}{1.2em}
 \newcommand{\abs}{\paragraph{}\hspace*{0.2em}}

\newcommand{\as}{\emph{a.s. }}
\newcommand{\cQ}{{\cal Q}}\newcommand{\cA}{{\cal A}}
\newcommand{\cB}{{\cal B}}\newcommand{\cC}{{\cal C}}
\newcommand{\cD}{{\cal D}}
\newcommand{\cBu}{{\cal B}^{\rm u}}
\newcommand{\cBd}{{\cal B}^{\rm d}}
\newcommand{\cCu}{{\cal C}^{\rm u}}
\newcommand{\cCd}{{\cal C}^{\rm d}}
\newcommand{\cP}{{\cal P}}
\newcommand{\cS}{{\cal S}}
\newcommand{\cO}{{\cal O}}
\newcommand{\cT}{{\cal T}}
\newcommand{\cPn}{\mathcal{P} (n)}

\newcommand{\Dil}{\Delta_{il}}
\newcommand{\dil}{\delta_{il}}

\newcommand{\eps}{\varepsilon}
\newcommand{\ex}{\mathbb{E}}

\newcommand{\nlim}{\lim_{n \to \infty}}

\newcommand{\pnp}{\cP(n,p)}
\newcommand{\pr}{\mathbb{P}}

\newcommand{\rc}{\lceil r \rceil}
\newcommand{\rf}{\lfloor r \rfloor}

\def\length{\mathop{\rm length}\nolimits}
\def\Bin{\mathop{\rm Bin}\nolimits}
\def\Var{\mathop{\rm Var}\nolimits}

\outer\def\endproof{{\unskip\nobreak\hfil\penalty50
         \hskip2em\hbox{}\nobreak\hfil$\Box$
         \parfillskip0pt\finalhyphendemerits=0\par}% TeXbook, p 106.
    {\ifdim\lastskip<\bigskipamount\removelastskip\penalty-10\bigskip\fi}}



\title{The Length of Random Subsets of Boolean Lattices%
  \footnote{Research supported by PROBRAL project number~026/95, a
    CAPES--DAAD exchange programme.}}
\author{%\sc 
    Y.~Kohayakawa,\thanks{Partially supported by FAPESP
    (Proc.~96/04505--2), by CNPq (Proc.~300334/93--1), and by MCT/ FINEP
    (PRONEX project~107/97).}\\\small
    Instituto de Matem\'atica e Estat\'{\i}stica, 
    Universidade de S\~ao Paulo\\\small  
    Rua do Mat\~ao 1010, 05508--900~S\~ao Paulo, 
    Brazil\\\small
    {\it E-mail address\/}: {\tt yoshi@ime.usp.br}
\and 
    B.~Kreuter, and  D.~Osthus\thanks{Graduate school 
    ``Algorithmische Diskrete Mathematik'', 
    supported by Deutsche Forschungsgemeinschaft grant GRK/3-98}
    {}\\\small 
    Institut f\"ur Informatik, 
    Humboldt-Universit\"at zu Berlin\\\small 
    Unter den Linden 6, 
    10099 Berlin, 
    Germany\\\small 
    {\it E-mail address\/}:  {\tt kreuter@informatik.hu-berlin.de} \\\small
    {\tt osthus@informatik.hu-berlin.de} 
    }
    \date{}
\maketitle
\vspace{-.8cm}
\begin{abstract}
We form the random poset $\pnp$ by including each subset 
  of~$[n]=\{1,\dots,n\}$ with probability $p$ and ordering the subsets by 
  inclusion. 
   We investigate the length of the longest
  chain contained in~$\pnp$.  For $p \geq e/n$ we obtain the limit
  distribution of this random variable. For smaller $p$ we give 
  thresholds for the existence of chains which imply that almost 
  surely the length of $\pnp$ is 
  $(1\!+\!o(1)) \, n(\log n-\log\log 1/p)/\log 1/p$.
\end{abstract}





\section{Introduction and basic definitions}
We investigate random subsets of the power set $\cPn$ of $[n]=\{1,\dots,n\}$.
Such a random subset, denoted $\pnp$, is obtained by selecting each element 
of $\cPn$ with probability $p$ independently of all other elements.
If we order the elements of $\cPn$ by inclusion, we obtain a Boolean
lattice. If we order the elements of $\pnp$ by inclusion, we 
obtain a partially ordered set (or simply \emph{poset}) which is a 
subposet of the above Boolean lattice. 

We focus on the cardinality of the maximum chain contained in $\pnp$. 
Here a \emph{chain} is a subset of $\cPn$ whose elements are pairwise 
comparable and the \emph{length} of a chain is its cardinality minus one.
The \emph{length} of $\pnp$,
for which we write $\length \pnp$, is defined to be the length of 
the maximum chain contained in $\pnp$.  
R\'enyi
was the first to investigate the behaviour of this random variable:
in~\cite{re} he determined the threshold for the existence of
a chain of length one in $\pnp$. Recently, Kreuter~\cite{kr} obtained (amongst 
other results) thresholds for the appearance of chains of any fixed length.
Thus in this paper we confine our attention to the evolution of the length of 
$\pnp$ 
when we increase $p$ beyond the ranges investigated in the above references.
Another important parameter of $\pnp$ is the 
cardinality of its maximum antichain, also called the \emph{width}. 
This is studied in~\cite{kkr} and~\cite{ost}. We remark that the results  
proven in~\cite{ost}
make use of the central lemma of this paper, Lemma~\ref{lem:delta}. 
Indeed, the investigation of antichains in~$\pnp$ for certain values of~$p$
seems to depend essentially on this technical lemma on chains.

Brightwell~\cite{br} gives an overview of some other models of random 
posets. For example, several authors (see e.g.~\cite{bb}) have studied
the length of the random poset generated by picking $n$ random points 
in the $k$-dimensional unit cube. However this model, although similar to 
ours, requires quite different proof techniques.
Our methods are more related to those used in the past to investigate
the diameter and other parameters of random subgraphs 
of the $n$-dimensional hypercube 
(see e.g. Bollob\'{a}s, Kohayakawa and {\L}uczak~\cite{bkl1,bkl2}).
Also, in~\cite{fp} Fill and Pemantle prove the analogue of 
Theorem~\ref{thm:long} in the context
of edge percolation on the hypercube.

Throughout, we refer to the subset 
$\cP_t(n) \subset \cPn$ whose elements have cardinality $t$ as the 
$t$th \emph{level} of $\cPn$. 
The levels of $\pnp$ are defined in the same way.
The (Hamming) distance 
$d_H (x,y)$ of $x$, $y \in \cPn$ is given by
$|(x \setminus y) \cup (y \setminus x)|$.
We write \emph{a.s.} to mean ``with probability tending to one as $n$
tends to infinity''.  

This paper is organised as follows.  In the next section, we state our main
results, Theorems~\ref{thm:short} and~\ref{thm:long}.  Our main technical tool
is given in Section~\ref{sec:regular}, where we state and prove
Lemma~\ref{lem:delta}.  Theorems~\ref{thm:short} and~\ref{thm:long} are proved
in Sections~\ref{sec:thm_short} and~\ref{sec:thm_long}.  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Results}

Kreuter~\cite{kr} proved that the length of $\pnp$ is constant
when $p$ decreases exponentially. The following theorem tells us about
the length of $\pnp$ when $p$ is superexponential:
\begin{thm} \label{thm:short}
Let $k=k(n) \le n \! - \! 1$ be an integer valued function tending to infinity.
%and let $r=(n-1)(k+1)$
Then
\begin{equation} \label{eq:short}
\nlim \pr (\, {\length\pnp \!\geq\! k \!-\!1} \, ) = 
       \left\{ \begin{array}{r@{\quad}l}
            0 & \mbox{if} \ \,  p \, (k \! + \! 1)^{n/k}    \to 0\\
            1 & \mbox{if} \ \, p \, (k \! + \! 1)^{n/k}(k/n)^2  \to \infty.
               \end{array} \right. 
\end{equation}
\end{thm}

At the end of Section~\ref{sec:regular} we indicate how one may remove 
the factor $(k/n)^2$ at the expense of more extensive calculations. 
An immediate corollary of the above theorem is that when
$p$ decreases polynomially in $n$, the degree of the polynomial turns  out 
to be the average distance beween two elements of a typical maximum chain:
\begin{cor} \label{cor:medium}
Let $r \ge 1$ be a fixed constant. Then
\begin{equation} \label{eq:medium}
\nlim \pr \left(\, {\length \pnp \!\geq\! \frac{n}{r}   -\! 2} \, \right) = 
       \left\{ \begin{array}{r@{\quad}l}
            0 & \mbox{if} \ \, pn^r \to 0\\
            1 & \mbox{if} \ \, pn^r \to \infty.
               \end{array} \right. 
\end{equation}
\end{cor}
We remark that the above threshold could be sharpened slightly by the use of 
branching processes and indicate how this may be done at the end of 
the final section.
Another immediate corollary of Theorem~\ref{thm:short} is the following 
asymptotic formula for the length of $\pnp$:
\begin{cor} \label{cor:smallp}
If $c^n=o(p)$ for any $0<c<1$ and $p=\cO(n^{-1})$, then \as
\begin{equation}
  \length \pnp=\left(1+o(1)\right) \frac{n}{\log{1/p}}
  \left(\log{n}-\log{\log{1/p}}\right).
\end{equation}
\end{cor}
%\emph{Proof.} Fix any $\eps >0$. Then if $p=k^{-(1+\eps)n/k}$, 
%(\ref{eq:medium}) and (\ref{eq:short}) imply that \as $\length \pnp \le k-1$.
%Similarly, if $p=k^{-(1-\eps)n/k}$, then \as $\length \pnp \ge k-1$.
%\endproof

Our second theorem (which improves Corollary~\ref{cor:medium} for the 
special case when $r=1$) gives a detailed picture of the final stage 
of the evolution of the length of $\pnp$:
\begin{thm} \label{thm:long}
Let $c \geq e$ be a given constant. Define $p(n)=c/n$. Let $\eta=\eta(c)$  
satisfy $\eta=e^{c(\eta-1)}$ and $0 < \eta < 1$.  Then
\begin{align*}
\nlim & \pr (\, {\length \pnp \!=\! n\!-\!2} \, )={(1-\eta )^2},  \\
\nlim & \pr (\, {\length \pnp \!=\! n\!-\!3} \, )={2 \eta (1-\eta )}, \\
\nlim & \pr (\, {\length \pnp \!=\! n\!-\!4} \, )={\eta ^2}. 
\end{align*}
\end{thm}
We remark that $\eta$ is the extinction probability of a branching process 
whose family size has Poisson distribution with parameter $c$.
Also note that since the top and bottom levels of $\cPn$ contain 
only a single element,
\as we have that $\length \pnp < n-1$ as long as $p \to 0$.
Finally, the following proposition shows that the previous theorem is 
essentially best possible in the sense that if $c < e$, then $\pnp$
becomes significantly shorter.  Indeed, if~$p=p(n)=c/n$, 
Theorem~\ref{thm:short} and Proposition~\ref{prp:smallc} imply that, very
crudely, we have 
\begin{equation}
  \label{eq:gap}
  n-\length\pnp\quad\cases{\quad O(1)        &if~$c\geq e$\cr
                           \quad \to\infty   &if~$c<e$\cr
                          }
\end{equation}
almost surely.  We believe that the fact that the techniques in this paper are
enough to identify the sharp change of behaviour given in~(\ref{eq:gap}) is
quite pleasant.

\begin{prp}  \label{prp:smallc}
Let $c<e$ be a given constant. Define $p(n)=c/n$. 
Then \as
\[  \length \pnp\le \left(1- \frac{\log(e/c)}{3 \log n}\right)n.\]
\end{prp}
\proof
Let  $$a = \left\lceil \frac{\log(e/c) }{3 \log n}n \right\rceil.$$
For $\cQ\subset \cP(n)$ denote by $Y(\cQ)$ the number of $(n-a)$-element chains
in $\cQ$.
A chain on $n-a$ elements corresponds to an ordered partition of $[n]$ into 
$n-a$ nonempty sets. To bound the number of those, first choose $n-a$ 
elements, one
for each partition class. There are $(n)_{n-a}= n!/a!$ ways of doing this. 
Then order the remaining $a$ elements and distribute them among the $n-a$
classes, with $(n-a)^a$ possibilities for this second step. 
Hence by Stirling's formula,
\[ Y(\cP(n)) \le n^a n! = \cO( n^{a+1/2} (n/e)^n). \]
Thus the expected value of $Y=Y(\pnp)$ is
\[  \ex(Y) = \cO( n^{a+1/2} (n/e)^n p^{n-a}) 
     =  \cO( n^{2a+1/2} (c/e)^{n-a})  =o(1)
\]
by the definition of $a$.
\endproof


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\section{Regular chains} \label{sec:regular}

The aim of this section is to prove Lemma \ref{lem:delta} 
below. This lemma implies that the number of ``regular'' chains is not too far
from its expected value provided that $p$ is beyond some threshold.
Once we have this result,
Theorem~\ref{thm:short} will follow immediately, while we still have 
to do some additional work for Theorem~\ref{thm:long}.
These ``regular'' chains are defined as follows:
suppose $x$, $y \in \cPn$ are given with $x \subset y$. Given any $r$ and 
$k$, we say $(x_1, \dots, x_k)$ is an $(x,y,r,k)$-\emph{chain} if 
$x \subset x_1 \subset \dots \subset x_k \subset y$ with the additional 
condition that $|x_i|=|x|+\lceil ir \rceil$ for all $i$. 
Since $r$ and $k$ are always related in what follows, 
$(x,y,r,k)$-chains are simply referred to as $(x,y,r)$-chain. 

Throughout this section we assume that $x \in \cP_t(n)$ and 
$y \in \cP_{n-t}(n)$ for some fixed integer $t$. 
Also $k$, the number of elements in a 
chain, is a given integer function of $n$ with $k \le n-2t-1$.
As a measure of the average distance between two chain elements we define
\begin{equation} \label{eq:defr}
r = \left\{ \begin{array}{c@{\quad}l}
         1              & \mbox{if} \ \,  k=n-2t-1  \\
         (n \! - \! 2t \! - \! 1)/(k \! + \! 1) & \mbox{if} \ \, k < n-2t-1 .
             \end{array} \right.
\end{equation}
The extra minus one in the fraction 
is a technical artifice to ensure that 
$\cP_{|x_i|}(n,p)$ is large enough even when  
$r$ is not an integer and $i$ is close to $k$. 
We separate the two cases since we want to achieve
the best possible result when $r=1$. Now, for given $m \in \mathbb{N}$, let
\begin{equation} \label{eq:defh}
h(m) = \left\{ \begin{array}{c@{\quad}l}
         m+1                       & \mbox{if} \ \,  k=n-2t-1  \\
         \lfloor (m+1)r \rfloor +1 & \mbox{if} \ \, k < n-2t-1 .
             \end{array} \right.
\end{equation}
Writing $x_0=x$ and $x_{k+1}=y$, the Hamming distance between chain elements 
$x_j$ and $x_{j'}$ with 
$j'>j$ is then at most $h(j'-j-1)$. We shall often make use of the fact that 
$h(j')-h(j) \le (j'-j)r+1$.
Finally we assume that 
\begin{equation} \label{eq:defp}
p(n)=d \, h(0)! \left( \frac{e}{(n-2t)(k+1)^{1/k}} \right)^{r} 
\end{equation}
with $d=d(n) \ge 1$. 
The following form of Stirling's formula (valid for all $n > 0$) 
will suffice for our purposes:
\begin{equation} \label{eq:stirling}                        
\sqrt{n} \left( \frac{n}{e} \right)^n < n! <
3\sqrt{n} \left( \frac{n}{e} \right)^n.
\end{equation}

Let $\cS$ be a family of subsets  of $\cPn$. In what
follows, $\cS$ will usually consist of various chains in $\cP(n)$.
For $\alpha \in \cS$ let $I_\alpha$ be the indicator
of $\alpha$, i.e., for $\cQ\subseteq \cPn$ we have $I_\alpha(\cQ)=1$
iff $\alpha \subseteq \cQ$. 
Now define 
\begin{equation}
    \label{eq:defXS}
    X_{\cS} = \sum_{\alpha\in \cS} I_\alpha.
\end{equation}
\begin{prp} \label{prp:regexp}
Let $t \in \mathbb{N}$, $x \in \cP _t(n)$ and  
$y \in \cP _{n-t} (n)$ with $x \subset y$ be given. 
Let $\cS=\cS (x,y,r)$ be the set of all $(x,y,r)$-chains in $\cPn$. Then 
$$\lim_{n \to \infty} \ex(X_{\cS}) =\infty.$$
\end{prp}
\proof
Let $R_k$ denote the number of $(x,y,r)$-chains in $\cPn$.
By definition of $k$ and $r$ we have   
$$R_k=
  {n-2t \choose \rc, \lceil 2r \rceil -\rc, \dots, n-2t-\lceil kr \rceil}  
\ge \frac{(n-2t)!}{h(0)!^{k+1}}.$$
But $\ex(X_{\cS}) =R_k \,  p^k $. The result now follows by 
Stirling's formula (checking the cases $r=1$ and $r>1$ separately).
\endproof

For $\alpha\neq\beta\in \cS$ write $\alpha \sim \beta$ if  $\alpha\cap
\beta \neq \emptyset$. Then we define 
\begin{equation}  \label{eq:defDeltaS}
   \Delta(\cS) = \sum_{\alpha\sim\beta}\ex ( I_\alpha I_\beta),
\end{equation} 
where the sum is over all ordered pairs $\alpha$, $\beta \in \cS$ with
$\alpha\sim\beta$.

\begin{lem} \label{lem:delta}
     Let $t \in \mathbb{N}$, 
     $x \in \cP _t(n)$ and  
     $y \in \cP _{n-t} (n)$ with $x \subset y$ be given. 
     Let $\cS=\cS(x,y,r)$ be the set of all $(x,y,r)$-chains in $\cP(n)$.
     Then 
  \[   \Delta(\cS) \le \frac{9}{d} \,  \ex(X_\cS)^2, \]
      provided $n$ is large enough. 
\end{lem}
There are several results on random subgraphs of the hypercube which rely 
on a similar lemma, essentially giving bounds on the number of pairs of 
various kinds of paths in the hypercube. 
In fact, case~(a) of the proof of Lemma~\ref{lem:delta} is similar to Lemma 2.2 
proved by Fill and Pemantle in~\cite{fp}, but is sketched for completeness.
However, in general their bounds do not apply to our model 
(even for the simplest case $r=1$) owing to 
the differences in the geometry of the paths involved.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\proofof Lemma~\ref{lem:delta}.
Consider any ordered pair $(\alpha, \beta)$ of 
$(x,y,r)$-chains with $\alpha \sim \beta$. 
Let $i=i(\alpha,\beta)=|\alpha \cap \beta|$ be the number of 
common elements. Note that $0 < i <k$.

A \emph{disjoint interval} $\gamma$ is a subset of $\alpha \setminus \beta$
with the property that, whenever we have $w$, $w' \in \gamma$, 
$v \in \alpha$, and $w \subset v \subset w'$, we must
have $v \in \gamma$. We then let $l$ be the maximum cardinality 
(or \emph{size}) of a disjoint
 interval and let $s$ be the number of disjoint intervals. 
Note that $0< l \le k-i$ and $0< s \le k-i$. 

Now write $\sum_{i,l,s}$ for the sum over all ordered pairs of 
$(x,y,r)$-chains 
$\alpha$ and $\beta$ with  $i(\alpha,\beta)=i$, $l(\alpha,\beta)=l$, and 
$s(\alpha,\beta)=s$.  Let
$$ \Delta_{ils} = \sum_{i,l,s} \ex (I_{\alpha}I_{\beta})$$
and define $\Delta_{i}$, $\Delta_{il}$ and $\Delta_{is}$ similarly. 
We can then write $\Delta=\Delta(\cS)$ as 
\begin{equation}
  \label{eq:sumDeltails}  
  \Delta = \sum_{i=1}^{k-1} \Delta_{i}, \quad \mbox{ where }  \quad
  \Delta_{i} = \sum_{l=1}^{k-i} \Delta_{il} =\sum_{s=1}^{k-i} \Delta_{is}
  \quad \mbox{ and }  \quad
  \Delta_{is} = \sum_{l=1}^{k-i} \Delta_{ils}.
\end{equation}
Let now $i$, $l$ and $s>0$ with $i+l \leq k$ and  $i+s \leq k$ be given.
Then an {\em admissible $(i,l,s)$-configuration} is a set $A\subset [k]$
with $|A|=i$ such that the longest
interval of consecutive elements in $[k]\backslash A$ contains exactly
$l$ elements and such that the number of intervals of consecutive 
elements is exactly $s$. 
The set of all admissible $(i,l,s)$-configurations,
denoted $\cA_{ils}$,
corresponds to 
the possible intersection patterns of two $(x,y,r)$-chains
(indeed, the configurations give the positions in which two chains 
may intersect).  
Let $C_{ils}=|\cA_{ils}|$.
Let $C_{il}=\sum_s C_{ils}$, $C_{is}=\sum_l C_{ils}$, 
and $C_{i}=\sum_l C_{il}$. Note the trivial bounds
$C_{ils} \le C_{il} \le C_{i} \le {k \choose i}$.      

Now we investigate the number of ways in which a given configuration
can be \emph{extended}. Let $i$, $l$ and $s$ be given and 
let $\alpha=(x_1\subset x_2\subset \dots \subset x_k)$ 
be a fixed $(x,y,r)$-chain and $A \in \cA_{ils}$. 
Let $E(A)$ be the number of possible extensions corresponding
to the intersection pattern given by $A$:
i.e., $E(A)$ is the number of $\beta$ that
are $(x,y,r)$-chains in  $\cPn$ with 
$\alpha\cap \beta = \{x_i \colon i\in A\}$.
Let 
\begin{equation*}
E_{ils}=\max_{A \in \cA_{ils}} E(A).
\end{equation*} 
This time, define $E_{il}=\max_s E_{ils}$ and $E_{is}=\max_l E_{ils}$.
To estimate $E_{ils}$, note that each disjoint interval, between
$x_j$ and $x_{j'}$ with $j'>j$ say, contributes a factor of
$${\lceil j'r \rceil - \lceil jr \rceil \choose 
\lceil (j+1)r \rceil - \lceil jr \rceil,\dots,
\lceil j'r \rceil - \lceil (j'-1)r \rceil}.$$
By the convexity of factorials, $E(A)$ is then maximised if $A$
has as few disjoint intervals as possible and if as many of these 
intervals as possible have maximum size.
Instead of bounding $E_{ils}$ directly, 
it turns out to be more convenient 
to consider $E_{ils}/R_k$, where $R_k$ is defined to be the number of 
$(x,y,r)$-chains in $\cPn$ as in the proof of Proposition~\ref{prp:regexp}.
This has the advantage that some of the factorials involving $\rc$ and
$\rf$ cancel straightaway. The same applies also to $E_{il}$ and 
$E_{is}$: for instance, the above argument and the 
formula for $R_k$ given in the proof of 
Proposition~\ref{prp:regexp} imply that
\begin{equation} \label{eq:boundEil}
\frac{E_{il}}{R_k} \le \frac{h(0)!^i}{(n-2t)!}  
      h(l)! \,  h(k-i-l)!.
\end{equation}
Indeed, note that we must have at least one disjoint interval of size $l$
and that in the worst case, all the remaining disjoint vertices
are contained in a single disjoint interval of size $k-i-l$.
We remark that the above inequality also shows that one may interpret 
$E_{il}/R_k$ as an upper bound on the fraction of all 
$(x,y,1)$-chains whose intersection with a given $(x,y,r)$-chain is
an admissible $(i,l)$-configuration.

For notational convenience let $\delta_{ils} = \Delta_{ils}/\ex(X_{\cS})^2$ 
and define the $\delta_i$ etc similarly. 
Noting that $\ex(X_{\cS})=R_k\,  p^k$, we have 
\begin{equation}
   \label{eq:defsdil}
   \delta_{ils} = \frac{\Delta_{ils}}{\ex(X{_ \cS})^2} \le 
        \frac{R_k \,  p^{2k-i} \,  C_{ils} \,  E_{ils}}{\ex(X_{\cS})^2}
        \le \frac{C_{ils} \,  E_{ils}}{R_k \,  p^{i}}.
\end{equation}           
We will bound the $\delta_{ils}$ by applying different estimates for different
ranges of $i$, $l$ and $s$.
To fix these ranges we need to  define the following constants: 
\begin{equation}
\lambda=1/40 \quad \mbox { and } \quad \rho =1/40e.
\end{equation}
Choose $\kappa  >0$ sufficiently small so that
\begin{equation} \label{eq:defkappa}
    (1-\lambda)(1+ \kappa)^{2} <1.
\end{equation}    
Choose $\sigma >0$ sufficiently small so that
\begin{equation} \label{eq:defsigma}
    (e/\sigma)^{2\sigma} (1-\lambda)^{\rho}(1+\kappa)^{2}<1.
\end{equation}  
Finally choose $l_0 \in \mathbb{N}$ large so that for any $l\ge l_0$, 
\begin{equation} \label{eq:defl0}
    2 \left( \frac{4e}{l} \right)^{\sigma} <1 \quad\mbox{ and }\quad
         h(l)!^{1/(l-1)} \leq \left(\frac{lr(1+\kappa)}{e} \right)^r.
\end{equation}
We assume that $n$ is large enough whenever needed. 
We shall also make use of the following inequality, which 
follows immediately from Stirling's formula~(\ref{eq:stirling}) and the 
definition of $r$ and $p$ in~(\ref{eq:defr}) and~(\ref{eq:defp}):
\begin{equation} \label{eq:stirlingapp}
\frac{h(0)!^i}{p^i \,  (n-2t)!} \le
     \frac{(k+1)^{ir/k}}{d\sqrt{kr}} 
     \,  \left( \frac{e}{(k+1)r} \right)^{h(k-i)}.
\end{equation}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\medskip\noindent
(a) $i < \lambda k$ 

\medskip\noindent
It turns out that the only significant contribution of $\Delta_{ils}$
to $\Delta$ comes from the case when $i$ is small and $l=k-i$
(which implies that $s=1$): 
in the case (a1), when $l$ is small, we have only a trivial bound on the 
number of configurations but this is compensated by the fact that, in this 
case, the number of extensions is severely limited.
In the case (a2), when $l$ is large, the situation is reversed.
Overall this allows us to show that $\delta_i$ is a constant multiple 
of the worst case contribution $\delta_{i,k-i}$.

\medskip\noindent
(a1) $l \le k-4i$ 

\medskip\noindent
We have $\sum_{l=1}^{k-4i} C_{il} \leq C_i \le {k \choose i}$ and 
by~(\ref{eq:boundEil})
$$\frac{E_{il}}{R_k} \leq 
      \frac{h(0)!^i}{(n-2t)!} \, 
      h(k-4i)! \,  h(3i)!.$$
\noindent
Thus, using $h(0) \ge 1$ and $\lambda=1/40$, we have 
\begin{align*}
\sum_{l \leq k-4i} C_{il} \frac{E_{il}}{R_k}
  &  \le\frac{h(0)!^i}{(n-2t)!} \,  h(k-i)! \, 
    \frac{h(k-4i)!}{h(k-i)!} \, h(3i)! \, 
    {k \choose i} \\
  & \le \frac{h(0)!^i}{(n-2t)!} \, h(k-i)! \,      
    \left( \frac{(4ir)^3}{((k-4i)r)^3}\, \frac{ek}{i} \right)^
                         {\lfloor ir \rfloor}    \\
  & \le \frac{h(0)!^i}{(n-2t)!} \,  h(k-i)! \,      
    \left( \frac{64e\lambda^2}{(1-4\lambda)^3} \right)^{\lfloor ir \rfloor} \\
  & \le \frac{h(0)!^i}{(n-2t)!} \,  h(k-i)! \,  \frac{1}{4}. 
\end{align*}

\medskip\noindent
(a2) $l > k-4i$ 

\medskip\noindent
As there are $k-l+1$ choices for picking the position of the lowest 
disjoint interval of length $l$ and at most ${k-l-1 \choose i-1}$ 
choices for picking the remaining elements we have
\begin{equation}
  \label{eq:boundCil}
  C_{il} \le (k-l+1){k-l-1 \choose i-1}. 
\end{equation}  
Define $M_{il}$ to be the product of the right-hand sides of 
inequalities~(\ref{eq:boundCil}) and~(\ref{eq:boundEil}). Thus 
$C_{il} \,  E_{il}/R_k \leq M_{il}$. Furthermore, since $r \ge 1$,
\begin{align*}
\frac{M_{i,l+1}}{M_{i,l}} 
 & \geq \frac{k-l}{k-l+1} \,  \frac{k-i-l}{k-l-1} \, 
     \left( \frac{(l+1)r}{(k-i-l+2)r} \right)^r \\
 & \geq \frac{k-i-l}{k-i-l+2} \frac{k-4i}{4i}  
     \geq \frac{1}{3} \, \frac{1-4\lambda}{4\lambda} = \frac{7}{3}.
\end{align*}
Since $\sum_{j=0}^{\infty} (3/7)^{j} =7/4$,  the total contribution 
of the $M_{il}$ for $l > k-4i$ is at most  
$7/4$ times that of the maximum term $l=k-i$.

Putting both (a1) and (a2) together gives 
\begin{align}
\delta_i 
    & \le \sum_{l=1}^{k-i} \dil 
      \le 2  \,  \frac{M_{i,k-i}}{p^i} 
      \le 2 \, (i+1) \,  \frac{h(k-i)!}{(n-2t)!} \,  p^{-i} \nonumber \\
    &  \le \, 2 (i+1) \left( \frac{1}{2d} \right)^i, 
\end{align}
since $r \ge 1$ and, very crudely, 
$h(k-i) \ge (1-\lambda)(n-2t) \ge p^{-1/r}$.
Thus, using this time that $d \ge 1$, 
$$ \sum_{1 \le i \le \lambda k} \delta_i  
       \le 2  \left( \left( 1-\frac{1}{2d} \right)^{-2} -1 \right) 
       \le \frac{8}{d}.$$
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%          
\medskip\noindent
(b) $\lambda k \leq i < (1-\rho)k$ 

\smallskip\noindent
(b1) $l<l_0$ 

\medskip\noindent
We have $C_{il} \leq {k \choose i} \le 2^k$. To estimate $E_{il}/R_k$, note
that chain elements in the intersection which lie at either 
end of a disjoint stretch have distance at most $h(l)$.
Thus for each disjoint interval (of size $\bar{l}$ say) we have 
a contribution of a factor of 
$h(\bar{l})! \le h(0)! \,  (2h(l))^{\bar{l}r}$.
Using the fact that there are $k-i$ disjoint vertices and 
at most $i+1$ disjoint intervals yields the following bound:
$$\frac{E_{il}}{R_k} \leq 
      \frac{h(0)!^i}{(n-2t)!} \,  
          (2h(l))^{(k-i+1)r}.$$
Hence, by inequality~(\ref{eq:stirlingapp}), and noting (crudely) that 
$(k+1)^{ir/k} \le (k+1)^r < e^{\rho kr}$, we have
\begin{align*}
\delta_{il} 
&  \le \frac{h(0)!^i}{p^i (n-2t)!} \, 
       (2h(l))^{(k-i+1)r}  \,  2^k\\
& \leq \frac{e^{\rho kr}}{d}
      \left( \frac{e}{(k+1)r} \right)^{(k-i+1)r} \
       (2(l_0 \! +\! 1)r)^{(k-i+1)r} \, 2^k\\
& \leq \frac{1}{d} \, 
       \left( \frac{2^{1+1/\rho} (l_0 \! +\! 1) e^2}{k} \right)^{\rho kr}  \\
& \leq \frac{1}{dk^3}.
\end{align*}    
In the last line we used the fact that $k \to \infty$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\medskip\noindent
(b2) $l>l_0$

\medskip\noindent
Fix a chain  $\alpha$ and any configuration with parameters $i$, $l$, and 
$s$. Denote
the size of the disjoint intervals by $l_j$, for $1 \leq j \leq s$. Then  
there are at most $h(0)^{i-(s-1)} \prod_{j=1}^{s} h(l_j)!$ 
$(x,y,1)$-chains which meet $\alpha$ exactly at 
the $i$ chosen points. But this product is maximised if we have as many 
disjoint intervals of size $l$ as possible, say $q$ of them.
The remaining disjoint vertices will be distributed among  one interval 
of size $\bar{l}$, with $1 \le \bar{l} <l$, 
and $s-q-1$ unit size intervals.
Then noting that  $ql+\bar{l}+(s-q-1) =k-i$ and $s-q-1 < s$ gives  
$$\frac{E_{ils}}{R_k} 
 \le  \frac{h(0)!^{i-(s-1)}}{(n-2t)!} \, 
     h(l)!^{\frac{k-i-s-\bar{l}}{l-1}} \, h(\bar{l})! \, h(1)!^s
 \, \le \,  \frac{h(0)!^i}{(n-2t)!} \, 
     h(l)!^{\frac{k-i-s}{l-1}}  \, (4r)^{sr}.$$
Now use $l \le k-i <(1-\lambda)k$ and the definition of 
$l$ in (\ref{eq:defl0}) to obtain
\begin{align*}
  \frac{E_{ils}}{R_k} 
   & \le h(0)!^i \,  \left( \frac{e}{n-2t} \right) ^{n-2t} \, 
     \left( \frac{lr(1+\kappa)}{e} \right)^{(k-i)r}
     \,  \left( \frac{4er}{(l+1)r} \right) ^{sr} \\
   & \le h(0)!^i \, 
     \left( \frac{e}{n-2t} \right) ^{ir}
     \,  \left((1-\lambda)(1+\kappa) \right)^{(k-i)r}
     \,  \left( \frac{4e}{l} \right) ^s. 
\end{align*}  
By the definition of $p$ in~(\ref{eq:defp}), and again crudely estimating 
$(k+1)^{ir/k} \le (k+1)^r \le (1+\kappa)^{\rho kr}$, we have
\begin{equation*}
  \delta_{il}  \le \frac{1}{d} \, 
    \sum_{s=1}^{k} C_{ils} 
          \left( (1-\lambda)(1+\kappa)^{2} \right) ^{\rho kr} 
    \,  \left( \frac{4e}{l} \right) ^s.
\end{equation*}
When bounding $C_{ils}$ we distinguish two cases.
First suppose that $s \leq \sigma k$. 
Note that any admissible configuration may be defined 
in the following way: we first fix the lowest point of each of the $s$ 
disjoint intervals. ${k \choose s}$ is a crude bound on the number of 
choices. This first step fixes the positions of at least $s-1$ 
common vertices, since unless a disjoint interval is right at the top,
it must obviously be below a common vertex. 
We now fix a configuration uniquely by successively adding a further $i-s$ 
common vertices on top of the existing common intervals. In other words,   
we are now drawing $i-s+1$ elements (with replacement) from a set of $s$  
distinct elements, giving us ${s+(i-s+1)-1 \choose i-s+1} = {i \choose s-1}$
choices on the second step. Thus
$$C_{ils} \leq {k \choose s} \,  {i \choose s-1}
          \le \left( \frac{ek}{s}\right)^{s} 
            \,  \left( \frac{ei}{s-1}\right)^{s-1}
          \le \left( \frac{ek}{s}\right)^{2s} 
          \leq \left(\frac{e}{\sigma}\right)^{2 \sigma k}.$$
For $s>\sigma k$ we just use the trivial bound $C_{ils}\le 2^k$. 
Plugging in and using  (\ref{eq:defsigma}) and
  (\ref{eq:defl0}) this yields
\begin{align}  
   \nonumber
  \delta_{il} & \leq  \frac{1}{d} \left( \sum_{1 \le s \le \sigma k} 
         \left(\frac{e}{\sigma}\right)^{2 \sigma k}
          ((1-\lambda)(1+\kappa)^{2})^{\rho kr} 
        + \sum_{\sigma k <s \le k} 2^k  \left(\frac{4e}{l}\right)^s \right)\\
   \nonumber
        & \leq  \frac{1}{d} \left(k^{-4}+
        k 2^k  \left(\frac{4e}{l_0}\right)^{\sigma k} \right) \\
        & \leq \frac{1}{dk^3}.
      \label{eq:sdilc}    
\end{align}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\medskip\noindent
(c) $i \geq (1-\rho)k$

\medskip\noindent
There are at most ${i+s \choose  s}$ ways of choosing the relative order  
of $i$ common vertices and the $s$ disjoint intervals. We now
fix the size of the intervals, by distributing the $k-i-s$ remaining
``disjoint'' vertices among the $s$ disjoint intervals.
We are choosing these elements (with replacement) from $s$ ``urns'',
giving at most ${k-i-1 \choose k-i-s }$ possibilities for this step. 
Hence, by applying Stirling's inequality and then that 
$i+s \le k$ and $m^{-m} \le 3(m+1)^{-m}$ for all $m \ge 0$,
\begin{align}
C_{is} & \leq {i+s \choose  s} {k-i-1 \choose k-i-s }  \nonumber\\
  & \le \left( \frac{e(i+s)}{s} \right)^s \,  
    \left( \frac{k-i}{e} \right)^{k-i} \, 
    \left( \frac{k-i-s}{e} \right)^{s-(k-i)} \, 
    \left( \frac{e}{s-1} \right)^{(s-1)}   \nonumber\\
  & \le 3^{16} \left( \frac{ek}{s^2} \right)^s \, 
    (k-i)^{k-i+1} \,  (k-i-s+15)^{s-(k-i)}.  \label{eq:ccis}
\end{align}
Similarly to case (b2), but without the constraint on the size of the 
longest disjoint interval, the extremal configuration for given $s$ is 
now attained if we have
$s-1$ disoint intervals of unit size and one interval containing all the other 
disjoint vertices. Thus 
\begin{align*} 
\frac{E_{is}}{R_k} 
 & \le \frac{h(0)!^{i-(s-1)}}{(n-2t)!}  \, h(k-i-s+1)! \, h(1)!^{s-1}  \\
 & \le \frac{3 h(0)!^i}{(n-2t)!} 
\left( \frac{(k \! - \! i - \! s \! +\! 15)r}{e} \right)^{\! h(k-i-s+1)+1/2} 
   (4r)^{(s-1)r}.
\end{align*}
The second line follows by Stirling's formula~(\ref{eq:stirling}). 
By the definition of $h$, the fact that 
$(k\! -\! i-\! s\! +\! 15) \le 3^3 (k-i)$,
and inequality~(\ref{eq:stirlingapp}), we now have 
\begin{align}
\frac{E_{is}}{R_k \,  p^i} 
   & \le \frac{3^4}{d} \frac{(k \! -\! i)^{3/2}}{\sqrt{k}} 
   (k \! + \! 1)^r\times\\
   &\qquad\qquad\quad\times
   \left( \frac{e}{(k \!+ \!1)r}\! \right)^{\! h(k-i)}  \! \!
   \left( \frac{(k\! -\! i-\! s\! +\! 15)r}{e}\! \right)^{\! h(k-i)-(s-1)r} 
   \! \!  (5r)^{(s-1)r} \nonumber \\
  & \le \frac{3^7}{d} \frac{(k \! -\! i)^{3/2}}{\sqrt{k}}
    \left( \frac{k-i-s+15}{(k+1)^{1-1/(k-i+1)}} \right)^{h(k-i)}
    \left( \frac{5e}{k-i-s+15} \right)^{(s-1)r} \nonumber\\
 & \le \frac{3^{10}}{d\sqrt{k}}  (k \! -\! i)^{5/2}\, 
     \left( \frac{k-i-s+15}{k} \right)^{k-i} \, 
     \left( \frac{5e}{k-i-s+15} \right)^{s-1}. \label{eq:ceis}
\end{align}
The last line follows since one may check that both of the bracketed terms 
in the second line are smaller than one.
Combining inequalities (\ref{eq:ccis}) and  (\ref{eq:ceis}), we have
$$\delta_{is} \le \frac{3^{30}}{d\sqrt{k}} \,  (k-i)^{4} \, 
                   \left( \frac{3e^2 k}{s^2} \right)^s \, 
                   \left( \frac{k-i}{k} \right)^{k-i}.$$               
It is easily verified that for fixed $k$ and $i$, the expression 
$\left( 3e^2 k/s^2 \right)^s$ is
maximised at $s=\sqrt{3k}$ if $i \le k-\sqrt{3k}$ and is maximised at 
$s=k-i$ if $i \ge k-\sqrt{3k}$. 
Thus if $i \le k-\sqrt{3k}$, we have
$$\delta_{is} \le  \frac{3^{30}}{d\sqrt{k}}
          (k-i)^{4} e^{2\sqrt{3k}} \rho^{k-i} 
           \le  \frac{3^{30}}{d\sqrt{k}} k^{4} (\rho e)^{2\sqrt{3k}},$$
and if $i \ge k-\sqrt{2k}$, we have
$$\delta_{is} \le  \frac{3^{30} 1}{d\sqrt{k}}
       (k-i)^{4}  \left( \frac{3e^2}{k-i} \right)^{k-i}.$$
Putting both the above together, and noting that $s \le k-i \le k$,
\begin{align*}
 \sum_{(1-\rho)k \le i < k} \delta_{i} &
%  = \sum_{(1-\rho)k \le i <k} \sum_{s=1}^{k-i} \delta_{is} \\
   \le \frac{3^{30}}{d\sqrt{k}}
    \! \left( \sum_{(1-\rho)k \le i \le k-\sqrt{3k}} 
       \!\!\!\!\! k^5 (\rho e)^{2\sqrt{3k}} 
    +  \!\!\!\!\sum_{k-\sqrt{3k} \le i < k} 
     \!\!\!\! (k \!- \! i)^5 \left( \frac{3e^2}{k\! -\! i} 
                                              \right)^{k-i} \right) \\
  & \le \frac{3^{30}}{d\sqrt{k}} 
     \left( k^6 ( \rho e^2 )^{\sqrt{3k}} 
             +K \right) \\
  & \le \frac{1}{d k^{1/4}},
\end{align*}
where $K$ is some fixed constant.

Summing up the bounds in (a), (b) and (c) gives the desired result:
$$\frac{\Delta}{\ex(X_{\cS})^2} 
   \le \frac{8}{d} + k^2 \,  \frac{1}{d k^3} + \frac{1}{d k^{1/4}} 
   \le \frac{9}{d}.$$
\newline    
\endproof
We remark that the above result is best possible up to a constant factor. 
This may be seen by noting that the contribution 
to $\Delta/\ex(X_{\cS})^2$ of those pairs of chains
which have only the bottom element in common is asymptotically equal to 
$1/ed$. 

In the previous section, we mentioned that the threshold in 
Theorem~\ref{thm:short} could be tightened by a factor of $(n/k)^2$: 
this can be done by considering not just $(x,y,r)$-chains (where the 
level of the $i$th element $x_i$ is fixed at 
$|x_i|=|x|+\lceil ir \rceil$), but allowing the level of $x_i$ to deviate 
from this by a factor of $\sqrt{r}$. The calculations are then more 
cumbersome, but the techniques of this section still apply.

Finally, we state a slight variant of the previous lemma, which will be 
needed in~\cite{ost}, the difference being that the regular chains under
consideration are now ``squeezed'':
let $k$ be given as before and let $m=m(n)$ and $m'=m'(n)$
be given integer functions which are $o(n)$. 
In the definitions of $r$, $h$, and $p$ in~(\ref{eq:defr}),~(\ref{eq:defh}),
 and~(\ref{eq:defp}) respectively, replace the term $2t$ by 
$m+m'$.
Then we say that $(x_1 \subset \dots \subset x_k)$
is an $[m,m',r]$-chain if $|x_i|=m+\lceil ir \rceil$ for all $i$. 
\begin{lem} \label{lem:delta2}
     Let $\cS$ be the set of all $[m,m',r]$-chains in $\cP(n)$.
     Then for large enough $n$, and $p$ as in~{\rm (\ref{eq:defp})}, we have 
     \[   \Delta(\cS) \le \frac{9}{d} \,  \ex(X_\cS)^2. \]
\end{lem}
The proof of Lemma~\ref{lem:delta} goes through as before: 
we may first of all assume without loss of generality that $m \ge m'$; 
it turns out that the only difference arises 
when bounding the number of extensions: in the extremal configuration
 the longest disjoint interval is now 
situated at the top, which contributes a factor of at most 
$(h(l)+m)_{m}$ to the numerator of the $E_{ils}/R_k$. Similarly, the second 
largest interval contributes a factor of at most $(h(l)+m')_{m'}$.
This is compensated by the additional $(n)_{m+m'}$ in the denominator.
In fact the only reason for stating Lemma~\ref{lem:delta2} separately
was to avoid additional notation in the previous lemma and its proof.

We further remark that the above bound on $\Delta(\cS)$ is only required 
in~\cite{ost}. 
For the purposes of this paper, it would have been slightly 
more convenient to bound $\ex(X_{\cS}^2)$ directly instead of $\Delta(\cS)$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Proof of Theorem \ref{thm:short}}\label{sec:thm_short}

The technically difficult part in the proof of Theorem~\ref{thm:short} has
been dealt with in Lemma~\ref{lem:delta}, and hence this theorem may now be
proved easily.

\proofof Theorem \ref{thm:short}.
 For the first part assume that $p \, (k \! + \! 1)^{n/k} \to 0$. 
 Let $Y_k$ then be the number of $k$-element chains
 in $\pnp$. The number of $k$-element chains in $\cPn$ is at most 
 $(k \! + \! 1)^n$.  
 To see this, note that we may associate with each $k$-element chain 
 $\alpha$ a   
 $(k \! + \! 1)$-colouring of $\{1,\dots,n\}$ as follows: 
 Suppose $\alpha=(x_1 \subset x_2 \dots \subset x_{k})$. 
 Assign colour $1$ to all 
 elements in $x_1$, colour $j$ to all elements in $x_j\setminus x_{j-1}$
  for $1 < j \leq k$ and colour $k \! + \! 1$ to $[n] \! \setminus \!  x_{k}$. 
Hence 
$$\pr (Y_k >0) \leq \ex(Y_k) \leq (k \! + \! 1)^n \,  p^k =o(1),$$
which implies the first statement.

To prove the second statement, suppose 
$p \, (k \! + \! 1)^{n/k} (k/n)^2 \to \infty$.
Let $r$ be given by~(\ref{eq:defr}). 
It is easily checked that this implies that $p$ satisfies~(\ref{eq:defp}) 
with $d=d(n) \to \infty$.  
Now let  $\cS$ be the set of $(\emptyset,[n],r)$-chains, so that $X_{\cS}$
is the number of $(\emptyset,[n],r)$-chains in $\pnp$.
Since $\Var (X_{\cS}) \leq \Delta(\cS) +\ex(X_{\cS})$ (see e.g. \cite{aes}), 
the desired result
follows immediately from Chebyshev's inequality after applying
Proposition~\ref{prp:regexp} and  Lemma~\ref{lem:delta} with $t=0$. 
\endproof


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\section{Proof of Theorem \ref{thm:long}}\label{sec:thm_long}
We shall use some results on branching processes in the proof 
of Theorem~\ref{thm:long} in order to ``amplify''
the results of the previous section. 
This is a natural approach also exploited in~\cite{fp}.
We first present 
a few basic concepts and some notation. 

Let $X$ be a nonnegative integer
valued random variable. A \emph{Galton-Watson branching process} with 
family size $X$ is a discrete Markov chain $(X_t)_{t=0}^{\infty}$ with  
the following properties: at time $t=0$ we have one ``ancestor'', so we set 
$X_0 =1$. For $t \geq 1$ define $X_t$ to be the sum of $X_{t-1}$ 
independent random variables, each having the same distribution as $X$
%Thus the number of 
%children of each member of the $t$th generation is distributed as  $X$
(see e.g.~\cite{har} for details).
As we shall only be concerned with the case when $X$ has Poisson distribution 
with parameter $c$, in what follows $(X_t)_{t=0}^{\infty}$ will always  
refer to a branching 
process with this property. Let $\eta$ be the \emph{extinction probability}
 of this process:
\begin{equation} \label{eq:defeta}
\eta=\eta(c) = \pr (X_t=0 \textrm{ for some } t).
\end{equation}
A simple result in branching process theory says 
that if $c>1$ then $\eta$ is the (unique) root of $s=\ex (s^X)=e^{c(s-1)}$ 
in $0<s<1$.
Another basic result (see~\cite{har} again) is that for any 
constant $k>0$, we have 
\begin{equation} \label{eq:harris}
{\lim _{t \to \infty} \pr (X_t =k)}=0.
\end{equation}
We now define branching processes in $\cPn$. Consider any $x \in \cPn$
at level $m$, say. An \emph{upward} $x$-process 
$(Z_t^n)_{t=0}^{n-m}= (Z_t^n(x))_{t=0}^{n-m}$ is 
defined by letting $Z_t^n$ denote the number of $z\in P_{m+t}(n,p)$
that are connected to $x$ via an $(x,z,1)$-chain in $\pnp$.  
A downward $y$-process is defined similarly.
For simplicity, we will henceforth call an $(x,y,1)$-chain an $xy$-chain.

The following proposition will help us determine the number of 
descendants we need at each end in order to link the ``top'' and ``bottom'' 
of $\pnp$:
\begin{prp}
\label{prp:defab}
For any given $c \ge e$ define $\eta=\eta(c)$ as in {\rm (\ref{eq:defeta})}.  
Given $0 \! <\eps \! <1 \! -\! \eta$,
 there exists $a =a(c,\eps )\in \mathbb{N}$ with 
 $(43/44)^a \le \eps$ satisfying the following:
  for a random variable 
 $Z \sim \Bin( \left\lceil 2a/(1-\eta-\eps) \right\rceil,1-\eta-\eps)$, 
 we have ${\pr (Z<a)}<\eps$.
\end{prp}
\proof
Certainly $\pr (Z>a) \le \pr (|Z-\ex(Z)| \ge a)$.
Thus the result follows from Chernoff's bound. \endproof
For positive integers $m$ and $n$ with $n>2m$, 
denote by $\cP_{m\dots n-m}(n,p)$ the family of all sets from $\pnp$ 
of cardinality
at least $m$ and at most $n-m$. 
Let  $X \subseteq \cP_{m}(n)$  and $Y \subseteq \cP_{n-m}(n)$ be given. 
We say that $X$ and $Y$ {\em can be linked} 
%(in $\cP_{m+1\dots n-m-1}(n,p)$)} 
if there are $x\in X$ and $y\in Y$ such that there is an $xy$-chain 
contained in $\cP_{m+1\dots n-m-1}(n,p)$.
\begin{lem}
\label{lem:link}
 Let $\eps>0$, $c \ge e$ and $m \in \mathbb{N}$ be given.
 Let $p=c/n$ and define $\eta=\eta(c)$ as in {\rm (\ref{eq:defeta})}.
 Let $a=a(c,\eps )$ be as in Proposition \ref{prp:defab}. Let
 \[ b=\left\lceil {2a}/{(1-\eta-\eps)} \right\rceil. \] 
 Furthermore let $X \subseteq \mathcal{P}_{m}(n)$ with ${|X|} = b$ and  
 $Y \subseteq \mathcal{P}_{n-m}(n)$ with ${|Y|} = b$
 and $x\subset y$ for any $x\in X$ and $y\in Y$ be given. 
 Then for large enough $n$ 
  \[ \pr (\mbox{$X$ and $Y$ can be linked}) 
  \ge 1-\eps.\]
\end{lem}
Lemma~\ref{lem:delta} implies that a single pair $x \subset y$ is linked with 
probability bounded away from zero.
Hence in order to prove Lemma~\ref{lem:link} we would like to consider 
several pairs at the same time to ensure that 
with arbitrarily high probability we can find at least one that is linked 
by a chain. The following lemma 
tells us that this is indeed possible, provided the elements at each level 
are far enough apart. 

Given $x$, $y \in \cPn$ with $x \subset y$, denote by $\cP^{xy}$ the 
subset of $\cPn$ consisting of all elements (including $x$ and 
$y$) which are both subset of $y$ and superset of $x$.
\begin{lem}
\label{lem:intersect}
Let $t$, $h \in \mathbb{N}$  be given.
Suppose that $x_1$, $x_2 \in \cP _t (n)$ and 
$y_1$, $y_2 \in \cP _{n-t}(n)$
are such that  $x_1 \subset y_1$, $x_2 \subset y_2$, 
$d_H (x_1,x_2) \geq h$ and $d_H (y_1,y_2) \geq h$. 
Then the 
proportion of all $x_1 y_1$-chains that meet $\cP ^{x_2 y_2}$ is at most  
$2e^{-h/2}$, provided $n$ is large enough. 
\end{lem}
\proof
Let $\bar{x}=x_1 \cup x_2$ and $\bar{y}=y_1 \cap y_2$.
Then one may easily 
verify that $\cP ^{x_1 y_1} \cap \cP ^{x_2 y_2} = \cP ^{\bar{x} 
\bar{y}}$. Furthermore $\bar{x}$ has cardinality at least $t+h$ and 
$\bar{y}$ has cardinality at most $n-(t+h)$. 
The crucial observation now is that any $x_1 y_1$-chain which 
meets $\cP^{x_2 y_2}$ must be \emph{contained} in  
$\cP^{x_1 \bar{y}} \cup \cP ^{\bar{x} y_1}$. 
For suppose an $x_1 y_1$-chain contains a $z\in \cP ^{x_2 y_2}$.
Then all elements in that chain below $z$ are contained in $\cP^{x_1 \bar{y}}$
and all elements above $z$ are contained in $\cP ^{\bar{x} y_1}$.  
It follows that any $x_1 y_1$-chain which 
meets $\cP^{x_2 y_2}$ intersects 
$(\cP^{x_1 \bar{y}} \cup \cP ^{\bar{x} y_1}) \cap 
                                  \cP_{\lfloor n/2 \rfloor} (n)$. 
But the fraction of such chains among all $x_1 y_1$-chains is at most
\[ \frac{|(\cP^{x_1 \bar{y}} \cup \cP ^{\bar{x} y_1})\cap 
                                    \cP_{\lfloor n/2 \rfloor} (n)|}
{|\cP ^{x_1 y_1}\cap \cP_{n/2} (n)|}
\le 2 
\left. {n-2t-h \choose \lfloor (n-2t)/2 \rfloor}\right/ 
        {n-2t \choose \lfloor (n-2t)/2 \rfloor}
\le  2e^{-h/2} \]
and the lemma follows.  \endproof

We are now ready to prove the Lemma~\ref{lem:link}. In the sequel, we will
make use of the following form of the second moment inequality:
\begin{equation}\label{eq:2ndmoment}
 \pr (X_{\cS}=0) \leq
   1-\frac{\ex(X_{\cS})^2}{\ex(X_{\cS}^2)}.
\end{equation}
A proof of this elementary inequality may be found in~\cite{bol}.

\proofof Lemma \ref{lem:link}. 
Let $a$ be as in Proposition~\ref{prp:defab} and set  $h = \log{4a}$.
For each $x \in X$ consider the upward $x$-branching process.
For each such process the probability of survival during the next $h$ steps is
at least $1-\eta -\eps$. We may assume that $n$ is large enough 
to ensure that the probability that these processes
intersect is at most $\eps$.
Thus, by the definition of $b$ in Lemma~\ref{lem:link} and
by Proposition \ref{prp:defab}, with probability at least
$1-2 \eps$ there are
  $a$ processes which survive until level $m+h$. Pick one
  descendant $x_i \in \cP _{m+h} (n)$ of each, where $1 \leq i \leq a$.
   Let $X^{'}= \{ x_1 , \dots,x_a \}$.
    Note that we may find $\bar{X} \subset X$, 
 $\bar{X}=\{\bar{x}_1, \dots, \bar{x}_a \}$, so that there
  is an $\bar{x}_i x_i$-chain in $\pnp$ for all $i$. Analogously,
with probability $1-2\eps$, we may find a set 
   $Y^{'} = \{ y_1 , \dots ,y_a \}$
    with $Y^{'} \subset \cP _{n-m-h} (n)$ and which is linked to $Y$ in a 
similar way.
Now assume that $n$ is large enough to ensure that with probability 
at least $1-\eps$ 
these branching processes have the following property: 
$(x_i \backslash \bar{x}_i) \cap 
(x_j \backslash \bar{x}_j)=\emptyset$ 
for all pairs $i \neq j$, and similarly for the $y_i$. The latter 
implies that $d_H(x_i,x_j) \geq 2h$ and $d_H(y_i,y_j) \geq 2h$ for
 $i \neq j$.

Now let $\cS_i$ be the set of $x_iy_i$-chains and let
 $\cT_i\subseteq \cS_i$
  be the set of $x_iy_i$-chains not meeting
  $\bigcup_{j \neq i} \cP^{x_jy_j}$.
We let  $Y_i = X_{\cS_i}$ and
$Y_i^{'} = X_{\cT_i}$, where the notation is as in (\ref{eq:defXS}). 
We also let $\Delta_i =\Delta(\cS_i)$
and $\Delta_i^{'} =\Delta(\cT_i)$, using the notation of 
(\ref{eq:defDeltaS}).
Note that Proposition~\ref{prp:regexp} certainly implies that 
$\ex(Y_i) \le \ex(Y_i)^2$. Thus by the definition of $\Delta_{\cS_i}$ and 
Lemma~\ref{lem:delta} (with $t=m+h$ and $d=1$) 
we have
$$\ex(Y_i^2) \le \Delta_{i} + \ex(Y_i) + \ex(Y_i)^2
             \le 11 \ex(Y_i)^2.$$
Now  $Y_i^{'} \le Y_i$ implies that  $\ex(Y_i^{'2}) \le \ex(Y_i^2)$.          
But since $2a\exp(-h) \le 1/2$, Lemma~\ref{lem:intersect} shows that 
$\ex (Y_i^{'}) \geq \ex (Y_i)/2$. 
Altogether this implies that
$$\frac{\ex(Y_i^{'})^2}{\ex(Y_i^{'2})}
  \ge \frac{\ex(Y_i^2)}{4\ex(Y_i^{2})}
  \ge \frac{1}{44}.$$
Thus applying in turn the independence of the $Y_i^{'}$, 
the second moment inequality~(\ref{eq:2ndmoment}),
and the definition of $a$ in Proposition~\ref{prp:defab}, 
 we have (for $n$ sufficiently large)
$$\pr \left( \bigcap_{i=1}^a Y_i^{'}=0 \right)  
        =  \prod_{i=1}^{a} \pr \left( Y_i^{'}=0 \right)
        \le \left( \frac{43}{44} \right)^a \le \eps$$
and the lemma follows. \endproof
In the remainder of this section we shall
define $(X_t^n)_{t=0}^{n}$ as the Markov chain of an upward 
$\emptyset$-process and $(Y_t^n)_{t=0}^{n}$ as that of a downward
 $\left[ n \right]$-process.
%It is easy to see that for fixed $t_0$, the distribution of 
%$(X_t^n)_{t=0}^{t_0}$ converges to that of a Poisson branching process  
%(cf. Proposition~\ref{prp:defm}).    \\ 
We need a final preparation for the proof of Theorem~\ref{thm:long}:
\begin{prp}
\label{prp:defm}
For a given $c \geq e$ define $\eta=\eta(c)$ as in 
{\rm (\ref{eq:defeta})} and let $p=c/n$. 
Let $0<\eps < 1-\eta$ and $b \in \mathbb{N}$ be given. Then there exist
 $m_0$, $n_0 \in \mathbb{N}$ so that for $m \in\{ m_0,m_0+1\}$ and all 
 $n\ge n_0$, we have
\begin{eqnarray}
 \pr (X_m^n  = 0  ) & \ge & \eta - \eps  \label{eq:defm1}, \\
\pr  (X_m^n \ge b ) & \ge & 1- \eta -  \eps.  \label{eq:defm2}
\end{eqnarray} 
\end{prp}
\proof
Let $(X_m)_{m=0}^{\infty}$ be a Poisson branching process with parameter 
$c$. 
Note that  $\pr (X_m =0) \uparrow \eta $. Thus  by (\ref{eq:harris}) there 
is an  $m_0$ such that for $m \in\{ m_0,m_0+1\}$ we have 
\begin{eqnarray} \nonumber
  \pr  (X_m =0) &\geq & \eta - \eps/2,   \\ \nonumber
  \pr  (X_m \leq  b \mid X_m >0) &\leq & {\eps/2}.
\end{eqnarray} 
It is straightforward to show that for fixed $m$, the random variables
$X_m^n$ tend to $X_m$ in distribution as $n\to \infty$.
This implies that (\ref{eq:defm1}) and (\ref{eq:defm2}) hold for 
sufficiently large $n$. \endproof
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\proofof Theorem \ref{thm:long}.
Let $\eps >0$ be given. 
%We set $n$ large enough to satisfy all the estimates in the proofs below.
% First note trivially that
% for any large $n$ the probability that $\pnp$ contains a chain 
% meeting all but at most one levels is at most $\eps$.  \\
We now fix an $a=a(c,\eps)$ satisfying the conditions in 
Proposition \ref{prp:defab} and let $b=\lceil 2a/(1-\eta-\eps) \rceil$. Then 
we fix  $m_0= m_0(b,\eps)$ as in
 Proposition  \ref{prp:defm} and let $m=m_0+1$.
 Consider the branching processes 
$(X_t^n)_{t=0}^{n}$, $(Y_t^n)_{t=0}^{n}$ defined earlier. 
We will distinguish several cases according to their
 (non)-extinction during the first $m$
generations. To do so we first define some events. 
For $\cQ\subseteq \cPn$ and $i=0$, $1$ call $x\in \cQ_m$ {\em $i$-connected}
if there is a $zx$-chain in $\cQ$ for some $z \in \cP_i(n)$.
Then we define 
\begin{eqnarray*}
  \cA & = &\{\cQ\subseteq \cPn\colon \emptyset,\,[n] \not\in \cQ\}; \\
  \cBu & = &\{\cQ\subseteq \cPn\colon \cQ_m \mbox{ contains 
     $b$ elements which are $0$-connected}\};   \\
  \cCu & = &\{\cQ\subseteq \cPn\colon \cQ_m \mbox{ contains 
      $b$ elements which are $1$-connected}\}.
\end{eqnarray*}
Here the superscript  accounts for the fact that we consider the
upward branching process. 
Observe that $\cQ\in \cBu$ iff $X_m^n(\cQ)\ge b$. 
For later use we now give some related definitions.
First we equip the elements from $\cP_m(n)$  with a
 total ordering by letting  $x<y$ if $\min x\backslash y <
 \min y\backslash x$. Now 
define $B_m(\cQ)$ to be the set of the first $b$ elements 
in $\cQ_m$ which are $0$-connected. If there are less than $b$
elements in $\cQ_m$ which are $0$ connected then let  $B_m(\cQ)$ consist  
of all of these. 
Analogously define $C_m(\cQ)$ to be the set of the smallest elements 
in $\cQ_m$ which are $1$-connected (again at most $b$ of them). 

Now we define some  events for the downward branching
process. To make them
fit with the upward branching process we slightly refine the
above definitions. 
For $i=0$, $1$ call an element
$y \in  \cQ_{n-m}$  {\it strongly $(n-i)$-connected}  if 
for any $x\in B_m(\cQ)\cup C_m(\cQ)$, we have $x\subset y$, and furthermore  
there is a $yz$-chain in $\cQ$ for some $z \in \cQ_{n-i}$. 
With this notion we define 
\begin{eqnarray*}
  \cBd & = &\{\cQ\subseteq \cPn\colon \cQ_{n-m} \mbox{ contains 
     $b$ strongly $n$-connected elements}\};   \\
  \cCd & = &\{\cQ\subseteq \cPn\colon \cQ_{n-m} \mbox{ contains 
     $b$ strongly $(n-1)$-connected elements}\}.
\end{eqnarray*}
Observe that all events defined above only depend on 
$\cP_{0\dots m}(n,p) \cup \cP_{n-m\dots n}(n,p)$. 
Also observe that
\begin{equation}
\label{eq:ln-1}
 \pr( \length \pnp\ge n-1) \le 1-\pr(\cA) \le \eps.
\end{equation}
Now we estimate $ \pr( \length \pnp\ge n-2)$.
Assume that $\cBu$ and $\cBd$ both  hold. Then there exist   
$X\subseteq \cP_m(n,p)$ and
$Y\subseteq \cP_{n-m}(n,p)$  with $|X|=|Y|=b$ such that all
elements from $X$ are 0-connected in $\pnp$ and 
all elements from $Y$ are strongly  $n$-connected in $\pnp$.
We may assume that $X$ contains the $b$ smallest 0-connected elements
and thus $x\subset y$ for any $x\in X$ and
$y\in Y$.
If $X$ and $Y$ can be linked then $\length \pnp \geq n-2$.
Observe that the event that $X$ and $Y$ can be linked only depends
on  $\cP_{m+1\dots n-m-1}(n,p)$.
Hence if $\cBu$ and $\cBd$ hold then by
applying  Lemma~\ref{lem:link} we have that
\[ 
  \pr\big(\length\pnp\ge n-2\,\big|\,\cBu\cap\cBd\big)\ge1-\eps. 
\]  
By (\ref{eq:defm2}) from Proposition \ref{prp:defm}, we have 
\begin{equation}
  \label{eq:prBu}
   \pr (\cBu)  \ge  1-\eta-\eps. 
\end{equation} 
As $b$ and $m$ are constant, the probability that a fixed 
$y \in \cP_{n-m}(n)$
does not contain all elements from $B_m(\cP(n,p))\cup C_m(\cP(n,p)) $ 
 is $\cO(1/n)$.  
Hence, 
\begin{equation}
   \label{eq:prBd}
   \pr (\cBd)  \ge  1-\eta-2\eps 
\end{equation} 
provided $n$  is large enough. Thus,
\begin{equation}
  \label{eq:ln-2low}
   \pr( \length \pnp\ge n-2) \ge ( 1- \eps) ( 1-\eta-\eps)( 1-\eta-2\eps).
\end{equation}

On the other hand, if $\length \pnp\ge n-2$ and $\cA$ does not hold, then 
certainly $X_m^n>0$ and $Y_m^n>0$. Thus, by (\ref{eq:defm1})
 from Proposition \ref{prp:defm},
\begin{eqnarray}
   \nonumber
   \pr( \length \pnp\ge n-2) & \le & \pr( X_m^n>0 \mbox{ and } Y_m^n>0)
      + \pr( \cA) \\
   & \le & ( 1-\eta+\eps)^2 +\eps.\label{eq:ln-2up}
\end{eqnarray}

Now we consider $ \pr( \length \pnp\le n-4)$.
We first estimate $\pr(\cCu)$. 
Let $k$ satisfy $(\eta+\eps)^k \leq 
\eps/2$. Let $x_i=\{i\}$ for $i=1,\dots, k$. For each 
$x_i$, consider the upward $x_i$-branching process. 
Let $\cD$ denote the event that the branching processes
are disjoint up to level $m$, i.e., 
$x'_i \ne x'_j$ whenever $i \ne j$, $x_i \subset x'_i$,  $x_j \subset x'_j$,
and $x_i'$, $x_j' \in \cP_{1 \dots m}(n,p)$. 
Then $\pr (\cD) \ge 1-\eps/2$. 
Observe that $\cCu$ holds
if at least one of the branching processes has (at least) $b$ descendants
in the $m$th generation. Hence, by (\ref{eq:defm2})
from Proposition \ref{prp:defm}, we have
$\pr (\neg \cCu\mid\cD) \le  (\eta+\eps)^k \le  \eps/2 $. Thus, 
\begin{equation}
     \label{eq:prCu}
     \pr(\cCu)\ge 1- \eps. 
\end{equation}
As in the proof of  (\ref{eq:prBd}), we have
\begin{equation}
    \label{eq:prCd}
     \pr(\cCd)\ge 1- 2\eps. 
\end{equation}
Moreover, if $\cBu$ and $\cCd$ both hold, then Lemma~\ref{lem:link} 
implies that with probability 
at least $1-\eps$ we have  $\length \pnp \geq n-3$. The same is true
if  $\cBd$ and $\cCu$ both hold. Hence by (\ref{eq:prBu}),  (\ref{eq:prBd}),
using that $\cBu$ and $\cBd$ are independent,  (\ref{eq:prCu}),
and  (\ref{eq:prCd}) imply
\begin{eqnarray*} 
  \pr( \length \pnp\ge n-3) &\ge &  (1-\eps)\pr\big( (\cBu\cap \cCd)\cup 
     (\cBd\cap \cCu)\big) \\ 
  & \ge &  (1-\eps)\pr\big( \cBu \cup \cBd\big) 
             - \pr\big(\neg(\cCu\cap \cCd)\big)  \\
  & \ge &  (1-\eps) (1-(\eta+\eps)(\eta+2\eps)) - 3\eps. 
\end{eqnarray*}
Thus
\begin{eqnarray}
\nonumber
\pr( \length \pnp\le n-4 ) & \le &  1-(1-\eps) 
                     (1-(\eta+\eps)(\eta+2\eps)) + 3\eps \\
\label{eq:ln-4up} & \le & (\eta+2\eps)^2+ 4\eps. 
\end{eqnarray}

On the other hand, if both branching processes do not survive
(and $\emptyset$, $[n]\not\in \pnp$) then the length can be at most $n-4$.    
Thus by (\ref{eq:defm1})
 from Proposition~\ref{prp:defm},
\begin{eqnarray}
\nonumber
\pr( \length \pnp\le n-4) &\ge& \pr( X_m^n = 0 \mbox{ and  } Y_m^n=0)
 - \pr( \cA)  \\  \label{eq:ln-4low}
 &\ge&   (\eta-\eps)^2 - \eps. 
\end{eqnarray}

Finally if both $\cCu$ and $\cCd$ hold then with probability 
at least $1-\eps$ we have  $\length \pnp \geq n-4$. Hence by (\ref{eq:prCu}) and (\ref{eq:prCd})
\begin{equation}
\label{eq:ln-5}
\pr( \length \pnp\le n-5 ) \le 4\eps. 
\end{equation}
The theorem now follows from (\ref{eq:ln-1}), 
(\ref{eq:ln-2low}), (\ref{eq:ln-2up}), (\ref{eq:ln-4up}), 
(\ref{eq:ln-4low}), and (\ref{eq:ln-5}) by using the fact that $\eps$ 
is arbitrary. \endproof

We remark that the methods of this section would also enable us to 
replace the condition $pn^r \to \infty$ by $pn^r \ge C$ for some $C$
depending only on the constant $r$ in the statement of Corollary~
\ref{cor:medium}. However, the analysis is rather cumbersome if $r$ 
is not an integer, so we have chosen to omit it.   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%{\renewcommand{\section}{\subsection}

\begin{thebibliography}{}

\bibitem{aes} N.\ Alon and J.H.\ Spencer,
 {\sl The Probabilistic Method}, Wiley, 1992. 

\bibitem{bol} B.\ Bollob\'{a}s, 
  {\sl Random graphs}, Academic Press, London, 1985.
    
\bibitem{bb} B.\ Bollob\'{a}s and G.~Brightwell, 
  Random high-dimensional orders,
 {\em Adv. Appl. Prob.} {\bf 27}, 161--184 (1995).

\bibitem{bkl1} B.\ Bollob\'{a}s, Y.\ Kohayakawa, and T.\ {\L}uczak,
 On the diameter and radius of random subgraphs of the cube,
 {\sl Random Struct. Alg.}, {\bf 5}, 627--648 (1994).

\bibitem{bkl2} B.\ Bollob\'{a}s, Y.\ Kohayakawa, and T.\ {\L}uczak, 
 Connectivity properties of random subgraphs of the cube, 
 {\sl Random Struct. Alg.}, {\bf 6}, 221--230  (1995).

\bibitem{br} G. Brightwell, Models of random partial orders,
  {\em Surveys in Combinatorics 1993} (K. Walker, Ed.), pp. 53--83, 
  Cambridge Univ. Press, Cambridge, UK. 

\bibitem{fp}  J.E.\ Fill and R. Pemantle, 
  Percolation, first-passage
 percolation and covering times for Richardson's model of the $n$-cube,
{\sl Annals Appl. Probab.} {\bf 3} (2), 593--629 (1993).

\bibitem{har} T.E.\ Harris, {\sl The Theory of Branching Processes}, 
 Springer Verlag, Berlin, 1963.


\bibitem{kkr} Y.\ Kohayakawa and B.\ Kreuter, 
  The width of random subsets of Boolean lattices, submitted, 1998.

\bibitem{kr} B.\ Kreuter, 
 Small sublattices in random subsets
 of Boolean lattices, {\sl Random Struct. Alg.}, to appear. 

\bibitem{ost} D. Osthus, 
  Maximum antichains in random subsets of the 
  Boolean lattice (in preparation).

\bibitem{re}
A.~R\'enyi.
\newblock On random subsets of a finite set,
\newblock {\em Mathematica {\rm(}Cluj{$\,$\rm)}}, {\bf 3} (26), 355--362
(1961). 


\end{thebibliography}

\end{document}















