%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%     On Richardson's Model on the Hypercube
%
%                       by  
%
%         B. Bollob\'as and Y. Kohayakawa
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% style
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\magnification=\magstephalf
\newcount\spcounter
\def\setupspacing{\afterassignment\setupsp\spcounter}
\def\setupsp{\ifcase\spcounter
\baselineskip=\normalbaselineskip
\smallskipamount=\smallskipamount
\medskipamount=\medskipamount
\bigskipamount=\bigskipamount
\or
\baselineskip=1.38\normalbaselineskip
\smallskipamount=1.38\smallskipamount
\medskipamount=1.38\medskipamount
\bigskipamount=1.38\bigskipamount
\or
\baselineskip=1.53\normalbaselineskip     
\smallskipamount=1.53\smallskipamount     
\medskipamount=1.53\medskipamount         
\bigskipamount=1.53\bigskipamount         
\or                                       
\baselineskip=1.67\normalbaselineskip     
\smallskipamount=1.67\smallskipamount     
\medskipamount=1.67\medskipamount         
\bigskipamount=1.67\bigskipamount
\fi}
\setupspacing0
\input mssymb
\font\ninerm=cmr9   \font\eightrm=cmr8       \font\sixrm=cmr6
\font\ninei=cmmi9   \font\eighti=cmmi8       \font\sixi=cmmi6
\font\ninesy=cmsy9  \font\eightsy=cmsy8      \font\sixsy=cmsy6
\font\ninebf=cmbx9   \font\eightbf=cmbx8     \font\sixbf=cmbx6
\font\ninett=cmtt9   \font\eighttt=cmtt8
\font\nineit=cmti9   \font\eightit=cmti8
\font\ninesl=cmsl9   \font\eightsl=cmsl8
\font\ninemsx=msxm9  \font\eightmsx=msxm8 \font\sixmsx=msxm6
\font\ninemsy=msym9  \font\eightmsy=msym8 \font\sixmsy=msym6
\let\deffont=\it
%\font\deffont=cmssi10
% the following \ninepoint and \eightpoint come from the TeXbook
\def\ninepoint{\def\rm{\fam0\ninerm}%
\textfont0=\ninerm \scriptfont0=\sixrm \scriptscriptfont0=\fiverm
\textfont1=\ninei  \scriptfont1=\sixi  \scriptscriptfont1=\fivei
\textfont2=\ninesy \scriptfont2=\sixsy \scriptscriptfont2=\fivesy
\textfont3=\tenex  \scriptfont3=\tenex  \scriptscriptfont3=\tenex
\textfont\itfam=\nineit \def\it{\fam\itfam\nineit}%
\textfont\slfam=\ninesl \def\sl{\fam\slfam\ninesl}%
\textfont\ttfam=\ninett \def\tt{\fam\ttfam\ninett}%
\textfont\bffam=\ninebf \scriptfont\bffam=\sixbf
 \scriptscriptfont\bffam=\fivebf \def\bf{\fam\bffam\ninebf}%
\textfont\msxfam=\ninemsx  \scriptfont\msxfam=\sixmsx
  \scriptscriptfont\msxfam=\fivemsx
\textfont\msyfam=\ninemsy  \scriptfont\msyfam=\sixmsy
  \scriptscriptfont\msyfam=\fivemsy
%\tt\ttglue=.5em plus.25em minus.15em
\normalbaselineskip=11.7pt
\setbox\strutbox=\hbox{\vrule height8pt depth3pt width0pt}%
\let\sc=\sevenrm%\let\big=\ninebig
\normalbaselines\rm}
\def\eightpoint{\def\rm{\fam0\eightrm}%
\textfont0=\eightrm \scriptfont0=\sixrm \scriptscriptfont0=\fiverm
\textfont1=\eighti  \scriptfont1=\sixi  \scriptscriptfont1=\fivei
\textfont2=\eightsy \scriptfont2=\sixsy \scriptscriptfont2=\fivesy
\textfont3=\tenex  \scriptfont3=\tenex  \scriptscriptfont3=\tenex
\textfont\itfam=\eightit \def\it{\fam\itfam\eightit}%
\textfont\slfam=\eightsl \def\sl{\fam\slfam\eightsl}%
\textfont\ttfam=\eighttt \def\tt{\fam\ttfam\eighttt}%
\textfont\bffam=\eightbf \scriptfont\bffam=\sixbf
 \scriptscriptfont\bffam=\fivebf \def\bf{\fam\bffam\eightbf}%
\textfont\msxfam=\eightmsx  \scriptfont\msxfam=\sixmsx
  \scriptscriptfont\msxfam=\fivemsx
\textfont\msyfam=\eightmsy  \scriptfont\msyfam=\sixmsy
  \scriptscriptfont\msyfam=\fivemsy
%\tt\ttglue=.5em plus.25em minus.15em
\normalbaselineskip=10pt
\setbox\strutbox=\hbox{\vrule height7pt depth2pt width0pt}%
\let\sc=\sixrm%\let\big=\eightbig
\normalbaselines\rm}
\let\centreline=\centerline
\def\enddiscard{}
\long\def\discard#1\enddiscard{}
\def\date{\number\day\space
  \ifcase\month\or January\or February\or March\or April\or May\or June
               \or July\or August\or September\or November\or December\fi,
  \number\year}
%
% further maths macros
%
\def\N{{\Bbb N}}
\def\Z{{\Bbb Z}}
\def\R{{\Bbb R}}
\def\E{{\Bbb E}}
\def\P{{\Bbb P}}
\def\e{{\rm e}}
\def\symmdiff{\bigtriangleup}
\def\im{\mathop{\rm im}\nolimits}
\def\({\left(}
\def\){\right)}
\def\[{\left[}
\def\]{\right]}
\def\<{\left\langle}
\def\>{\right\rangle}
\def\lbr{\left\{}
\def\rbr{\right\}}
\def\setof#1{\left\{#1\right\}}
\def\sizeof#1{\left|#1\right|}
\def\comp{^{\rm c}}
\def\superset{\supset}
%
\newcount\eqnocounter
\eqnocounter=0
\def\slabel#1{\global\advance\eqnocounter by1%
  \global\expandafter\edef\csname eqno#1\endcsname{(\number\eqnocounter)}%
  \eqno({\number\eqnocounter})}
\def\alabel#1{\global\advance\eqnocounter by1%
  \global\expandafter\edef\csname eqno#1\endcsname{(\number\eqnocounter)}%
  ({\number\eqnocounter})}
%
%\voffset=.5truein
\voffset=.8truein
\hoffset=.63truein
\vsize=7.1truein
\hsize=5truein
\font\titlefont=cmbx12 at13pt
\def\authorfont{\rm}
\def\addressfont{\rm}
\def\title#1{\null\vglue3truecm{\parindent=0pt\titlefont#1}}
\def\titlecont#1{\vskip2\jot{\parindent=0pt\titlefont#1}}
\def\author#1{{\authorfont\vglue1truecm\noindent#1}}
\def\Fapesp{${}^*$\footnote\null{{\eightpoint${^*}$ Research supported by
                                    FAPESP, Brazil, Proc.\ MAP 86/0904--8}}}
\def\NSF{\footnote{${}^{\hbox{\dag}}$}{{\eightpoint Partially
                             supported by NSF grant DMS-8806097}}}
\def\endaddress{\par\endgroup}
\def\address#1\endaddress{\medskip\begingroup
               \eightpoint\baselineskip=9pt
               \noindent\raggedright\addressfont#1\endaddress}
\newif\ifemailwanted
\emailwantedfalse
\def\DPMMS{Department of Pure Mathematics
           and Mathematical Statistics, \hfill\break
           University of Cambridge, 16 Mill Lane, Cambridge
           CB2~1SB, England\ifemailwanted\hfill\break\vskip1\jot
           \noindent{\tt e-mail: yk101@phx.cam.ac.uk}\hfill\fi}
\def\LSU{\noindent Department of Mathematics, \hfill\break
         Louisiana State University, Baton Rouge, LA 70803, USA}
\def\IMEUSP{\noindent Instituto de Matem\'atica e Estat\'\i stica, Universidade
            de S\~ao Paulo, \hfill\break
            Caixa Postal~20570, 01452--990~S\~ao Paulo, SP, Brazil}
\def\draft{\vglue1truecm\noindent{\eightpoint\rm Draft of \date}}
\def\endabstract{\par\endgroup}
\def\abstract{\vglue1truecm\begingroup
  \ninepoint\noindent{\bf Abstract.\enspace}\ignorespaces}
\def\endfinalnotes{\par\endgroup}
\def\finalnotes#1.{\bigbreak\begingroup
  \eightpoint\noindent{\bf #1.\enspace}\ignorespaces}
\outer\def\proclaim #1. {%\message{#1 }
  \medbreak
  \noindent{\bf#1.\enspace}\bgroup\sl\ignorespaces}
\def\endproclaim{\par\egroup\ifdim\lastskip<\medskipamount\removelastskip
                                \penalty1000\medskip\fi}
\outer\def\endproclaimsquare{{\unskip\nobreak\hfil\penalty50
         \hskip2em\hbox{}\nobreak\hfil\square
         \parfillskip0pt\finalhyphendemerits=0\par}% TeXbook, p 106.
 \egroup\ifdim\lastskip<\bigskipamount\removelastskip\penalty-10\bigskip\fi}
\def\endclaim{\egroup\par\ifdim\lastskip<\smallskipamount
                \removelastskip\penalty20\smallskip\fi}
\long\def\claim{\smallbreak
\noindent  %BB's preference, without \noindent
{\it Claim.\enspace}\ignorespaces\bgroup\sl}
\def\endassertion{\egroup\par\ifdim\lastskip<\smallskipamount
                \removelastskip\penalty20\smallskip\fi}
\def\endassertionsquare{{\unskip\nobreak\hfil\penalty50
         \hskip2em\hbox{}\nobreak\hfil\square
         \parfillskip0pt\finalhyphendemerits=0\par}
 \egroup\par\ifdim\lastskip<\smallskipamount\removelastskip\penalty20\smallskip\fi}
\long\def\assertion(#1){\smallbreak
\noindent %BB's preference, without \noindent
{\rm(}#1{\rm)}\enspace\ignorespaces\bgroup\sl}
\def\endcase{\par\ifdim\lastskip<\smallskipamount
                \removelastskip\penalty3000\smallskip\fi}
\def\case#1.{\smallbreak
\noindent % BB's preference
{\sl Case\/} #1.\enspace\ignorespaces}
\def\casenodot#1 {\smallbreak
\noindent % BB's preference
{\sl Case\/} #1\enspace\ignorespaces}
\def\endcasebody{\par\ifdim\lastskip<\smallskipamount
                \removelastskip\penalty-20\smallskip\fi}
\outer\def\endcasebodysquare{{\unskip\nobreak\hfil\penalty50
         \hskip2em\hbox{}\nobreak\hfil\square
         \parfillskip0pt\finalhyphendemerits=0\par}% TeXbook, p 106.
    {\ifdim\lastskip<\bigskipamount\removelastskip\penalty-10\bigskip\fi}}
\def\casebody{\noindent\ignorespaces}
\let\proofofassertion=\casebody
\let\endproofofassertion=\endcasebody
\let\endproofofassertionsquare=\endcasebodysquare
\def\square{\ifmmode\sqr\else{$\sqr$}\fi}
\def\sqr{\vcenter{
         \hrule height.1mm
         \hbox{\vrule width.1mm height2.2mm\kern2.18mm\vrule width.1mm}
         \hrule height.1mm}}                  % This is a slimmer sqr.
\outer\def\endproofnoskip{{\unskip\nobreak\hfil\penalty50
         \hskip2em\hbox{}\nobreak\hfil\square
         \parfillskip0pt\finalhyphendemerits=0\par}}% TeXbook, p 106.
\outer\def\endproofsmallskip{{\unskip\nobreak\hfil\penalty50
         \hskip2em\hbox{}\nobreak\hfil\square
         \parfillskip0pt\finalhyphendemerits=0\par}% TeXbook, p 106.
    {\ifdim\lastskip<\smallskipamount\removelastskip\penalty-10\smallskip\fi}}
\outer\def\endproof{{\unskip\nobreak\hfil\penalty50
         \hskip2em\hbox{}\nobreak\hfil\square
         \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}
\outer\def\proofofnodot#1 {%
   \ifdim\lastskip<\medskipamount\removelastskip\penalty60\medskip\fi
   \noindent{\it Proof of\/} {#1}\enspace\ignorespaces}
\def\beginsection#1\par{\vskip0pt plus.08\vsize\penalty-250
    \vskip0pt plus-.08\vsize\bigskip\vskip\parskip
    %\message{#1}
    \leftline{\bf#1}\nobreak\smallskip\noindent}
\def\ititem(#1){\item{({\it#1})}}
\def\ititemnohangindent(#1){\par\textindent{({\it#1\/})}}
\def\itemnohang#1{\par\textindent{#1}}
\let\TeXiff=\iff
\def\iff{\ifmmode\TeXiff\else if{}f\fi}
%
% Macros for references
%
\newif\ifPortuguese
\newif\iffirstgo
\Portuguesefalse
\def\scanreferences{\firstgotrue\refno=0\beginreferences%
                       \input refs\endreferences}%
\def\shipoutreferences{\firstgofalse\refno=0
                       \beginreferences\input refs\endreferences}
\def\endreferences{\par\endgroup}
\outer\def\beginreferences
   {\begingroup\iffirstgo\else\pretolerance=1000\tolerance=3000
    %\raggedright
    \frenchspacing
    \vskip0pt plus.3\vsize\penalty-150\vskip0pt plus-.3\vsize
    \bigskip\vskip\parskip%\message{References}
    \ifPortuguese\leftline{\bf Refer\^encias}%
             \else\leftline{\bf References}\fi
    \nobreak\smallskip\ninepoint\fi\obeylines}
% Journals
\def\BLMS{Bull. London Math. Soc.}
\def\JAMS{J. Amer. Math. Soc.}
\def\JLMS{J. London Math. Soc.}
\def\PLMS{Proc. London Math. Soc.}
\def\JCT{J. Combinatorial Theory}
\def\JCTA{J. Combinatorial Theory~(A)}
\def\JCTB{J. Combinatorial Theory~(B)}
\def\JGT{J. Graph Theory}
\def\Comb{Combinatorica}
\def\AMASH{Acta Math. Acad. Sci. Hungar.}
\def\SSMH{Studia Sci. Math. Hung.}
\def\EJC{Europ. J. Combinatorics}
\def\GC{Graphs and Combinatorics}
\def\IJM{Israel J. Math.}
\def\DM{Discrete Math.}
\def\ADM{Ann. Discrete Math.}
\def\TAMS{Trans. Amer. Math. Soc.}
\def\PAMS{Proc. Amer. Math. Soc.}
\def\RSA{Random Structures and Algorithms}
\def\PMH{Periodica Math. Hungar.}
\def\PCPS{Proc. Cambridge Phil. Soc.}
\def\MPCPS{Math. Proc. Cambridge Phil. Soc.}
% Authors
\def\Aj{Ajtai, M.}
\def\Al{Alon, N.}
\def\Be{Beck, J.}
\def\BB{Bollob\'as, B.}
\def\Chung{Chung, F.R.K.}
\def\Er{Erd\H os, P.}
\def\Fr{Frankl, P.}
\def\Fu{F\"uredi, Z.}
\def\Gra{Graham, R.L.}
\def\Ka{Katona, G.O.H.}
\def\Kl{Kleitman, D.J.}
\def\Ko{Koml\'os, J.}
\def\Lo{Lov\'asz, L.}
\def\Ne{Ne\v set\v ril, J.}
\def\Po{P\'osa, L.}
\def\Ro{R\"odl, V.}
\def\Sey{Seymour, P.}
\def\Sh{Shearer, J.B.}
\def\Si{Simonovits, M.}
\def\So{S\'os, V.T.}
\def\Sp{Spencer, J.}
\def\Sz{Szemer\'edi, E.}
\def\Tur{Tur\'an, P.}
\def\Tutte{Tutte, W.T.}
\def\Tu{Tuza, Zs.}
%
\newcount\refno
\def\vol{}
\begingroup
\obeylines
\long\global\def\paper[#1] #2
#3
#4\vol#5
#6, #7
{\global\advance\refno by1%
 \iffirstgo\global\expandafter\edef\csname ref#1\endcsname{[\number\refno]}%
           \global\expandafter\edef\csname refnb#1\endcsname{\number\refno}%  
 \else\smallskip\item{[\number\refno]} %
#2, #3, {\it#4}~{\bf#5} (#7), \hbox{#6}.\fi}%
\global\def\proceedings[#1] #2
#3
#4
#5
#6
#7
{\global\advance\refno by1%
\iffirstgo\global\expandafter\edef\csname ref#1\endcsname{[\number\refno]}%
          \global\expandafter\edef\csname refnb#1\endcsname{\number\refno}%          
\else\smallskip\item{[\number\refno]} #2, #3, {\it in} {``#4''}, #5 (#6 eds), %
\hbox{#7}.\fi}%
\global\def\book[#1] #2
#3
#4
{\global\advance\refno by1%
\iffirstgo\global\expandafter\edef\csname ref#1\endcsname{[\number\refno]}%
          \global\expandafter\edef\csname refnb#1\endcsname{\number\refno}%  
\else\smallskip\item{[\number\refno]} #2, {\it #3\/}, #4.\fi}%
\global\def\preprint[#1] #2
#3
#4
{\global\advance\refno by1%
\iffirstgo\global\expandafter\edef\csname ref#1\endcsname{[\number\refno]}%
          \global\expandafter\edef\csname refnb#1\endcsname{\number\refno}%  
\else\smallskip\item{[\number\refno]} #2, #3, #4.\fi}%
\global\def\privatecomm[#1] #2
{\global\advance \refno by1%
\iffirstgo\global\expandafter\edef\csname ref#1\endcsname{[\number\refno]}%
          \global\expandafter\edef\csname refnb#1\endcsname{\number\refno}%  
\else\smallskip\item{[\number\refno]} #2, private communication.\fi}%
\global\def\unpublished[#1] #2
{\global\advance \refno by1%
\iffirstgo\global\expandafter\edef\csname ref#1\endcsname{[\number\refno]}%
          \global\expandafter\edef\csname refnb#1\endcsname{\number\refno}%  
\else\smallskip\item{[\number\refno]} #2, unpublished.\fi}%
\global\def\dammit[#1] #2
#3
{\global\advance \refno by1%
\iffirstgo\global\expandafter\edef\csname ref#1\endcsname{[\number\refno]}%
          \global\expandafter\edef\csname refnb#1\endcsname{\number\refno}%  
\else\smallskip\item{[\number\refno]} #2, #3.\fi}%
\endgroup
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% statems
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newif\ifchapters
\chapterstrue
\newcount\chapterno\chapterno=0
\newcount\statemno\statemno=1
\def\yeschapters{\def\statementlabel{%\number\chapterno.
                                      \number\statemno}
              \def\newchapter{\statemno=1\advance\chapterno by1}}
\def\nochapters{\def\statementlabel{\number\statemno}
                \def\newchapter{\relax}}
\ifchapters\yeschapters\else\nochapters\fi
\def\newstatemno{\advance\statemno by1}
\edef\lemmaA
{\statementlabel}\newstatemno
\edef\lemmaB
{\statementlabel}\newstatemno
\edef\lemmaC
{\statementlabel}\newstatemno
\edef\lemmaD
{\statementlabel}\newstatemno
\edef\MainThm
{\statementlabel}\newstatemno
\edef\corollary
{\statementlabel}\newstatemno
\edef\conjA
{\statementlabel}\newstatemno
\edef\conjB
{\statementlabel}\newstatemno
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% macros
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\let\epsilon=\varepsilon
\def\:{\colon}
\def\T{{\cal T}}
\def\G{{\cal G}}
\def\cP{{\cal P}}
\def\Bi{\mathop{\rm Bi}\nolimits}
\def\diam{\mathop{\rm diam}\nolimits}
\def\F{{\cal F}}
\def\GammaQn{\Gamma_{Q^n}}
\def\GammaH#1{\Gamma_{H_{#1}}}
\def\dQn{d_{Q^n}}
%\def\dim{\mathop{\rm dim}\nolimits}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% scanreferences
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\firstgotrue\refno=0\beginreferences
\book[BBGTM] \BB
            Graph Theory---An Introductory Course
            Springer--Verlag, New York~1979, ${\it viii}+180$pp
\book[BBg]  \BB
            Combinatorics
            Cambridge University Press, Cambridge 1986, ${\it xii}+177$pp
\dammit[BKLdiam] \BB, Kohayakawa, Y., \L uczak, T.
            On the diameter and radius of random subgraphs of the %
            cube, {\it\RSA\/}, to appear
\dammit[BKLconn] \BB, Kohayakawa, Y., \L uczak, T.
            Connectivity properties of random subgraphs of the cube, %
            {\it\RSA\/}, to appear
\paper[FP] Fill, J.A., Pemantle, R.
            Percolation, first-passage percolation, and covering times %
            for Richardson's model on the $n$-cube
            The Annals of Applied Probability\vol3
            593--629, 1993
\endreferences
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% fstpg
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{On Richardson's Model on the Hypercube}
\author{B.~Bollob\'as${}^{1,\,2}$\footnote*{{\eightpoint Part of this
      work was done while this author was visiting the University of
      S\~ao Paulo, supported by FAPESP under grant~92/3169--8.}} and
  Y.~Kohayakawa${}^3$\footnote{\dag}{{\eightpoint Research partially
      supported by FAPESP under grant~93/0603--1 and by CNPq under
      grant~300334/93--1.}}} \address ${}^1$\DPMMS\medskip\noindent
${}^2$\LSU\medskip\noindent ${}^3$\IMEUSP
\endaddress
\abstract The $n$-cube~$Q^n$ is the graph on the subsets
of~$\{1,\ldots,n\}$ where two such vertices are adjacent if and only
if their symmetric difference is a singleton. Fill and
Pemantle~{\refFP} started the study of several percolation processes
on~$Q^n$ and obtained many asymptotic results for~$n\to\infty$. As an
application of these results, they investigated the contact process
with no recoveries in~$Q^n$, also known as Richardson's model for the
spread of a disease.  They obtained that, in this model, the cover
time~$T_n$ of~$Q^n$ starting from a single infected vertex is bounded
in probability: they proved that, with probability tending to~$1$
as~$n\to\infty$, one
has~$(1/2)\log(2+\surd5)+\log2+o(1)=1.414\ldots+o(1)\leq
T_n\leq4\log(4+2\surd3)+6+o(1)=14.040\ldots+o(1)$.  In this note we
substantially improve this upper bound by showing that one in fact
has~$T_n\leq 1+\log2+o(1)=1.693\ldots+o(1)$ in probability.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%lb=1.4149649, ubs=1.6931472 and 14.04042
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\endabstract
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% intro
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\beginsection \S0. Introduction

The $n$-dimensional cube~$Q^n$ is the graph whose vertices are the
subsets of~$[n]=\{1,\ldots,n\}$ where two such vertices are adjacent if
and only if their symmetric difference is a singleton. Here we are
interested in a stochastic process on~$Q^n$, known as Richardson's model
for the spread of a disease. In this model, one vertex of~$Q^n$ is at
first {\it infected\/} and the disease evolves by transmission of the
infection according to {i.i.d.}~Poisson processes associated to the edges
of~$Q^n$.  Every time our Poisson clock associated to an edge~$xy$ goes
off, if one of~$x$ or~$y$ is infected at that time the other vertex
becomes infected. The natural questions concerning this model regard the
manner in which the disease spreads, and in particular the time it takes
for all the vertices of~$Q^n$ to become infected. The latter question has
been recently studied by Fill and Pemantle~{\refFP}, who proved that this
{\deffont covering time\/} is bounded in probability. Our aim in this
note is to give an improved upper bound for this covering time.

One may study Richardson's model on~$Q^n$ by studying first-passage
percolation on this graph where the passage times on the edges are {i.i.d.}
exponential random variables. In fact, we shall study Richardson's model only
looking at first-passage percolation.  Let~$W=(W_e)_{e\in E(Q^n)}$ be a family
of independent exponential random variables each with mean~$1$.  If~$x$
and~$y$ are two vertices of~$Q^n$, we write~$d(x,y)=\dQn(x,y)$ for the
distance between~$x$ and~$y$ in~$Q^n$, and we set
$$
d_W(x,y)=\min_P\{\ell(P,W)\:P\hbox{ an $x$---$y$ path in }Q^n\},
$$
where~$\ell(P,W)=\sum_{e\in E(P)}W_e$ is the {\deffont$W$-length\/} of the
path~$P$. The result in~{\refFP} concerning Richardson's model on~$Q^n$ is
that, for a fixed~$x_0\in Q^n$, with probability~$1-o(1)$ as~$n\to\infty$, we
have~$(1/2)\log(2+\surd5)+\log2+o(1)=1.414\ldots+o(1)
\leq\max_{y\in
  Q^n}d_W(x_0,y)\leq4\log(4+2\surd3)+6+o(1)=14.040\ldots+o(1)$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%lb=1.4149649, ubs=1.6931472 and 14.04042
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
A corollary of our main result, Theorem~{\MainThm}, is that this upper
bound can be improved to~$1+\log2+o(1)=1.693\ldots+o(1)$.

Indeed, we shall show that with probability~$1-o(1)$ as~$n\to\infty$, ({\it
i\/})~for all fixed~$x_0\in Q^n$ we have that~$\max_{y\in
Q^n}d_W(x_0,y)\leq1+\log2+o(1)$, and ({\it
ii\/})~$\diam(Q^n,W)=\max\{d_W(x,y)\:x,\,y\in Q^n\}\leq1+2\log2+o(1)$. 
The methods used in the proof Theorem~{\MainThm} are reminiscent of certain
techniques first used in~[\refnbBKLdiam, \refnbBKLconn].

The organisation of this note is as follows. In~\S1 we present some
definitions and preliminary results, and in~\S2 we prove the main
technical lemma (Lemma~{\lemmaD}) that is needed in the proof of
Theorem~{\MainThm}. This theorem is proved in~\S3. We close this note
with some remarks and further problems.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% sec1
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\beginsection \S1. Preliminaries

Throughout this note, we let~$W=(W_e)_{e\in E(Q^n)}$ be a family of
independent exponential random variables each of mean~1.  For this section and
the next, we assume that a constant~$0<\epsilon<1/6$ has been fixed.

One extremely simple but important idea in our analysis of~$(Q^n,W)$
is that we may easily decompose~$W_e$ ($e\in E(Q^n)$) into a
collection of independent exponential random variables. This
decomposition is then used to handle several events independently.
Let~$X=(X_e)$, $Y=(Y_e)$, and~$Z=(Z_e)$ be three families of
independent exponential r.vs, where the~$X_e$ have
mean~$(1-2\epsilon)^{-1}$, and the~$Y_e$ and~$Z_e$ have
mean~$\epsilon^{-1}$.  Writing~$a\wedge b$ for the minimum of~$a$
and~$b$, if~$W'_e=X_e\wedge Y_e\wedge Z_e$ ($e\in E(Q^n)$),
clearly~$W'_e$ is an exponential r.v.~with mean~1. Thus we may
study~$(Q^n,W)$ by analysing~$(Q^n,X)$, $(Q^n,Y)$, and~$(Q^n,Z)$.

All the asymptotics below refer to~$n\to\infty$. Moreover, we very often
tacitly assume that~$n$ is large enough in the estimates that follow.  As
is usual in the theory os random graphs, we use the terms `almost surely'
and `almost every' to mean `with probability tending to~$1$
as~$n\to\infty$'.  For clarity, we shall denote~$\emptyset\in Q^n$
by~$x_0$.  The neighbourhood of~$x\in Q^n$ is denoted
by~$\Gamma(x)=\GammaQn(x)$. For graph-theoretical terminology not defined
here, we refer the reader to~{\refBBGTM}.

Our first two lemmas concern~$(Q^n,X)$.

\proclaim Lemma {\lemmaA}. For all~$x\in Q^n$,
let~$N_x=N_x(\epsilon,X)\subset\GammaQn(x)$ be defined
by~$N_x=\{y\in\GammaQn(x)\:X_{xy}\leq\log2+3\epsilon\}$ if~$x\neq x_0$,
and~$N_{x_0}=\{y\in\GammaQn(x_0)\:X_{x_0y}\leq\epsilon\}$. Then there
is a constant~$c_1=c_1(\epsilon)>0$ such that with
probability~$1-o(1)$ we have~$|N_x|\geq c_1n$ for all~$x\in Q^n$. 
\endproclaim
\proof
Fix an arbitrary vertex~$x\neq x_0$ in~$Q^n$. Then, for a
fixed~$y\in\GammaQn(x)$,
$$
\P(X_{xy}\geq\log2+3\epsilon)=\exp\{-(\log2+3\epsilon)(1-2\epsilon)\}
  \leq(1-\alpha)/2,
$$
for some~$\alpha=\alpha(\epsilon)>0$. From standard bounds for the tail
of the binomial distribution, we see that for a suitable
constant~$c'_1>0$ we almost surely have~$|N_x|\geq c'_1n$ for all~$x\neq
x_0$. Similarly, for a suitable constant~$c''_1>0$, we have
that~$|N_{x_0}|\geq c''_1n$ almost surely. Thus we may
take~$c_1=c'_1\wedge c''_1$. 
\endproof

We now describe the results from~{\refFP} concerning first-passage
percolation on~$Q^n$.  For all~$n\geq1$, let~$x_0=x_0^{(n)}=\emptyset\in
Q^n$ and~$y_0=y_0^{(n)}=[n]\in Q^n$.  Consider~$(Q^n,W)$, and let
$$
T_0=\inf\{T\in\R\:d_W(x_0,y_0)\leq T\hbox{ with probability }1-o(1)\}.
                                                          \slabel{Tnought}
$$
Equivalently, $T_0$ is the smallest~$T$ ($0\leq T\leq\infty$) such
that, for any given~$\delta>0$, we have~$\limsup_n\P(d_W(x_0,y_0)\geq
T+\delta)=0$ Thus~$T_0$ is the first-passage percolation time between
two opposite vertices in~$Q^n$.  Fill and Pemantle~{\refFP} have shown
that~$T_0\leq1$, and an argument due to Durrett given in~{\refFP}
gives that~$T_0\geq\log(1+\surd2)=.881\cdots\,$. Our next lemma brings
in the parameter~$T_0$ into our problem. Before we can state this
lemma we need some definitions. A {\deffont subcube\/} of~$Q^n$ is a
subgraph induced in~$Q^n$ by a set of the form
$$
Q_{S,A}=Q(S,A)=\{x\in Q^n\:x\cap S=A\}, 
$$
where~$A\subset S\subset[n]$. In the sequel we shall denote the
subcube induced by~$Q_{S,A}$ by~$Q_{S,A}=Q(S,A)$ as well, since this
will not cause any confusion. The {\deffont dimension\/}~$\dim(Q_{S,A})$
of~$Q_{S,A}$ is~$n-|S|$. For an integer~$k\geq0$ and a set~$X$, we
write~$X^{(k)}$ for the set of all $k$-element subsets of~$X$.

Given~$x$ and~$y\in Q^n$ we define the subcube~$\<x,y\>$ {\deffont
  spanned\/} by~$x$ and~$y$ by
$$
\<x,y\>=Q\big((x\symmdiff y)\comp,x\setminus(x\symmdiff y)\big)
       =Q\big((x\symmdiff y)\comp,y\setminus(x\symmdiff y)\big),
$$
where~$u\comp=[n]\setminus u$ and as usual~$\symmdiff$ denotes
symmetric difference. If~$x\subset y$ then~$\<x,y\>$ equals the
`interval'~$[x,y]$ in~$Q^n=\cP([n])$ regarded as a partial order under
inclusion, that is~$\<x,y\>=[x,y]=\{z\in Q^n\:x\subset z\subset y\}$.
If~$v\in\<x,y\>$, let us call the pair~$(\<x,y\>;v)$ a {\deffont rooted
cube\/} with {\deffont root\/}~$v$. For the rest of this note, we
let~$k_0=\lceil\log n\rceil$, and
set
$$
\T=\{(x,y,z)\in Q^n\times Q^n\times Q^n\:
       d(x,y)\geq2k_0+1,\,d(x,z)=2k_0,\,z\in\<x,y\>\}.
$$
For a triple~$(x,y,z)\in\T$ let~$\F_{x,y,z}$ be the family
$$
\big\{(\<v,w\>;v)\:v\in\<x,z\>,\,d(x,v)=k_0,\,w=v\symmdiff y\symmdiff z\big\}
$$ 
of rooted subcubes of~$\<x,y\>$. In visualising~$\F_{x,y,z}$, it might be
helpful to note that the map~$\varphi_{y,z}\:u\mapsto
u\symmdiff(y\symmdiff z)$ gives a natural isomorphism between the
subcubes~$\<x,z\>$
and~$\<\varphi_{y,z}(x),\varphi_{y,z}(z)\>=\<\varphi_{y,z}(x),y\>$.
Moreover, note that the rooted subcubes $(\<v,w\>;v)$ in~$\F_{x,y,z}$ are
translates of the rooted cube~$(\<x,\varphi_{y,z}(x)\>;x)=(\<x,x\symmdiff
y\symmdiff z\>;x)$.  In fact, we may clearly regard~$Q^n$
as~$\<x,z\>\times\<x,\varphi_{y,z}(x)\>$.  Let us say
that~$(\<v,w\>;v)\in\F_{x,y,z}$ is {\deffont inexpensive\/} if~$d_X(v,w)$
is at most~$(T_0+\epsilon)/(1-2\epsilon)$, and {\deffont expensive\/}
otherwise.  In the sequel we write~$m_0={2k_0\choose k_0}$.  Rather
crudely we have~$n^{1.38}\leq m_0\leq n^{1.39}$.

\proclaim Lemma {\lemmaB}. There is a constant~$c_2=c_2(\epsilon)>0$ such that 
the following holds almost surely.  For all~$(x,y,z)\in\T$ the
number of rooted subcubes in~$\F_{x,y,z}$ that are inexpensive is at
least~$c_2m_0=c_2{2k_0\choose k_0}$.
\endproclaim
\proof
Let~$(x,y,z)\in\T$ be given.  Fix~$v$, $w\in Q^\ell$ ($\ell\geq1$)
with~$d(v,w)=\ell$, and let $U=(U_e)_{e\in E(Q^\ell)}$ be a family of
independent exponential r.vs of mean~$1$.  By the definition of~$T_0$,
we have that for any given fixed~$\delta>0$ we
have~$\lim_\ell\P(d_U(v,w)\geq T_0+\delta)=0$.  It follows that there
is an integer~$\ell_0=\ell_0(\epsilon)$ such
that~$\P\big(d_U(v,w)\leq(T_0+\epsilon)/(1-2\epsilon)\big)\geq1/2$
if~$\ell\geq\ell_0$.  Moreover, there clearly exists a
constant~$c'_2=c'_2(\epsilon)>0$ such that the probability that a
rooted cube~$(\<v,w\>;v)$ is inexpensive is at least~$c'_2$
if~$1\leq\dim\<v,w\>\leq\ell_0$. Let us now
set~$c_2=(1/2)(c'_2\wedge1/2)$.

Let~$(\<v_i,w_i\>;v_i)$ ($1\leq i\leq m_0$) be the~$m_0$ rooted cubes
in~$\F_{x,y,z}$. Note that the~$\<v_i,w_i\>$ are pairwise vertex-disjoint
and hence the events that~$(\<v_i,w_i\>;v_i)$ ($1\leq i\leq m_0$) should
be inexpensive are independent. Thus the number~$J$ of inexpensive rooted
cubes in~$\F_{x,y,z}$ has binomial distribution~$\Bi(m_0,p)$ with
parameters~$m_0={2k_0\choose k_0}$ and~$p\geq2c_2$. It now follows
that~$\P(J<c_2m_0)\leq\exp\{-pm_0/8\}\leq\exp\{-n^{1.3}\}=o(|\T|^{-1})$, 
as required.
\endproof

Our next result is a simple lemma concerning~$(Q^n,Y)$. Recall
that~$k_0=\lceil\log n\rceil$. If~$x$, $y\in Q^n$ are such
that~$d(x,y)=2\ell$, let~$L_{x,y}$ denote the {\deffont middle
layer\/}~$\{z\in\<x,y\>\:d(x,z)=d(z,y)=\ell\}$ of~$\<x,y\>$.

\proclaim Lemma {\lemmaC}. Let~$V_0=V_0(Y)$ be the set of vertices~$z$
of~$Q^n$ that are incident to at least~$(\epsilon^2/3)n$ edges~$e$
with~$Y_e\leq\epsilon$.  Then almost surely for all~$x$, $y\in Q^n$
with~$d(x,y)=2k_0$ at most~$n$ vertices in the middle layer~$L_{x,y}$
of~$\<x,y\>$ fail to be in~$V_0$.
\endproclaim
\proof
Let~$x=x_0=\emptyset$ and fix~$y\in[n]^{(2k_0)}$. For any edge~$e\in E(Q^n)$
we have~$\P(Y_e\leq\epsilon)=1-\exp(-\epsilon^2)\geq\epsilon^2/2$, and hence
for fixed~$z\in L_{x,y}$ the probability that~$z$ does not belong to~$V_0$ is
at most~$p_0=\exp\{-\epsilon^2 n/36\}$. Thus the probability that we
have~$|L_{x,y}\setminus V_0|\geq n$ is at most
$$
{m\choose n}\exp\{-\epsilon^2n^2/36\}
  \leq{n^{1.4}\choose n}\exp\{-\epsilon^2n^2/36\}
  \leq\exp\{-\Omega(n^2)\}.
$$
Thus the probability that there exist~$x$, $y\in Q^n$
with~$d(x,y)=2k_0$ such that~$|L_{x,y}\setminus V_0|\geq n$ is at
most~$4^n\exp\{-\Omega(n^2)\}=o(1)$.
\endproof

Let~$V_0=V_0(Y)$ be defined as in Lemma~{\lemmaC}. For all~$z\in V_0$ we
let~$N'_z=N'_z(\epsilon,Y)=\{z'\in\GammaQn(z)\:Y_{zz'}\leq\epsilon\}$.
Thus~$|N'_z|\geq(\epsilon^2/3)n$ for any~$z\in V_0$. 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% sec2
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\beginsection \S2. The main lemma

In this section we study~$(Q^n,Z)$, and prove a lemma
(Lemma~{\lemmaD}) that will be fundamental for the proof of our main
result, Theorem~{\MainThm}. We stress that the argument in the proof
below is quite crude, and that with a little more patience one may
prove a stronger result. However, such a stregthening of this lemma
would not, as far as we can see, improve Theorem~{\MainThm}. Before
turning to our lemma, recall that~$0<\epsilon<1/6$ has been fixed.

\proclaim Lemma {\lemmaD}.
Set~$K=\lfloor(\epsilon^6n/650)^{1/7}\rfloor$, and let~$m^2=\omega
n^{11/7}\leq n^2$, where~$\omega=\omega(n)\to\infty$ as~$n\to\infty$.
Let~$x=x_0=\emptyset$ and fix~$y\subset[n]$ with~$1\leq k=|y|\leq K$.
Let~$S\subset\GammaQn(x)$ and~$T\subset\GammaQn(y)$ with~$|S|$,
$|T|\geq m$ be given. Then in~$(Q^n,Z)$ there is an $S$---$T$~path~$P$
of $Z$-length~$\ell(P,Z)=\sum_{e\in E(P)}Z_e$ at most~$\epsilon$ with
probability at least~$1-\e^{-\omega n/\log\omega}$.
\endproclaim
\proof
For all~$e\in E(Q^n)$ and $2\leq j\leq K+1$, let~$Z_e^{(j)}$ be an exponential
r.v.~with mean~$K/\epsilon$, and assume that all these variables are
independent.  Set~$Z^{(j)}=(Z_e^{(j)})_{e\in E(Q^n)}$ for~$2\leq j\leq K+1$.
Clearly~$Z_e$ and~$\bigwedge_j Z_e^{(j)}$ have the same distribution for
all~$e\in E(Q^n)$.  Let~$t_0=\epsilon/(2K+k-2)$. Then for all~$2\leq j\leq
K+1$ we have
$$
p=\P\{Z_e^{(j)}\leq t_0\}=1-\exp\left\{-\epsilon^2\over K(2K+k-2)\right\} 
                \geq{\epsilon^2\over2K(2K+k-2)}\geq{\epsilon^2\over6K^2}.
$$
For all~$2\leq j\leq K+1$, let~$H_j=H_j(Z^{(j)})\subset Q^n$ be the
spanning subgraph of~$Q^n$ whose edge-set is~$\{e\in E(Q^n)\:Z_e^{(j)}\leq
t_0\}$. Note that the~$H_j$ ($2\leq j\leq K+1$) are~$K$ independent
random elements of~$\G(Q^n,p)$, the space of random spanning subgraphs
of~$Q^n$ whose edges are independently present with probability~$p$.  Let
us set~$G_j=H_2\cup\cdots\cup H_j$ ($2\leq j\leq K+1$).  We now claim the
following.

\claim In~$G_{K+1}$ there is an $S$---$T$~path of length at most~$2K+k-2$ with
probability at least~$1-\exp\{-\omega n/\log\omega\}$.
\endclaim

Note that a path as in the claim above has $Z$-length at
most~$t_0(2K+k-2)=\epsilon$, and hence to prove our lemma it suffices
to prove this claim. To verify this claim we start by
setting~$S_1=\{v\in S\:v\not\subset y\}$ and~$T_1=\{v\in T\:y\subset
v\}$. Clearly~$|S_1|$, $|T_1|\geq m-k\geq m/2$. We shall think
of~$Q^n$ as~$Q^{n-k}\times Q^k$ in the following way. For
each~$v\subset y\comp=[n]\setminus y$, let
$$
Q_v=\<v,v\symmdiff y\>=\<v,v\cup y\>=\{z\subset[n]\:z\cap y\comp=v\}.
\slabel{Qv} 
$$
Note that~$Q_v$ is a cube of dimension~$k=|y|$, and
that~$Q=\<x_0,y\comp\>=\{v\in Q^n\:v\subset y\comp\}$ is a cube of
dimension~$n-k$. Also, we may naturally regard~$Q^n$
as~$\<x_0,y\comp\>\times\<x_0,y\>$.

Write~$n_1=|y\comp|=n-k$ and note that clearly~$n_1=(1+o(1))n$. Let 
us set
$$
S_2'=\{z\in(y\comp)^{(2)}\:z\in\GammaQn(S_1)
                \hbox{ and }z\cup y\in\GammaQn(T_1)\}.
$$
A moment's thought shows that~$|S'_2|\geq{m/2\choose2}$. Thus, setting 
$$
S_2=\{z\in(y\comp)^{(2)}\:z\in\GammaH2(S_1)
                 \hbox{ and }z\cup y\in\GammaH2(T_1)\},
$$
quite crudely we have~$\E(|S_2|)\geq{m/2\choose2}p^2\geq
m^2p^2/9$. Hence, with probability at least~$1-\exp\{-m^2p^2/1800\}=1- 
\exp\{-\Omega(\epsilon^{4/7}\omega n)\}$, we have~$|S_2|\geq m^2p^2/10$.

For the rest of the argument, we condition on~$|S_2|\geq
m^2p^2/10\geq(1/5)(mp/n)^2{n_1\choose2}$. In the sequel,
if~$U\subset\<x_0,y\comp\>$, we write~$U\vee y$ for~$\{u\cup y\:u\in U\}$,
namely the translate of~$U$ by the map~$u\mapsto u\cup y$, which is
contained in the cube~$\<y,[n]\>$. Let us now fix~$3\leq j\leq K$ and
condition on the existence
of~$S_2\subset(y\comp)^{(2)},\ldots,S_{j-1}\subset(y\comp)^{(j-1)}$ for
which the following conditions hold for all~$2\leq i<j$.
\smallskip
\itemitem{({\it i\/})}$|S_i|\geq(4/5)2^{-i}\(mp^{i-1}/n\)^2{n_1\choose i}$,
\itemitem{({\it ii\/})}for all~$z\in S_i$ there is an $S_1$---$z$~path
of length~$i-1$ in~$G_i=H_2\cup\cdots\cup H_i$, 
\itemitem{({\it iii\/})}for all~$z\in S_i$ there is a $T_1$---$(z\cup
y)$~path of length~$i-1$ in~$G_i=H_2\cup\cdots\cup H_i$.
\smallskip
\noindent Now let~$S'_j=\GammaQn(S_{j-1})\cap(y\comp)^{(j)}
=\{z'\in(y\comp)^{(j)}\:z\subset z'\hbox{ for some }z\in S_{j-1}\}$.
Then, by the local LYM inequality (see for instance~{\refBBg}, \S3),
we have that
$$
|S'_j|\geq|S_{j-1}|{n_1\choose j-1}^{-1}{n_1\choose j} 
      \geq{4\over5}2^{-j+1}\(mp^{j-2}\over n\)^2{n_1\choose j}.
$$
We now set~$S_j=\{z\in S'_j \:z\in\GammaH{j}(S_{j-1}) \hbox{ and
  }z\cup y\in\GammaH{j}(S_{j-1}\vee y)\}$. Then very crudely we have
that 
$$
\E(|S_j|)\geq|S'_j|p^2
  \geq{4\over5}2^{-j+1}\(mp^{j-1}\over n\)^2{n_1\choose j},
$$
and so with probability at least
$$
1-\exp
 \left\{-{1\over5}2^{-j}\(mp^{j-1}\over n\)^2{n_1\choose j}\right\},
$$
condition~({\it i\/}) above holds for~$i=j$, that
is~$|S_j|\geq(4/5)2^{-j}\(mp^{j-1}/n\)^2{n_1\choose j}$.  Note that by
the definition of~$S_j$ conditions~({\it ii\/}) and~({\it iii\/}) above
hold for~$i=j$. Let
$$
S''_K=\{z\in(y\comp)^{(K)}
            \:d_{G_K}(S,z),\,d_{G_K}(T,z\cup y)\leq K-1\},
$$
where~$d_{G_K}$ denotes the distance in the graph~$G_K$. Then, using
the argument above for~$3\leq j\leq K$ in turn, we see that with
probability at least
$$
P_0=1-\sum_{3\leq j\leq K}
   \exp\left\{-{1\over5}2^{-j}\(mp^{j-1}\over n\)^2{n_1\choose j}\right\}
$$
we have
$$
|S''_K|
  \geq{4\over5}2^{-K}\(mp^{K-1}\over n\)^2{n_1\choose K}. \slabel{SK}
$$
To estimate~$P_0$, note that if~$3\leq j\leq K$ then
$$
\eqalign{
A=2^{-j}\(mp^{j-1}\over n\)^2&{n_1\choose j}
\geq{m^2\over n^2p^2}\(p^2n_1\over2j\)^j\cr
   &\quad\geq{m^2\over n^2p^2}
       \left\{\(p^2n_1\over6\)^3\wedge\(p^2n_1\over2K\)^K\right\},\cr
}
$$
since the function~$f(x)=(B/x)^x$ ($x>0$) is log-concave. However, 
$$
\(p^2n_1\over2K\)^K\geq\({1\over73}{\epsilon^4n\over K^5}\)^K
    =\(\Omega(n^{2/7})\)^K\geq\(p^2n_1\over6\)^3,
$$
and hence~$A\geq(1/216+o(1))m^2np^4=\Omega(\omega n^{10/7})$. Thus, very
crudely, 
$$
P_0\geq1-K\exp\{-\Omega(\omega n^{10/7})\}
      \geq1-\exp\{-\omega n\}. \slabel{Pnought}
$$
Let us now condition on~{\eqnoSK}. To finish the proof of our claim, we
shall show that with very high probability there is an
$S''_K$---$(S''_K\vee y)$~path of length~$k$ in~$H_{K+1}$. We shall do
this using an extremely crude argument.  Consider the
family~$\F=\{Q_v\:v\in S''_K\}$ of $k$-cubes as defined
in~{\eqnoQv}. Recall that~$Q_v$ is a translate of~$\<x_0,y\>$ by~$v$,
and note that in particular the~$Q_v$ ($v\in S''_K$) are pairwise
disjoint. Consider for each~$v\in S''_K$ a fixed $v$---$(v\cup y)$
path~$P_v\subset Q_v$ of length~$k$, and note that the
probability~$P_1$ that there should not be an $S''_K$---$(S''_K\vee
y)$ path of length~$k$ in~$H_{K+1}$ is at
most~$(1-p^k)^{|S''_K|}\leq(1-p^K)^{|S''_K|}\leq\exp\{-p^K|S''_K|\}$.
However, as~{\eqnoSK} holds, 
$$
\eqalign{
p^K|S''_K|
 &\geq{4\over5}2^{-K}p^K\(mp^{K-1}\over n\)^2{n_1\choose K}\cr   
 &\qquad\qquad\geq{4\over5}{m^2\over p^2n^2}\(p^3n\over3K\)^K
    \geq{4\over5}\(m\over pn\)^2\(650\over648\)^K,\cr
}
$$
which is much larger than~$\omega n$. Thus~$P_1\leq\e^{-\omega
  n}$. This bound and inequality~{\eqnoPnought} finish the proof of
the claim, and hence Lemma~4 is proved. 
\endproof
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% sec3
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\beginsection \S3. The main result

Recall that~$W=(W_e)$ is a collection of independent exponential r.vs
each with mean~1. Also, recall that~$T_0$ is the first-passage
percolation time between two diametrically opposite vertices in~$Q^n$
when the passage times are given by~$W$ (cf.~{\eqnoTnought} in
Section~2).

\proclaim Theorem {\MainThm}. The following hold with probability~$1-o(1)$
as~$n\to\infty$. 
\item{\rm({\it i\/})}Writing~$x_0=\emptyset\in Q^n$, we
  have~$\max_{y\in Q^n}d_W(x_0,y)\leq T_0+\log2+o(1)$,
\item{\rm({\it ii\/})}$\diam(Q^n,W)\leq T_0+2\log2+o(1)$.
\endproclaim
\proof
({\it i\/})~Let~$0<\epsilon<1/6$ be fixed. We regard~$W_e$ as~$X_e\wedge
Y_e\wedge Z_e$ ($e\in E(Q^n)$), where~$X_e$, $Y_e$, and~$Z_e$ are as in
Section~2, {\it i.e.\/}~the~$X_e$ are exponential with
mean~$(1-2\epsilon)^{-1}$, the~$Y_e$ and~$Z_e$ are exponential with
mean~$\epsilon^{-1}$, and all these variables are independent.
Let us now consider the following events. (We keep the notation
introduced in Section~2.)
\smallskip
\itemitem{({\it a\/})}For all~$x\in Q^n$ we
have~$|N_x|=|N_x(\epsilon,X)|\geq c_1n$,
\itemitem{({\it b\/})}for all~$(x,y,z)\in\T$, the number of
inexpensive rooted subcubes in~$\F_{x,y,z}$ is not smaller
than~$c_2m_0=c_2{2k_0\choose k_0}$,
\itemitem{({\it c\/})}for all~$x$, $y\in Q^n$ with~$d(x,y)=2k_0$, we
have~$|L_{x,y}\setminus V_0|=|L_{x,y}\setminus V_0(Y)|\leq n$.
\smallskip
\noindent Note that by Lemmas~{\lemmaA}, {\lemmaB}, and~{\lemmaC}
conditions~({\it a\/}), ({\it b\/}), and~({\it c\/}) above hold almost
surely.  For the rest of the argument we condition on~$(Q^n,X)$
and $(Q^n,Y)$ satisfying~({\it a\/}), ({\it b\/}), and~({\it c\/}).

Let~$S_{x_0}=N_{x_0}=N_{x_0}(\epsilon,X)
=\{y\in\GammaQn(x_0)\:X_{x_0y}\leq\epsilon\}$.
For every~$x\in Q^n-x_0$, set~$S_x=N'_x=N'_x(\epsilon,Y)$
if~$x\in V_0=V_0(Y)$, and~$S_x=N_x=N_x(\epsilon,X)$ otherwise. For a
fixed pair~$x$, $y\in Q^n$ with~$d(x,y)\leq
K=\lfloor(\epsilon^6n/650)^{1/7}\rfloor$, if we let~$S=S_x$ and~$T=S_y$,
Lemma~{\lemmaD} tells us that~$d_Z(S,T)\leq\epsilon$ with probability at
least~$1-\exp\{-n^{5/4}\}$. Thus~({\it d\/}) below holds with
probability~$1-o(1)$.
\smallskip
\itemitem{({\it d\/})}For all~$x$, $y\in Q^n$ with~$d(x,y)\leq K$ we
have 
$$
d_W(x,y)\leq\cases{
          3\epsilon         &if~$x$, $y\in V_0\cup\{x_0\}$\cr
          \log2+5\epsilon   &if~$x\in V_0\cup\{x_0\}$ 
                                or~$y\in V_0\cup\{x_0\}$\cr
          2\log2+7\epsilon  &otherwise.\cr}
$$

\noindent We now condition on~$(Q^n,W)$ satisfying~({\it d\/}), and
claim that consequently we have~$\max\{d_W(x_0,y)\:y\in Q^n\}\leq
T_0+\log2+3\epsilon T_0+12\epsilon$.  First note that it follows
from~({\it d\/}) that~$\max\{d_W(x_0,y)\:y\in Q^n,\,d(x_0,y)\leq K\}$
is as small as claimed, and hence let~$y\in Q^n$ be such
that~$d(x_0,y)>K\geq2k_0$.  Pick~$z\in\<x_0,y\>$ with~$d(x_0,z)=2k_0$,
and note that then~$(x_0,y,z)\in\T$. Since we are conditioning
on~({\it b\/}) and~({\it c\/}) above, we may find~$v\in L_{x_0,y}$
such that~$v\in V_0$, $w=v\symmdiff y\symmdiff z\in V_0$,
and~$(\<v,w\>;v)$ is an inexpensive rooted cube. But then
$$
\eqalign{
d_W(x_0,y)&\leq d_W(x_0,v)+d_W(v,w)+d_W(w,y)  \cr
&\qquad\leq3\epsilon
     +{T_0+\epsilon\over1-2\epsilon}+\log2+5\epsilon
 \leq T_0+\log2+3\epsilon T_0+12\epsilon.\cr
}
$$
Theorem~{\MainThm}({\it i\/}) follows by letting~$\epsilon\to0$.

({\it ii\/})~Minor modifications to the above argument gives a proof
of Theorem~{\MainThm}({\it ii\/}). 
\endproof

The result above, coupled with the upper bound~$T_0\leq1$ for the
first-passage percolation time~$T_0$ established by Fill and
Pemantle~{\refFP}, gives the following corollary.

\proclaim Corollary {\corollary}. The following hold 
with probability~$1-o(1)$ as~$n\to\infty$.
\item{\rm({\it i\/})}Writing~$x_0=\emptyset\in Q^n$, we
  have~$\max_{y\in Q^n}d_W(x_0,y)\leq1+\log2+o(1)$,
\item{\rm({\it ii\/})}$\diam(Q^n,W)\leq1+2\log2+o(1)$.
\endproclaimsquare
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% sec4
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\beginsection \S4. Concluding remarks and open problems

The best bounds so far for the first-passage percolation time~$T_0$
in~$Q^n$, defined in~\S1, are the ones given in~{\refFP},
namely~$.881\ldots=\log(1+\surd2)\leq T_0\leq1$. We believe that
percolation happens at a sharply defined time.

\proclaim Conjecture {\conjA}. For all~$\delta>0$ we
have~$\lim_{n\to\infty}\P\{d_W(x_0,y_0)\leq T_0-\delta\}=0$.
\endproclaimsquare

We also believe that the analogous phenomenon happens in Richardson's
model. As a starting point, it would be interesting to settle the
following problem.

\proclaim Problem {\conjB}. Do the following two assertions hold with
probability~$1-o(1)$ as~$n\to\infty${\rm$\,$?}
\item{\rm({\it i\/})}Writing~$x_0=\emptyset\in Q^n$, one 
  has~$\max_{y\in Q^n}d_W(x_0,y)=T_0+\log2+o(1)$.
\item{\rm({\it ii\/})}One has~$\diam(Q^n,W)=T_0+2\log2+o(1)$. 
\endproclaimsquare
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% shipoutreferences
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\firstgofalse\refno=0
\beginreferences
\book[BBGTM] \BB
            Graph Theory---An Introductory Course
            Springer--Verlag, New York~1979, ${\it viii}+180$pp
\book[BBg]  \BB
            Combinatorics
            Cambridge University Press, Cambridge 1986, ${\it xii}+177$pp
\dammit[BKLdiam] \BB, Kohayakawa, Y., \L uczak, T.
            On the diameter and radius of random subgraphs of the %
            cube, {\it\RSA\/}, to appear
\dammit[BKLconn] \BB, Kohayakawa, Y., \L uczak, T.
            Connectivity properties of random subgraphs of the cube, %
            {\it\RSA\/}, to appear
\paper[FP] Fill, J.A., Pemantle, R.
            Percolation, first-passage percolation, and covering times %
            for Richardson's model on the $n$-cube
            The Annals of Applied Probability\vol3
            593--629, 1993
\endreferences
\bye
