%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% LaTeX2e file for 
%
% ``The Width of Random Subsets of Boolean Lattices''
% 
% by Y. Kohayakawa and B. Kreuter
%
% FINAL VERSION
%
% submitted : 11. Februar 1998
% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[11pt]{article}
\usepackage{latexsym}
\def\thebibliography#1{\section*{References\markboth
 {REFERENCES}{REFERENCES}}\list
 {[\arabic{enumi}]}{\settowidth\labelwidth{[#1]}\leftmargin\labelwidth
 \advance\leftmargin\labelsep\setlength{\parsep}{0pt}%
 \setlength{\itemsep}{3pt}%
 \usecounter{enumi}}
 \def\newblock{\hskip .11em plus .33em minus -.07em}
 \sloppy
 \sfcode`\.=1000\small\relax}
\let\endthebibliography=\endlist
\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}} 
\outer\def\endproofnosquare{\removelastskip\penalty-10\bigskip}
\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}
\def\endassertion{\egroup\par\ifdim\lastskip<\smallskipamount
                \removelastskip\penalty20\smallskip\fi}
\def\assertion(#1){\smallbreak\noindent 
  {\rm(}{#1}{\rm)}\enspace\ignorespaces\bgroup\sl}
\def\endcasebody{\par\ifdim\lastskip<\smallskipamount
                \removelastskip\penalty-20\smallskip\fi}
\def\casebody{\noindent\ignorespaces}
\def\Nset{\hbox{I\hskip-0.20em I\hskip-0.35em N}}        
\def\Qset{\hbox{\hbox{Q\hskip-0.525em\lower-0.097ex
          \hbox{\vrule height1.47ex width0.07em}}\hskip0.50em}}
\def\Rset{\hbox{I\hskip-0.23em R}}
\def\Zset{\hbox{Z\hskip-0.38em Z}}\oddsidemargin 3mm
\evensidemargin 3mm  
\textwidth15.3cm
\newtheorem{lem}       {Lemma}
\newtheorem{thm} [lem] {Theorem}
\newtheorem{cor} [lem] {Corollary}
\newtheorem{prp} [lem] {Proposition}
\newtheorem{NB}  [lem] {Remark}

\newtheorem{con} [lem] {Conjecture}
\def\Forb{{\cal F}\kern-.202em\hbox{\it orb}}
\def\ex{\mathop{{\rm ex}}}
\def\({\left(}
\def\){\right)}  
\def\e{{\hbox{\rm e}}}
\def\E{{\bf E}}
\def\textit#1{{\it #1\/}}
\def\MPCPS{Math. Proc. Cambridge Phil. Soc.}
\def\JAMS{J. Amer. Math. Soc.}

\let\epsilon=\varepsilon
\let\eps=\epsilon
\let\ln=\log

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% New macros
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\ycite#1{}
\def\cA{{\cal A}}
\def\cB{{\cal B}}
\def\cC{{\cal C}}
\def\cF{{\cal F}}
\def\cG{{\cal G}}
\def\cP{{\cal P}}
\def\cL{{\cal L}}
\def\cV{{\cal V}}\def\cK{{\cal K}}
\def\cR{{\cal R}}

\def\P{{\bf P}}
\def\bfV{{\bf V}}
\def\bfW{{\bf W}}
\def\bV{{\bar V}}
\def\bU{{\bar U}}
\def\bgamma{{\bar\gamma}}\def\bgam{{\bar\gamma}}
\def\bm{{\bar m}}
\def\bp{{\bar p}}
\def\bepsilon{{\bar\epsilon}}
\def\bd{{\bar d}}
\def\bB{{\bar B}}
\def\bC{{\bar C}}
\def\bD{{\bar D}}
\def\bT{{\bar T}}
%\def{\em aas}{{\em whp }}
%\def\Whp{{\em Whp }}

\def\brho{{\bar\rho}}
\def\bbfV{{\bar\bfV}}
\def\cU{{\cal U}}
\def\cH{{\cal H}}
\def\tH{{\widetilde H}}
\def\tp{{\widetilde p}}
\def\pH{{p_H}}
\def\pO{{p_0}}
\def\d0{{d_0}}
\def\Aut{\mathop{\!\hbox{\rm Aut}}}
\def\im{\mathop{{\rm im}}}
\def\sgn{\mathop{{\rm sgn}}}
\let\:=\colon
\def\bv{{\bf v}}
\def\bal{{\bar{\alpha}}}\def\balpha{{\bal}}
\def\bbeta{{\bar{\beta}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\bfG{{\bf G}}
\def\tbfG{{\widetilde{\bf G}}}
\def\cG{{\cal G}}\def\cQ{{\cal Q}}
\def\cH{{\cal H}}
\def\cF{{\cal F}}
\def\cE{{\cal E}}\def\cO{{\cal O}}
\def\lan{$\langle$}
\def\ran{$\rangle$}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\title{The Width 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 %\thanks{Part of this work was done while this
    %author was visiting the University of S\~ao Paulo 
    %supported by a DAAD--CAPES exchange programme.}
    {}\\\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} 
    }
    \date{}
\maketitle
\vspace{-.8cm}
\begin{abstract}\noindent
  Suppose we toss an independent coin with probability of success~$p$
  for each subset of~$[n]=\{1,\dots,n\}$, and form the random
  hypergraph~$\cP(n,p)$ by taking as hyperedges the subsets with
  successful coin tosses.  We investigate the cardinality of the
  largest Sperner family contained in~$\cP(n,p)$.  We obtain a sharp
  result for the range of~$p=p(n)$ in which this Sperner family has
  cardinality comparable to the cardinality of~$\cP(n,p)$.
\end{abstract}
\vspace*{0.2cm}
%{\noindent
%\small
%{\it AMS subject classification code\/} (1991):{\it Key words and
%phrases\/}:

\section{Results}
In this note we investigate random non-uniform hypergraphs,
\textit{i.e.}, random families of subsets of an $n$-element set, or,
equivalently, a random subset of the Boolean lattice $\cP(n)=2^{[n]}$,
where, as usual, $[n]=\{1,\dots,n\}$.  Such random hypergraphs were
probably first investigated by R\'enyi~\cite{Re} who, answering a
question of Erd\H{o}s, determined the minimum cardinality of a family
of random subsets of~$[n]$ that guarantees, with high probability, two
distinct sets~$A$ and~$B$ with~$A\subset B$.  A family containing no
such pair of sets, \textit{i.e.}, inducing no relation in the Boolean
lattice, is usually called a \textit{Sperner family}.  The size of the
largest Sperner family in a set-system~$\cQ\subset \cP(n)$ is simply
the \textit{width} of~$\cQ$ when~$\cQ$ is viewed as a poset, and we
shall denote it here by~$\alpha(\cQ)$.  For any given~$0<p=p(n)<1$,
let the random set-system~$\cP(n,p)$ be defined by picking each
element of~$\cP(n)$ independently at random with probability~$p$.
Denote by~$\Phi$ the distribution function of the normal distribution,
\textit{i.e.},
\[  
\Phi(b)=\frac{1}{\sqrt{2\pi}}
         \int_{-\infty}^b \exp(-x^2/2)\,dx.
\]
For two functions~$f(n)$ and~$g(n)$, write~$f\sim g$ if 
$\lim_{n\to\infty}f(n)/g(n)=1$  and~$f\asymp g$
if
$$
  0<\liminf_{n\to\infty}f(n)/g(n)\leq\limsup_{n\to\infty}f(n)/g(n)<\infty.  
$$

Our main result in this note may be formulated as follows.  In the
sequel, we use the term \textit{almost surely} to mean `with
probability tending to~$1$ as~$n\to\infty$'.

\begin{thm} \label{thm:width}
  Let $b>0$ be a constant and $p = n^{-b\sqrt{n}}$.  Then we almost 
  surely have
  \[
   \frac{\alpha(\cP(n,p))}{|\cP(n,p)|}\sim\Phi(2b)-\Phi(-2b).
  \]
\end{thm}

In fact, it will follow from the proof of Theorem~\ref{thm:width} that
the following structural result holds.

\begin{thm} 
  Almost surely, one may obtain a Sperner family of
  cardinality~$\sim\alpha(\cP(n,p))$ from~$\cP(n,p)$ by taking all
  members of~$\cP(n,p)$ whose cardinalities are in the interval
  $\{\lfloor n/2-b\sqrt{n}\rfloor,\dots,\lfloor
  n/2+b\sqrt{n}\rfloor\}$, and then removing from this family the
  elements that are contained in some other element of the family.
\end{thm}

An immediate corollary to the results above is that, for~$\epsilon>0$
and~$p=n^{-\eps\sqrt{n}}$, we almost surely have
\[  
  \frac{\alpha(\cP(n,p))}{|\cP(n,p)|}
   \sim\epsilon\(1+\cO\(\epsilon^2\)\)\sqrt{8\over\pi}.
\]

The proof of Theorem~\ref{thm:width} is given in the next section.
For results concerning the \textit{length} of~$\cP(n,p)$,
\textit{i.e.}, the cardinality of a longest chain, the reader is
referred to~\cite{KKrOlength}.  The threshold function for small
sublattices in~$\cP(n,p)$ are investigated in~\cite{Krla}, which may
be thought of as a modern sequel to R\'enyi's pioneering
work~\cite{Re}.

\section{Proofs}

\subsection{Proof of Theorem~\ref{thm:width}}
\label{sec:proof_thm_width}
Before giving the proof of Theorem~\ref{thm:width}, we state some
asymptotics involving binomial coefficients.  To simplify the
notation, we shall often omit the~$\lfloor\hphantom{x}\rfloor$
and~$\lceil\hphantom{x}\rceil$ signs whenever they are not crucial.
Moreover, we may and shall assume whenever needed that~$n$ is larger
than any fixed absolute constant.

Let $k$, $\ell$ be integers with $|k|$, $|\ell|=\cO(\sqrt{n})$ and
$k+\ell>0$.  Then,
\begin{eqnarray} 
  \nonumber
  {n\choose\frac{n}{2}-k,\frac{n}{2}-\ell,k+\ell}
    &=&{n-k-\ell\choose\frac{n}{2}-k}{n\choose k+\ell}\\
    \nonumber
    &\asymp&\frac{2^{n-k-\ell}}{\sqrt{n}}
             \times\frac{n^{k+\ell}}{(k+\ell)!}\\
    \label{eq:nchooseij}
    &\asymp&\frac{2^{n}}{\sqrt{n(k+\ell)}}
             \(\frac{\e n}{2(k+\ell)}\)^{k+\ell}. 
\end{eqnarray}
For later reference, notice that the multinomial coefficient on the
left-hand side of~(\ref{eq:nchooseij}) counts the number of
pairs~$(A,B)$ with~$A\subset B\subset[n]$, $|A|=n/2-k$,
and~$|B|=|A|+k+\ell$.

For integers~$k$ and~$m$ with~$k=\cO(\sqrt{m})$ and large enough $m$,
the following rough bound holds:
\begin{equation}
  \label{eq:mk}
  {m\choose k}\ge{1\over m}\(\e m\over k\)^k.
\end{equation}
Let an integer~$i$ with~$|i|\le(\log n)\sqrt{n}$ and a real number~$b$
with $0<b=\cO(1)$ be given.  Then, for large $n$, we have
\begin{eqnarray} \nonumber  %\left.
 \left. {n\choose\lfloor n/2\rfloor+i}\right/
         {n\choose\lfloor n/2\rfloor+i+\lfloor b\sqrt{n}\rfloor}
    &\le& \(1+\frac{2|i|+b\sqrt n}{n/2-|i|-b\sqrt n+1}\)^{b\sqrt{n}} 
   \\  \label{eq:nni} 
   &\le& \exp\(\frac{5\log n}{\sqrt{n}}b\sqrt{n}\)
    =n^{5b}.
\end{eqnarray}
 
For a set-system~$\cQ\subseteq \cP(n)$ and an integer~$i$ with~$|i|\le
n/2$, denote by~$\cQ_i$ the $(\lfloor n/2\rfloor-i)$-th \textit{layer}
of~$\cQ$, \textit{i.e.},
\[ 
  \cQ_i=\{x\colon x\in\cQ\mbox{ and }|x|=\lfloor n/2\rfloor-i\}.
\]
For a set of integers~$S\subseteq\{-\lceil n/2\rceil,\dots,\lceil
n/2\rceil\}$, let~$\cQ_S=\bigcup_{i\in S}\cQ_i$.  The set~$\cQ_S$ will
sometimes be viewed as a graph, where~$\{x,y\}$ is an edge in~$\cQ_S$
if and only if~$x\subset y$ or~$y\subset x$.  Instead of~$\cP(n,p)_S$
we write~$\cP_S(n,p)$, and instead of~$\cQ_{\{i,j\}}$ we
simply write~$\cQ_{i,j}$. 

Suppose~$0<p<1$ and~$0<\epsilon<1$ are given, and let $X$ be
binomially distributed with parameters~$p$ and~$N$. Then, the standard
Chernoff bound for large deviations states that
\begin{equation}
  \label{eq:chernoff}
  P\big[|X-Np|\ge \eps Np\big]\le2\exp\(-\frac{1}{3}\eps^2Np\).
\end{equation}
This implies the following very rough bound on~$|\cP_i(n,p)|$.

\assertion(*) Suppose~$p\ge(2/3)^n$.  Then, with probability at
least~$1-\exp\left\{-(5/4)^n\right\}$, for every integer~$i$
with~$|i|\le(\log n)\sqrt{n}$, we have
%\begin{equation} \label{eq:iconcentrated}
$$
  |\cP_i(n,p)|
    =\(1+\cO\(1\over n\)\){n\choose\lfloor n/2\rfloor-i}p.
$$
%\end{equation}
\endassertion

Let now a positive integer~$n$, reals~$0<\eps(n)<1$, $0<p(n)<1$,
and~$c=c(n)>0$ be given.  Let~$j$ be an integer
with~$c\sqrt{n}\le|j|\le(\log n)\sqrt{n}$.  Define~$i=i(j)$ by putting
\begin{equation}
  \label{eq:defi}
  i=j-\sgn(j)\lfloor 2c\sqrt{n}\rfloor,
\end{equation}
where~$\sgn(j)$ denotes the sign of~$j$.  Note that, then, we
have~$|j-i|=\lfloor2c\sqrt n\rfloor$ and, moreover, $|i|\leq|j|$.  In
what follows, we shall often be interested in the bipartite
graph~$\cQ_{i,j}$ with~$i$ and~$j$ as above.  We now introduce some
important definitions for what follows.

We shall say that~$\cQ\subseteq\cP(n)$ is
$(c,\eps,p,j)$-\textit{uniform} if properties~(\textit{a}) and
(\textit{b}) below are fulfilled.
\begin{list}{(a)}{\itemsep-1mm}
\item[({\it a\/})] The number of vertices of~$\cQ_{i,j}$ that have 
  degree larger than 
  $$
    (1+\eps){n/2+|j|\choose\lfloor2c\sqrt{n}\rfloor}p
  $$ 
  is at most~$2\exp(-\eps^{-1})|\cQ_j|$. 
\item[({\it b\/})] The number of vertices in~$\cQ_j$ that have
  $\cQ_{i,j}$-degree smaller than 
  $$
    (1-\eps){n/2+|j|\choose\lfloor2c\sqrt{n}\rfloor}p
  $$
  is at most~$\exp(-\eps^{-1})|\cQ_j|$. 
\end{list}
The set-system~$\cQ\subseteq\cP(n)$ is called
$(c,\eps,p)$-\textit{uniform} if the following properties are
fulfilled:
\begin{list}{(iii)}{\itemsep-1mm}
\item[({\it i\/})] For all integers~$j$ with~$|j|\le(\log n)\sqrt{n}$,
  we have
  $$
    |\cQ_j|=(1+\Theta(1/n)){n\choose\lfloor n/2\rfloor-j}p.
  $$
\item[({\it ii\/})] Let~$S=\{-n/2,\dots,-(\log n)\sqrt{n}\}\cup\{(\log
  n)\sqrt{n},\dots,n/2\}$.  Then~$|\cQ_S|\le 2^n p/n$.   
\item[({\it iii\/})] For all integers~$j$
  with~$c\sqrt{n}\le|j|\le(\log n)\sqrt{n}$, the set-system~$\cQ$ is
  $(c,\eps,p,j)$-uniform.
\end{list}
Now we state three lemmas that together imply Theorem~\ref{thm:width}.

\begin{lem}
  \label{lem:lowerbd}
  Let~$c=c(n)>0$ with~$c=\cO(1)$ be given.  Let
  $p=n^{-c\sqrt{n}}(4c/\e)^{2c\sqrt{n}}$ and
  put~$S=\{-c\sqrt{n},\dots,c\sqrt{n}\}$.  Then, almost surely, the
  number of edges in~$\cP_S(n,p)$ is at most~$2^np/\sqrt n$.
\end{lem}

\begin{lem} \label{lem:pnpunif}
  For~$c=c(n)>0$ with~$c=\cO(1)$, define $\eps=2^{-c\sqrt{n}/2}$, and
  $p=n^{-c\sqrt{n}}(9c/\e)^{2c\sqrt{n}}$.  Then, almost surely, the
  random set-system~$\cP(n,p)$ is $(c,\eps,p)$-uniform.
\end{lem}

\begin{lem} \label{lem:width}
  Let~$c=c(n)>0$ with~$c=\cO(1)$ be given.   Define
  $p=n^{-c\sqrt{n}}(9c/\e)^{2c\sqrt{n}}$ and let~$0<\eps\le1/n$ be
  given.  Assume that~$\cQ$ is $(c,\eps,p)$-uniform.  Then the width
  of~$\cQ$ is at most
  \[ 
    \(\sum_{|j|<c\sqrt{n}}
       {n\choose\lfloor n/2\rfloor-j}+\cO\({2^n\over n}\)\)p.
  \]
\end{lem}

Before proving Lemmas~\ref{lem:lowerbd}, \ref{lem:pnpunif},
and~\ref{lem:width} we deduce Theorem~\ref{thm:width} from those
lemmas.   

\proofof Theorem~\ref{thm:width}.  Let $b>0$ be given.
Define~$c=c(n)$ by
\[ 
  p=n^{-b\sqrt{n}}=n^{-c\sqrt{n}}\(4c\over\e\)^{2c\sqrt{n}}.
\]
Then $c=b+o(1)$.  Let~$S$ be as in Lemma~\ref{lem:lowerbd}.  Then
removing from~$\cP_S(n,p)$ all elements that are contained in some
other element of~$\cP_S(n,p)$ yields a Sperner subfamily
of~$\cP(n,p)$.  By Lemma~\ref{lem:lowerbd} and assertion~(*) this
subfamily is almost surely of cardinality at least
\begin{eqnarray*} 
  \(1+\cO\(1\over n\)\)
    \sum_{|i|\leq c\sqrt{n}}
      {n\choose\lfloor n/2\rfloor-i}p-{2^n\over\sqrt n}p
   &\sim&(\Phi(2c)-\Phi(-2c))2^np\\ 
   &\sim&(\Phi(2b)-\Phi(-2b))2^np.
\end{eqnarray*}
This establishes the lower bound in Theorem~\ref{thm:width}.  To prove
the upper bound, now define~$c=c(n)$ by
\[ 
  p=n^{-b\sqrt{n}}=n^{-c\sqrt{n}}\(9c\over\e\)^{2c\sqrt{n}}.
\]
Again, $c=b+o(1)$.  By Lemmas~\ref{lem:pnpunif} and \ref{lem:width},
the width of~$\cP(n,p)$ is almost surely at most
\[  
  \sim\(\Phi(2c)-\Phi(-2c)+\cO\(1\over n\)\)2^np
   \sim\(\Phi(2b)-\Phi(-2b)\)2^np,
\]
and the theorem follows.  
\endproof

\subsection{Proofs of the lemmas}
\label{sec:proofs_of_lemmas}
It now remains to prove Lemmas~\ref{lem:lowerbd}, \ref{lem:pnpunif},
and~\ref{lem:width}.

\proofof Lemma~\ref{lem:lowerbd}.  Denote by~$\sum_{k,\ell}$ the sum
over all pairs of integers~$k$, $\ell$ with~$|k|$, $|\ell|\le
c\sqrt{n}$ and~$k+\ell>0$.  For~$\cQ\subseteq\cP(n)$, denote
by~$X_S(\cQ)$ the number of edges in~$\cQ_S$.  Then,
by~(\ref{eq:nchooseij}), we have
\begin{eqnarray*}
  E[X_S(\cP(n,p))]
    &\asymp&\sum_{k,\ell}\frac{2^n}{\sqrt{n(k+\ell)}}
             \(\frac{\e n}{2(k+\ell)}\)^{k+\ell} p^2 \\
    &=&\cO\(2^nn^{-3/4}\(\frac{\e}{4c}\sqrt{n}\)^{2c\sqrt{n}} p^2\)\\
    &=&\cO\(2^nn^{-3/4}p\).
\end{eqnarray*}
By Markov's inequality, almost surely we have~$X_S\le2^np/\sqrt n$, as 
required.  
\endproof

\proofof Lemma~\ref{lem:pnpunif}.  Assertion~(*) immediately gives
that condition~({\it i\/}) holds almost surely.  One may also easily
check that condition~({\it ii\/}) is almost surely satisfied.  To
prove that condition~({\it iii\/}) holds almost surely, it is enough
to show that, for any~$j$ with~$c\sqrt{n}\le|j|\le(\log n)\sqrt{n}$,
the set-system~$\cP(n,p)$ is $(c,\eps,p,j)$-uniform with probability
at least, say, $1-1/n$. 
%To do so we bound from above the probabilities
%that condition~({\it a\/}) and~({\it b\/}) fail to hold. 

Thus, in the sequel, we fix~$j$ with~$c\sqrt{n}\le|j|\le(\log
n)\sqrt{n}$ and bound from above  the probability that~$\cP(n,p)$ is
not $(c,\eps,p,j)$-uniform.  By symmetry, we may assume that~$j>0$ and
thus~$i=i(j)$ in~(\ref{eq:defi}) is~$i=j-\lfloor 2c\sqrt{n}\rfloor$.
In particular, a set in $\cP_j(n)$
contains~${n/2+j\choose\lfloor2c\sqrt{n}\rfloor}$ elements
from~$\cP_i(n)$.

For each $x\in\cP_j(n)$, let~$Y_x$ be the random variable whose value
is the the number of neighbours of~$x$ in~$\cP_i(n,p)$
if~$x\in\cP_j(n,p)$, and~$0$ otherwise.  For all $x\in \cP_j(n)$, the
random variable~$Y_x$ conditioned on~$x\in\cP_j(n,p)$ is binomially
distributed with parameters~$p$ and
$$
N={n/2+j\choose\lfloor2c\sqrt{n}\rfloor}.
$$
Furthermore, by~(\ref{eq:mk}), if~$n$ is large enough,
\begin{equation} \label{eq:boundNp}
  Np\ge{1\over n}\(\frac{\e n}{4c\sqrt{n}}\)^{2c\sqrt{n}} 
        n^{-c\sqrt{n}}\(9c\over\e\)^{2c\sqrt{n}}   
    \ge2^{2c\sqrt{n}}=\eps^{-4}.
\end{equation}
By~(\ref{eq:chernoff}), if~$X$ is binomially distributed
with parameters~$p$ and~$N$,
$$
  P\big[|X-Np|\ge\eps Np\big]
    \le2\exp\(-\frac{1}{3}\eps^2Np\)
    \le2\exp\(-{1\over3}\eps^{-2}\).
$$
%
Denote by~$Z$ the number of elements in~$\cP_j(n,p)$ with degree
larger than~$(1+\eps)Np$ or smaller than~$(1-\eps)Np$.  By linearity
of expectation,
\[
  E[Z]=\cO\(
            {n\choose\lfloor n/2\rfloor-j}p\cdot\exp\(-{1\over3}\eps^{-2}\)
          \).
\]
By Markov's inequality and assertion~(*), the probability
that~$Z > \exp\(-\eps^{-1}\)|\cP_j(n,p)|$ is, very crudely, at
most~$1/2n$.  We have thus dealt with condition~({\it b\/}) and one
part of condition~({\it a\/}).

As to the remaining part of condition~({\it a\/}), we notice that the
degree of a vertex from~$\cP_i(n,p)$ in $\cP_{i,j}(n,p)$ is binomially
distributed with parameters~$p$ and
$$
  {n/2-i\choose\lfloor2c\sqrt{n}\rfloor}
  \,\leq\,{n/2+|j|\choose\lfloor2c\sqrt{n}\rfloor}
  \,=\,N,
$$ 
%
where we made use of the fact that~$|i|\le|j|=j$.  Hence the expected
number of elements in~$\cP_i(n,p)$ with degree larger than
$(1+\eps)Np$ is, by~(\ref{eq:nni}), at most
\[ 
  2\exp\(-{1\over3}\eps^{-2}\){n\choose\lfloor n/2\rfloor+i}p
    \;\le\;2\exp\(-{1\over3}\eps^{-2}\)
         {n\choose\lfloor n/2\rfloor+j}pn^{10c},
\]
provided~$n$ is large enough.  Again, by Markov's inequality and
assertion~(*), with probability at most~$1/2n$, more 
than~$\exp\(-\eps^{-1}\)|\cP_j(n,p)|$ 
elements in~$\cP_i(n,p)$ have  degree larger than~$(1+\eps)Np$
in~$\cP_{i,j}(n,p)$, and
the lemma follows.  \endproof

In the proof of Lemma~\ref{lem:width} we need the following auxiliary
result. 

\begin{lem} \label{lem:matching}
  Let~$0<c(n)=\cO(1)$ be given.  Define
  $p=n^{-c\sqrt{n}}(9c/\e)^{2c\sqrt{n}}$.  Let~$0<\eps\le1/n$ be
  given, and let~$\cQ$ be $(c,\eps,p,j)$-uniform for some~$j$
  with~$c\sqrt{n}\le|j|\le(\log n)\sqrt{n}$.  Define~$i=i(j)$ as
  in~{\rm (\ref{eq:defi})}.  Then there is a matching in $\cQ_{i,j}$
  that covers all but at most $4\eps|\cQ_j|$ elements from $\cQ_j$, as
  long as~$n$ is sufficiently large.
\end{lem}

\proofof Lemma~\ref{lem:matching}.  Remove all vertices of~$\cQ_{i,j}$
of degree larger than
$(1+\eps){n/2+|j|\choose\lfloor2c\sqrt{n}\rfloor}p$.  Call the
resulting set-system~$\cR_{i,j}$.  By~({\it a\/}), the number of edges
of~$\cQ_{i,j}$ incident to the vertices that have been removed may be
bounded from above, very crudely, by
\[
  2\exp(-\eps^{-1})|\cQ_j|{n\choose\lfloor2c\sqrt{n}\rfloor}
    \le2\exp(-\eps^{-1})|\cQ_j|n^{2c\sqrt{n}}   
    \le\eps|\cQ_j|p,
\]
provided $n$ is large enough. 

Using condition~({\it b\/}), we see that the number of
edges~$e(\cR_{i,j})$ in~$\cR_{i,j}$ is at least
\[ 
  \(1-\exp(-\eps^{-1})\)(1-\eps)|\cQ_j|
  {n/2+|j|\choose\lfloor2c\sqrt{n}\rfloor}p-\eps|\cQ_j|p
    \geq(1-2\eps)|\cQ_j|{n/2 + |j| \choose \lfloor 2c\sqrt{n}\rfloor}p. 
\]
Moreover, $\cR_{i,j}$ has maximum degree at most $\Delta(\cR_{i,j})\le
(1+\eps){n/2+|j|\choose\lfloor2c\sqrt{n}\rfloor}p$.  Since the
edge-set of the bipartite graph~$\cR_{i,j}$ may be partitioned
into~$\Delta(\cR_{i,j})$ matchings, the graph~$\cR_{i,j}$ contains a
matching covering at least
\[ 
  \frac{e(\cR_{i,j})}{\Delta(\cR_{i,j})} 
   \ge\frac{1-2\eps}{1+\eps}|\cQ_j|
   \ge(1-4\eps)|\cQ_j| 
\]
elements from~$\cQ_j$, provided~$n$ is large enough. 
\endproof

\proofof Lemma~\ref{lem:width}.  For each~$j$
with~$c\sqrt{n}\le|j|\le(\log n)\sqrt{n}$, fix a matching in
$\cQ_{i,j}$ that covers all but $\leq4\eps|\cQ_j|$ elements from
$\cQ_j$, as given by Lemma~\ref{lem:matching}.  Let~$\cR$ be the
spanning subgraph of~$\cQ$ having as edges the union of all these
matchings.  A component in the graph~$\cR$ corresponds to a chain
in~$\cQ$, when~$\cQ$ is considered as a poset.  Hence the width
of~$\cQ$ is at most the number of components of~$\cR$.

The graph~$\cR$ is a disjoint union of paths.  Therefore the number of
components of~$\cR$ is just the number of vertices in~$\cR$ minus the
number of edges in~$\cR$.  By properties~({\it i\/}), ({\it ii\/}),
and Lemma~\ref{lem:matching}, the number of components of~$\cR$ is,
therefore, almost surely at most
\begin{eqnarray*} 
  \lefteqn{\sum_{|j|\geq(\log n)\sqrt{n}}|\cQ_j|
   +\sum_{c\sqrt{n}\leq|j|<(\log n)\sqrt{n}}4\eps|\cQ_j|
   +\sum_{|j|<c\sqrt{n}}|\cQ_j|}\hspace{.5cm}&& \\
  &\le&
   \({2^n\over n}+4\(1+\cO\(1\over n\)\)\eps2^n
     +\(1+\cO\(1\over n\)\)\sum_{|j|<c\sqrt{n}}
         {n\choose\lfloor n/2\rfloor-j}\)p
\end{eqnarray*}
and the lemma follows as $\eps\le1/n$.
\endproof

\section{Concluding remarks}
\label{sec:conclude}
It would be interesting to investigate~$\alpha(\cP(n,p))$ for the
range of~$p$ in which~$\alpha(\cP(n,p))$ is comparable to
$$
  |\cP_0(n,p)|
    =\left|\cP(n,p)\cap{[n]\choose\lfloor n/2\rfloor}\right|.
$$
In particular, one may ask what the threshold functions for the
following properties are:
\begin{list}{(a)}{\itemsep-1mm}
\item[(1)] $\alpha(\cP(n,p))=|\cP_0(n,p)|$,
\item[(2)] $\alpha(\cP(n,p))\sim|\cP_0(n,p)|$.
\end{list}
Many similar questions remain open.  

\bibliographystyle{plain}
\begin{thebibliography}{3}

\bibitem{KKrOlength}
Y.~Kohayakawa, B.~Kreuter, and D.~Osthus.
\newblock The length of random subsets of Boolean lattices.
\newblock {\em In preparation}, 1998.

\bibitem{Krla}
B.~Kreuter.
\newblock Small sublattices in random subsets of Boolean lattices.
\newblock {\em Submitted}, 1997.

\bibitem{Re}
A.~R\'enyi.
\newblock On random subsets of a finite set.
\newblock {\em Mathematica {\rm(}Cluj{$\,$\rm)}}, 3 (26):355--362,
1961. 
%  [ ][1] 26 #1911 Rényi, A. On random subsets of a finite set. Mathematica
%  (Cluj) 3 1961 355--362. (Reviewer: P. Erdos) 60.10

\end{thebibliography}
\end{document}