%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% LaTeX2e file for 
%
% ``The Width of Random Subsets of Boolean Lattices''
% 
% by Y. Kohayakawa and B. Kreuter
%
% REVISED VERSION
%
% submitted : 11. Februar 1998
% sent to main office of JCTA : 6 March 1999
% version of 3 June 2002
% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[11pt]{article}
\usepackage{latexsym}
%\usepackage[colorlinks,backref]{hyperref} 
\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{fact} [lem] {Fact}
\newtheorem{NB}  [lem] {Remark}
\newtheorem{con} [lem] {Conjecture}

\def\eqref#1{{\rm(\ref{#1})}}
\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\cH{{\cal H}}
\def\cP{{\cal P}}
\def\cL{{\cal L}}
\def\cV{{\cal V}}\def\cK{{\cal K}}
\def\cR{{\cal R}}
\def\cS{{\cal S}}

\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 (proj.\ 026/95 and 089/99), a 
    CAPES--DAAD exchange programme.}}

\author{%\sc 
  Y.~Kohayakawa\thanks{Partially supported by MCT/CNPq through ProNEx
    Programme (Proc.\ CNPq 664107/1997--4), by CNPq (Proc.\ 300334/93--1,
    910064/99--7, and~468516/2000--0), and by FAPESP
    (Proc.\ 96/04505--2).}\\\small Instituto de Matem\'atica e Estat\'{\i}stica,
    Universidade de S\~ao Paulo\\\small Rua do Mat\~ao 1010, 05508--090~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{Introduction}
As is well known, a basic result in extremal set theory is a theorem of
Sperner, which determines the \textit{width}, that is, the maximum cardinality
of an antichain, in the poset~$\cP(n)=2^{[n]}$. The investigation of extensions
of this 74-year-old result has given rise to a surprisingly rich theory; the
reader unfamiliar with the more recent developments in this area is encouraged
to consult the monograph of Engel~\cite{engel97:_spern}.  In this note, we are
interested in the width of a poset naturally derived from~$\cP(n)=2^{[n]}$. 

Let~$0\leq p\leq1$ be given, and consider the \textit{random
  subposet}~$\cP(n,p)\subset\cP(n)$, whose elements are randomly chosen
from~$\cP(n)$, independently, with probability~$p$ each, and the order
relation is the naturally induced order.  Our main aim here is to investigate
the width of the random poset~$\cP(n,p)$.

For a good introduction to the theory of random posets, including results on
the width, we recommend a survey of Brightwell~\cite{brightwell93:_model}.  It
should be observed that, somewhat surprisingly, however, the model of random
posets that we are concerned with here has not been studied to any great
extent.  Indeed, we shall settle here a rather basic problem about the width
of~$\cP(n,p)$.  We shall observe that the width of~$\cP(n,p)$, measured
against the cardinality of~$\cP(n,p)$, varies from~$1$ to~$0$ as~$p$ grows
(this is an easy observation), and we shall identify in our main theorem the
parameterization of~$p$ that makes it transparent how this decay takes place
(see Theorem~\ref{thm:width} below).  Let us mention that our technique also
gives structural information about the largest antichains in~$\cP(n,p)$.

It may be of some interest to state a version of our results in terms of
counting, and in the language of hypergraphs.
Let~$\cH_{n,m}=\{H_1,\ldots,H_m\}$ be a collection of~$m$ subsets of~$[n]$.
Denote by~$\alpha(\cH_{n,m})$ the size of the largest \textit{Sperner family}
contained in~$\cH_{n,m}$.  That is, $\alpha(\cH_{n,m})$ is the largest
cardinality of a subcollection of~$\cH_{n,m}$ of mutually incomparable
elements.  Define~$b=b(n)$ so that
\begin{equation}
  \label{eq:b_def}
  m=m(n)=n^{-b\sqrt n}\,2^n.
\end{equation}
Theorem~\ref{thm:width} below implies that a typical~$\cH_{n,m}$ (that is,
almost all of them) are such that  
\begin{equation}
  \label{eq:1-statement}
  {1\over m}\alpha(\cH_{n,m})\to1\quad\hbox{if $b=b(n)\to\infty$ as
    $n\to\infty$} 
\end{equation}
and
\begin{equation}
  \label{eq:0-statement}
  {1\over m}\alpha(\cH_{n,m})\to0\quad\hbox{if $b=b(n)\to0$ as
    $n\to\infty$.}   
\end{equation}
Moreover, if~$b(n)\to b_0$ as~$n\to\infty$, where~$0<b_0<\infty$ is some
constant, then the ratio~$\alpha(\cH_{n,m})/m$ converges to a
constant~$c(b_0)>0$, which we explicitly identify. 

The random poset~$\cP(n,p)$ was probably first investigated by
R\'enyi~\cite{renyi61} who, answering a question of Erd\H{o}s, determined the
minimal asymptotic value of~$p=p(n)$ above for which the probability
that~$\cP(n,p)$ should itself be an antichain tends to~$0$.  The study
of~$\cP(n,p)$ remained dormant for many years, but, recently, motivated by the
explosive growth of the research in the theory of random graphs,
Kreuter~\cite{kreuter98:_small_boolean} investigated for $\cP(n,p)$ analogues
of some classical problems in random graphs.  In modern language, R\'enyi
established the threshold function for the emergence of the Boolean
lattice~$L=\cP(1)$ in~$\cP(n,p)$.  Kreuter extended this result by determining
the emergence threshold function for a large class of lattices~$L$.  The
interested reader is referred to~\cite{kreuter98:_small_boolean}, which may be
thought of as a modern sequel to R\'enyi's pioneering work~\cite{renyi61}.
For the background from the theory of random graphs, see
Bollob\'as~\cite{bollobas85:_random} and Janson, \L uczak, and
Ruci\'nski~\cite{janson00:_random_graph}.

Another parameter that is of interest in the study of a poset is its
\textit{height} or \textit{length}, \textit{i.e.}, the cardinality of a
longest chain.  For results concerning the length of~$\cP(n,p)$, the reader is
referred to Kohayakawa, Kreuter, and Osthus~\cite{kohayakawa98:_boolean}.  We
mention that Bollob\'as and Brightwell~\cite{bollobas91:_box,bollobas92} have
investigated the height of random $d$-dimensional partial orders and, more
generally, of random partial orders defined in terms of `box spaces' (certain
partially ordered probability spaces).  The study of the height of random
$2$-dimensional partial orders goes back to Ulam~\cite{ulam61:_monte_carlo}
(see~\cite{bollobas92,brightwell93:_model} for further references).  The
flavour of the arguments in~\cite{kohayakawa98:_boolean} are, however, closer
to the ones in Fill and Pemantle~\cite{fill93:_percol_richar} and Bollob\'as,
Kohayakawa and \L uczak~\cite{bollobas94}.

\subsection*{Further results}
\label{sec:osthus}
Soon after the results in this note were obtained,
Osthus~\cite{osthus98:_maxim_boolean} discovered a powerful method of proof
inspired in Lubell's beautiful proof~\cite{lubell66} of Sperner's theorem.
Indeed, making use of a technical lemma~\cite[Lemma~7]{kohayakawa98:_boolean},
Osthus showed that Lubell's method can be essentially carried over
to~$\cP(n,p)$, for a wide range of~$p=p(n)$.  Write~$p=p(n)=(r/n)^r$.
Osthus~\cite{osthus98:_maxim_boolean} determined~$\alpha(\cP(n,p))$ up to a
multiplicative factor of~$1+o(1)$ if~$r\to\infty$ as~$n\to\infty$.  Moreover,
he proved that, with probability tending to~$1$ as~$n\to\infty$, we have
$$
\alpha(\cP(n,p))=(1+o(1))p{n\choose\lfloor n/2\rfloor}
$$
when~$p=\omega n^{-1}\log n$, where~$\omega=\omega(n)$ is any function
with~$\omega\to\infty$ as~$n\to\infty$.  (It is an open problem whether the
$\log n$ factor is required.)

The results in this note cover a narrower range of~$p=p(n)$, namely, $r$~above
has to be of order~$\sqrt n$; note that, however, this is an interesting
period of the evolution of~$\cP(n,p)$, as show~\eqref{eq:b_def},
\eqref{eq:1-statement}, and~\eqref{eq:0-statement}.  Our proof follows the
`chain decomposition method', based on matchings, and is self-contained.  For
a discussion on these classical proofs of Sperner's theorem, see,
\textit{e.g.}, \cite{anderson87:_combin} and~\cite{bollobas86:_combin}.

\section{Statements of the main results}
\label{sec:statement}

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 what follows,
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}

Using standard estimates, we may deduce the following numerical result from
Theorem~\ref{thm:width}.

\begin{cor}
  \label{cor:small_epsilon}
  There is an absolute constant~$\epsilon_0>0$ for which the following
  assertion holds.  For any fixed~$0<\epsilon<\epsilon_0$, we have that
  $$
  \lim_{n\to\infty}\P\(\left|{\alpha(\cP(n,p))\over|\cP(n,p)|}
    -\epsilon\sqrt{8\over\pi}\right|\leq3\epsilon^2\)=1.
  $$
\end{cor}

We shall in fact prove the the following structural result.

\begin{thm}
  \label{thm:structure}
  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}

The proofs of Theorems~\ref{thm:width} and~\ref{thm:structure}, which are
quite simple and are self-contained, are given in
Section~\ref{sec:lemmas_and_pfs}.  Since we would like to reach these proofs
as soon as possible, our results are presented in a somewhat indirect order.
We introduce the main concepts that we shall need and state the three
technical lemmas that are required in the proofs of Theorems~\ref{thm:width}
and~\ref{thm:structure} in Section~\ref{sec:lemmas_and_pfs}, and immediately
give the half-page proof of Theorems~\ref{thm:width} and~\ref{thm:structure}.
The remainder of this note is devoted to the proofs of the three technical
lemmas.

Our logarithms are natural logarithms.
\section{Proofs}

\subsection{Preliminaries}
\label{sec:prelims}

%\subsection{Proof of Theorem~\ref{thm:width}}
%\label{sec:proof_thm_width}
In this section, 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{equation} 
  {n\choose\frac{n}{2}-k,\frac{n}{2}-\ell,k+\ell}
    ={n-k-\ell\choose\frac{n}{2}-k}{n\choose k+\ell}
    \asymp\frac{2^{n}}{\sqrt{n(k+\ell)}}
             \(\frac{\e n}{2(k+\ell)}\)^{k+\ell}. \label{eq:nchooseij}
\end{equation}
% \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}
(see, \textit{e.g.}, \cite[Corollary~2.3]{janson00:_random_graph}).  Routine
calculations using the Chernoff bound give the following simple estimate
on~$|\cP_i(n,p)|$.

\begin{fact}
  \label{fact:*}
  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
  $$
  |\cP_i(n,p)|
  =\(1+\cO\(1\over n\)\){n\choose\lfloor n/2\rfloor-i}p.
  $$
\end{fact}

\subsection{Main lemmas and the proofs of Theorems~\ref{thm:width}
  and~\ref{thm:structure}} 
\label{sec:lemmas_and_pfs}
We shall now introduce some key concepts and three lemmas that will allow us
to prove Theorems~\ref{thm:width} and~\ref{thm:structure}.  Since the lemmas
are somewhat technical, their proofs are postponed to the
Section~\ref{sec:proofs_of_lemmas}.

Let 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)$ will be 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 Theorems~\ref{thm:width}
and~\ref{thm:structure}. 

\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}

We now deduce Theorems~\ref{thm:width} and~\ref{thm:structure} from
Lemmas~\ref{lem:lowerbd}, \ref{lem:pnpunif}, and~\ref{lem:width}.

\proofof Theorems~\ref{thm:width} and~\ref{thm:structure}.  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~$\cS$ of~$\cP(n,p)$.  By
Fact~\ref{fact:*} and Lemma~\ref{lem:lowerbd} 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\nonumber\\ 
   &\sim&(\Phi(2b)-\Phi(-2b))2^np.\label{eq:lwbd}
\end{eqnarray}
This establishes the lower bound in Theorem~\ref{thm:width}.  We now observe
the following: \textsl{if we now prove that~\eqref{eq:lwbd} is also an
  asymptotic an upper bound for the width of~$\cP(n,p)$, then the family~$\cS$
  proves Theorem~\ref{thm:structure}, as~$\cS$ is as described in the
  statement of that theorem}.  Let us therefore prove that~\eqref{eq:lwbd} is
indeed an upper bound for the width of~$\cP(n,p)$.  We 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 hence~\eqref{eq:lwbd} is an upper bound for the width of~$\cP(n,p)$, as
required. 
\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}) and the comment immediately
after that estimate regarding the multinomial coefficient on the left-hand
side of~\eqref{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 \\
             &&\qquad\qquad\qquad\qquad\qquad
             =\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}.  Fact~\ref{fact:*} 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. 

In what follows, 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 Fact~\ref{fact:*}, 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
Fact~\ref{fact:*}, 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}.  
\proof 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{1.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)|
%     =\max
%       \left\{\left|\cP(n,p)\cap{[n]\choose k}\right|\colon\;
%       k=\lfloor n/2\rfloor,\,\lceil n/2\rceil\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}
% For results in this direction, see Osthus~\cite{osthus98:_maxim_boolean} (the
% powerful method in~\cite{osthus98:_maxim_boolean} makes use of some technical
% results from~\cite{kohayakawa98:_boolean}).  Many similar questions remain
% open.

\section{Acknowledgements}
\label{sec:acknow}

We are grateful to an anonymous referee for his or her comments.  We are also
grateful to Professor Bruce Rothschild for his generous handling of this note.

%\bibliographystyle{amsplain}
%\bibliography{refs}

\providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace}
\begin{thebibliography}{10}

\bibitem{anderson87:_combin}
Ian Anderson, \emph{Combinatorics of finite sets}, The Clarendon Press Oxford
  University Press, New York, 1987.

\bibitem{bollobas85:_random}
B{\'e}la Bollob{\'a}s, \emph{Random graphs}, Academic Press Inc. [Harcourt
  Brace Jovanovich Publishers], London, 1985.

\bibitem{bollobas86:_combin}
\bysame, \emph{Combinatorics}, Cambridge University Press, Cambridge, 1986, Set
  systems, hypergraphs, families of vectors and combinatorial probability.

\bibitem{bollobas91:_box}
B{\'e}la Bollob{\'a}s and Graham Brightwell, \emph{Box-spaces and random
  partial orders}, Trans. Amer. Math. Soc. \textbf{324} (1991), no.~1, 59--72.

\bibitem{bollobas92}
\bysame, \emph{The height of a random partial order: concentration of measure},
  Ann. Appl. Probab. \textbf{2} (1992), no.~4, 1009--1018.

\bibitem{bollobas94}
B{\'e}la Bollob{\'a}s, Yoshiharu Kohayakawa, and Tomasz {\L}uczak, \emph{On the
  diameter and radius of random subgraphs of the cube}, Random Structures
  Algorithms \textbf{5} (1994), no.~5, 627--648.

\bibitem{brightwell93:_model}
Graham Brightwell, \emph{Models of random partial orders}, Surveys in
  combinatorics, 1993 (Keele), Cambridge Univ. Press, Cambridge, 1993,
  pp.~53--83.

\bibitem{engel97:_spern}
Konrad Engel, \emph{Sperner theory}, Cambridge University Press, Cambridge,
  1997.

\bibitem{fill93:_percol_richar}
James~Allen Fill and Robin Pemantle, \emph{Percolation, first-passage
  percolation and covering times for {R}ichardson's model on the $n$-cube},
  Ann. Appl. Probab. \textbf{3} (1993), no.~2, 593--629.

\bibitem{janson00:_random_graph}
Svante Janson, Tomasz {\L}uczak, and Andrzej Ruci{\'n}ski, \emph{Random
  graphs}, Wiley-Interscience, New York, 2000.

\bibitem{kohayakawa98:_boolean}
Y.~Kohayakawa, B.~Kreuter, and D.~Osthus, \emph{The length of random subsets of
  {B}oolean lattices}, Random Structures Algorithms \textbf{16} (2000), no.~2,
  177--194.

\bibitem{kreuter98:_small_boolean}
B.~Kreuter, \emph{Small sublattices in random subsets of {B}oolean lattices},
  Random Structures Algorithms \textbf{13} (1998), no.~3-4, 383--407.

\bibitem{lubell66}
D.~Lubell, \emph{A short proof of {S}perner's lemma}, J. Combinatorial Theory
  \textbf{1} (1966), 299.

\bibitem{osthus98:_maxim_boolean}
Deryk Osthus, \emph{Maximum antichains in random subsets of a finite set}, J.
  Combin. Theory Ser. A \textbf{90} (2000), no.~2, 336--346.

\bibitem{renyi61}
A.~R{\'e}nyi, \emph{On random subsets of a finite set}, Mathematica (Cluj)
  \textbf{3} (1961), 355--362.

\bibitem{ulam61:_monte_carlo}
Stanislaw~M. Ulam, \emph{Monte {C}arlo calculations in problems of mathematical
  physics}, Modern mathematics for the engineer: Second series, McGraw-Hill,
  New York, 1961, pp.~261--281.

\end{thebibliography}

\end{document}