%
% TeX file for
%
%   `Connectivity properties of random subgraphs of the cube'
%
%
\magnification=\magstep1
\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}
\setupspacing1
\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\ninemsa=msam9  \font\eightmsa=msam8 \font\sixmsa=msam6
\font\ninemsb=msbm9  \font\eightmsb=msbm8 \font\sixmsb=msbm6
\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\msafam=\ninemsa  \scriptfont\msafam=\sixmsa
  \scriptscriptfont\msafam=\fivemsa
\textfont\msbfam=\ninemsb  \scriptfont\msbfam=\sixmsb
  \scriptscriptfont\msbfam=\fivemsb
%\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\msafam=\eightmsa  \scriptfont\msafam=\sixmsa
  \scriptscriptfont\msafam=\fivemsa
\textfont\msbfam=\eightmsb  \scriptfont\msbfam=\sixmsb
  \scriptscriptfont\msbfam=\fivemsb
%\tt\ttglue=.5em plus.25em minus.15em
\normalbaselineskip=10pt
\setbox\strutbox=\hbox{\vrule height7pt depth2pt width0pt}%
\let\sc=\sixrm%\let\big=\eightbig
\normalbaselines\rm}
\font\twelverm=cmr12
\font\twelvebf=cmbx12
\font\twelveit=cmti12
\font\twelvesl=cmsl12
\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\Bi{\mathop{\rm Bi}\nolimits}
\def\symmdiff{\bigtriangleup}
\def\im{\mathop{\rm im}\nolimits}
\def\mod{\mathop{\rm mod}}
\def\({\left(}
\def\){\right)}
\def\[{\left[}
\def\]{\right]}
\def\<{\left\langle}
\xdef\:{\>}
\def\>{\right\rangle}  % This is different from TeX  :( 
\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})}
%
\font\titlefont=cmbx10 scaled \magstep1
\def\authorfont{\rm}
\def\addressfont{\rm}
\def\title#1{\null\vglue5truecm{\parindent=0pt\titlefont#1}}
\def\titlecont#1{\vskip.3pt{\parindent=0pt\titlefont#1}}
\def\author#1{{\authorfont\vglue1.7truecm\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\draftdate{\vglue1truecm\noindent{\eightpoint\rm Draft of \date}}
\newif\ifdraft
\newif\ifexplicitdate
\def\draftof#1{\drafttrue\explicitdatetrue\def\givendate{#1}}
\explicitdatefalse
\draftfalse
\headline={\ifdraft\hfil{\eightpoint{\sl draft of %
\ifexplicitdate\givendate\else\date\fi}}\else\hfil\fi}
\def\endabstract{\par\endgroup}
\def\abstract{\vglue1.3truecm\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  
{\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 
{\rm(}{#1}{\rm)}\enspace\ignorespaces\bgroup\sl}
\def\endcase{\par\ifdim\lastskip<\smallskipamount
                \removelastskip\penalty3000\smallskip\fi}
\def\case#1.{\smallbreak
\noindent 
{\sl Case\/} #1.\enspace\ignorespaces}
\def\casenodot#1 {\smallbreak
\noindent 
{\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\proofoftheclaim{\proofofassertion{\it Proof of the Claim\/}.\enspace}
\let\endproofoftheclaim=\endproofofassertion
\def\square{\ifmmode\sqr\else{$\sqr$}\fi}
\def\sqr{\vcenter{
         \hrule height.1mm
         \hbox{\vrule width.1mm height2.2mm\kern2.16mm\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}
\let\endproofoftheclaimsquare=\endproof
\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}
\newif\iflargesectiontitles
\largesectiontitlesfalse
\def\beginsection#1\par{\vskip0pt plus.08\vsize\penalty-250
    \vskip0pt plus-.08\vsize\bigskip\vskip\parskip
    \message{#1}\leftline{\iflargesectiontitles\twelvebf\else\bf\fi#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
    \vskip0pt plus.1\vsize\penalty-250
    \vskip0pt plus-.08\vsize\bigskip\vskip\parskip
    \message{References}
    \ifPortuguese\leftline{\iflargesectiontitles
                             \twelvebf\else\bf\fi Refer\^encias}%
             \else\leftline{\iflargesectiontitles
                              \twelvebf\else\bf\fi 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\PMH{Periodica Math. Hungar.}
\def\PCPS{Proc. Cambridge Phil. Soc.}
\def\MPCPS{Math. Proc. Cambridge Phil. Soc.}
\def\RSA{Random Structures and Algorithms}
% 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.H.}
\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.tex
%
\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}
% sec2.tex
\edef\lemmaA 
{\statementlabel}\newstatemno
\edef\lemmakA
{\statementlabel}\newstatemno
% sec3.tex
\edef\lemmakB
{\statementlabel}\newstatemno
\edef\lemmakC
{\statementlabel}\newstatemno
\edef\kcon
{\statementlabel}\newstatemno
\edef\corkcon
{\statementlabel}\newstatemno
%
% macros.tex
%
\let\epsilon=\varepsilon
\def\o{\omega}
\def\O{\Omega}
\def\qnl{Q^{n[-l]}}
\def\qpl{Q_p^{[-l]}}
\def\Qnl#1{Q^{n[-#1]}}
\def\frac#1#2{{#1\over#2}}
\def\binom#1#2{{#1\choose#2}}
\def\dk{{\rm diam}^{(k)}}
\def\hQ{{\widehat Q}}
%\def\E{{\rm E}}
\def\Var{\mathop{\rm Var}\nolimits}
% 
\def\pv{p_{\rm v}}
\def\pe{p_{\rm e}}
\def\pbar{{\bar p}}
\def\qbar{{\bar q}}
\def\pvbar{\pbar_{\rm v}}
\def\pebar{\pbar_{\rm e}}
\def\cP{{\cal P}}
\def\bfi{{\bf i}}
\def\bfa{{\bf a}}
\def\A{{\cal A}}
\def\B{{\cal B}}
\def\C{{\cal C}}
\def\D{{\cal D}}
\def\F{{\cal F}}
\def\G{{\cal G}}
\def\Gc{\G_{\rm c}}
\def\Gind{\G_{\rm ind}}
\def\Gor{G^{\rm or}}
\def\cL{{\cal L}}
\def\cN{{\cal N}}
\def\dQn{d_{Q^n}}
\def\dQm{d_{Q^m}}
\def\dQp{d_{Q_p}}
\def\dQt{d_{Q_t}}
\def\Qn{Q^n}
\def\Qp{Q_p}
\def\Qnt{Q^{n,t}}
\let\Qtn=\Qnt
\def\dim{\mathop{\rm dim}}
\def\tQ{{\widetilde Q}}
\def\tG{{\widetilde G}}
\def\tQind{{\widetilde Q}_{\rm ind}}
\def\diam{\mathop{\rm diam}\nolimits}
\def\rad{\mathop{\rm rad}\nolimits}
\def\diamk{\diam^{(k)}}
\def\radk{\rad^{(k)}}
\def\GammaQn{\Gamma_{Q^n}}
\def\GammaQp{\Gamma_{Q_p}}
\def\GammaQt{\Gamma_{Q_t}}
\def\Pc{\P_{\rm c}}
\def\S{{\cal S}}
\def\Sak{\S^{(a)}_k}
\def\Ssk{\S^{({\rm s})}_k}
\def\Spk{\S^{({\rm p})}_k}
\def\Swk{\S^{({\rm w})}_k}
\def\Sa#1{\S^{(a)}_{#1}}
\def\Ss#1{\S^{({\rm s})}_{#1}}
\def\Sp#1{\S^{({\rm p})}_{#1}}
\def\Sw#1{\S^{({\rm w})}_{#1}}
\def\tak{t^{(a)}_k}
\def\tsk{t^{({\rm s})}_k}
\def\tpk{t^{({\rm p})}_k}
\def\twk{t^{({\rm w})}_k}
\def\tdk{t^{({\rm d})}_k}
\def\ta#1{t^{(a)}_{#1}}
\def\ts#1{t^{({\rm s})}_{#1}}
\def\tp#1{t^{({\rm p})}_{#1}}
\def\tw#1{t^{({\rm w})}_{#1}}
\def\td#1{t^{({\rm d})}_{#1}}
\def\Xsk{X^{({\rm s})}_k}
\def\Xpk{X^{({\rm p})}_k}
\def\Xak{X^{(a)}_k}
\def\tmink{t^{(k)}}
\def\tmin#1{t^{(#1)}}
%
% \scanreferences
%
\firstgotrue\refno=0\beginreferences
\paper[AKS]  \Aj, \Ko, \Sz
             Largest random component of a $k$-cube
             \Comb\vol2
             1--7, 1982
\book[BBf]  \BB
             Random Graphs
             Academic Press, London~1985, ${\it xvi}+447$pp
\paper[BBz] \BB
             Complete matchings in random subgraphs of the cube
             \RSA\vol1
             95--104, 1990
%\dammit[BK]  \BB, Kohayakawa, Y.
%             On Richardson's model in the cube, %
%             to appear
\paper[BKL] \BB, Kohayakawa, Y., \L uczak, T.
             The evolution of random subgraphs of the cube 
             \RSA\vol3
             55--90, 1992
%\dammit[BKLb] \BB, Kohayakawa, Y., \L uczak, T.
%             On the evolution of random Boolean functions, to appear
\dammit[BKLc] \BB, Kohayakawa, Y., \L uczak, T.
             On the diameter and radius of %
             random subgraphs of the cube, to appear
\dammit[BT]  \BB, Thomason, A.G.
             Random graphs of small order, in {\it Random Graphs~'83\/}, %
             Annals of Discrete Mathematics~28 %
             (Karo\'nski, M., Ruci\'nski, A., eds), %
             North-Holland, Amsterdam~1985, pp.~47--97
%\paper[Bua]  Burtin, Yu.D.
%             On extreme metric characteristics of a random graph~I. %
%             Asymptotic estimates
%             Mathematical Notes\vol19
%             710--725, 1974
%\paper[Bub]  Burtin, Yu.D.
%             On extreme metric characteristics of a random graph~II. %
%             Limit distributions
%             Mathematical Notes\vol20
%             83--101, 1975
\dammit[DFF] Dyer, M.E., Frieze, A.M., Foulds, L.R.
             On the strength of connectivity of %
             random subgraphs of the $n$-cube, %
             in {\it Random Graphs~'85\/}, %
             Annals of Discrete Mathematics~33 %
             (Karo\'nski, M., Palka, Z., eds), %
             North-Holland, Amsterdam~1987, pp.~17--40
\dammit[Fau] Faudree, R.J.
             Some strong variations of connectivity, %
             in {\it Combinatorics\/}, {\it Paul Erd\H os is Eighty\/}, %
             Volume~1 (Mikl\'os, D., S\'os, V.T., Sz\H onyi, T., eds), %
             Keszthely (Hungary)~1993, pp.~125--144
%\dammit[FP]  Fill, J.A., Pemantle, R.
%             Percolation, first-passage percolation, and covering times %
%             for Richardson's model on the $n$-cube, %
%             to appear
%\paper[Ka]   Kostochka, A.V.
%             Maximum matchings and connected components of random %
%             subgraphs of the $n$-cube (in Russian)
%             Methods Discrete Anal., Study Boolean Function Graphs\vol48
%             42--70, 1989
%\paper[Kb]   Kostochka, A.V.
%             Matchings in Random Spanning subgraphs of cubelike graphs
%             \RSA\vol1
%             277--285, 1990
\dammit[KSW] Kostochka, A.V., Sapozhenko, A.A., Weber, K.
             On random cubical graphs, in {\it Fourth %
             Czechoslovakian Symposium on Combinatorics, Graphs %
             and Complexity\/} (\Ne, Fiedler, M., eds), %
             Annals of Discrete Mathematics~51, %
             North--Holland, Amsterdam~1992, pp.~155--160
\paper[KSWb] Kostochka, A.V., Sapozhenko, A.A., Weber, K.
             Radius and diameter of random subgraphs of the hypercube
             \RSA\vol4
             215--229, 1993
\paper[LNLP] Lov\'asz, L., Neumann-Lara, V., Plummer, M.
             Mengerian theorems for paths of bounded length
             \PMH\vol9
             269--276, 1978
%\dammit[SW]  Sapozhenko, A., Weber, K.
%             Radius and diameter of random subgraphs %
%             of the hypercube, to appear
\endreferences
%
% fstpg.tex
%
\title{Connectivity Properties of}
\titlecont{Random Subgraphs of the Cube}
 
\author{B.~Bollob\'as${}^1$,
        Y.~Kohayakawa${}^2$,
        and T.~\L uczak${}^{3,\,4}$}
\address
${}^1$ \DPMMS \medskip
\noindent${}^2$ \IMEUSP \medskip
\noindent${}^3$ Mathematical Institute of the %
                Polish Academy of Sciences, \hfil\break
                Pozna\'n, Poland\medskip
\noindent${}^4$ On leave from the Department of Discrete Mathematics,
                \hfil\break 
                Adam Mickiewicz University, ul.~Matejki 48/49, Pozna\'n,
                Poland
\endaddress
\abstract
The $n$-dimensional cube~$Q^n$ is the graph whose vertices are the subsets
of~$\{1,\ldots,n\}$ where two such vertices are adjacent if and only if their
symmetric difference is a singleton.  Clearly~$Q^n$ is an $n$-connected graph
of diameter and radius~$n$.  Write~$M=n2^{n-1}=e(Q^n)$ for the size of~$Q^n$.
Let~$\tQ=(Q_t)_0^M$ be a random $Q^n$-process. Thus~$Q_t$ is a spanning
subgraph of~$Q^n$ of size~$t$, and~$Q_t$ is obtained from~$Q_{t-1}$ by the
random addition of an edge of~$Q^n$ not in~$Q_{t-1}$.
Let~$\tmink=\tau(\tQ;\delta\geq k)$ be the hitting time of the property of
having minimal degree at least~$k$. It is shown in~{\refBKLc} that, almost
surely, at time~$\tmin1$ the graph~$Q_t$ becomes connected and that in fact
the diameter of~$Q_t$ at this point is~$n+1$. Here we generalise this result
by showing that, for any fixed~$k\geq2$, almost surely at time~$\tmink$ the
graph~$Q_t$ acquires the extremely strong property that any two of its
vertices are connected by~$k$ internally vertex-disjoint paths each of length
at most~$n$, except for possibly one, which may have length~$n+1$.  In
particular, the hitting time of $k$-connectedness is almost surely~$\tmink$.
\endabstract
%
% intro.tex
%
\beginsection 1. Introduction

Let~$Q^n$ be the {\it$n$-dimensional cube\/}, the graph
whose vertices are the subsets of~$[n]=\{1,\ldots,n\}$
and where two such vertices are adjacent if and only if
their symmetric difference is a singleton. Note that~$Q^n$
is an $n$-connected graph and that 
both the diameter and the radius of~$Q^n$ are~$n$.
Write~$N=2^n=|Q^n|$ for the order of~$Q^n$
and~$M=n2^{n-1}=e(Q^n)$ for the size of~$Q^n$.
Let~$\tQ=(Q_t)_0^M$ be a {\deffont random
$Q^n$-processes\/}. This is a Markov chain whose states
are spanning subgraphs of~$Q^n$ and~$Q_t$ ($1\leq t\leq
M$) is obtained from~$Q_{t-1}$ by the addition of an
edge of~$Q^n$ not in~$Q_t$, with this edge chosen
uniformly at random from all the possibilities. We are
interested in the behaviour of~$\tQ$ for large~$n$
and, as is usual in the theory of random graphs, 
we use the terms `almost surely' and `almost
every' to mean `with probability tending to~1
as~$n\to\infty$'.

If~$P$ is a non-trivial monotone increasing property of spanning
subgraphs of~$Q^n$ we let~$\tau_P=\tau(P)=\tau(\tQ;P)$ be the hitting
time of~$P$ in the process~$\tQ=(Q_t)_0^M$, that is
$$
\tau_P=\tau(P)=\tau(\tQ;P)=\min\{t:Q_t\hbox{ has~$P$}\}.
$$
Some basic properties~$P$ we shall consider here are ({\it i\/})~the
property~$\{\delta\geq k\}$ that the minimal degree should be at 
least~$k$, ({\it ii\/})~the property~$\{\diam<\infty\}$ that the graph
should be connected, ({\it iii\/})~the property~$\{\rad\leq r\}$ that the
radius should be at most~$r$, ({\it iv\/})~the property~$\{\diam\leq
d\}$ that the diameter should be at most~$d$, and {({\it v\/})}~the property 
that the graph should be $k$-connected. In fact, we shall deal with a much
stronger property than $k$-connectedness but to describe it we need to
introduce some definitions.

For two vertices~$x$, $y$ of a graph~$G$ and an integer~$k\geq1$, let the 
{\deffont$k$-distance\/}~$d^{(k)}(x,y)$ between~$x$ and~$y$ in~$G$ be the 
infimum of the natural numbers~$\ell$ such that~$x$ and~$y$ are joined in~$G$
by~$k$ internally vertex-disjoint paths, each of length at most~$\ell$.
Define the {\deffont$k$-diameter\/}~$\dk(G)$ of~$G$ by setting
$$
\dk(G)=\max\{d^{(k)}(x,y):x,\,y\in G,\,x\neq y\}
$$
when~$G$ is $k$-connected, and~$\dk(G)=\infty$ otherwise.
Clearly~$\diam(G)=\diam^{(1)}(G)$. Here we shall consider the property 
$\{\dk\leq\ell\}$ for spanning subgraphs~$H$ of~$Q^n$ where~$k\geq1$ will
be fixed, independent of~$n$, and~$\ell\in\{n,n+1\}$. Thus, we shall be 
interested in finding a large number of short, internally vertex-disjoint
paths between any pair of vertices of~$H$.

Thus, generally speaking, our central problem here concerns a strong
variant of the concept of connectivity. The reader is referred to
Faudree~{\refFau} for a very recent survey on this variant and related topics.
We remark that problems concerning the existence of families of internally
vertex-disjoint paths of bounded length were first studied by Lov\'asz,
Neumann-Lara, and Plummer~{\refLNLP}. 

A simple corollary of the main results of~{\refBKLc} is that 
$$
\tau(\tQ;\delta\geq1)=\tau(\tQ;\hbox{connectedness})  
                         =\tau(\tQ;\diam\leq n+1)    
                         =\tau(\tQ;\rad=n),    \slabel{Ii}
$$
and that
$$
\tau(\tQ;\diam=n)=\tau(\tQ;\delta\geq2),  \slabel{Iiv}
$$
for almost every~$\tQ$.  Our main results here assert that much more general 
identities than~{\eqnoIi} and~{\eqnoIiv} hold almost surely.  Indeed, for
fixed~$k\geq2$, we show that
$$
\tau(\tQ;\delta\geq k)=\tau(\tQ;\diamk\leq n+1),   \slabel{InA}
$$
and that
$$
\tau(\tQ;\delta\geq k+1)=\tau(\tQ;\diamk\leq n),    \slabel{InB}
$$
for almost every~$\tQ=(Q_t)_0^M$. Thus, typically, at
time~$\tmink=\tau(\tQ;\delta\geq k)$ the graph~$Q_t$ acquires the rather
strong property that any two of its vertices are connected by~$k$ internally
vertex-disjoint paths each of length at most~$n+1$, and at
time~$\tmin{k+1}=\tau(\tQ;\delta\geq k+1)$ the graph~$Q_t$ almost surely
acquires the property that any two of its vertices are connected by~$k$
internally vertex-disjoint paths each of length at most~$n$.

Note that, trivially, if~$H\subset Q^n$ is a subgraph of~$Q^n$ with minimal
degree~$\delta(H)<k$, then~$H$ is not $k$-connected and
hence~$\diamk(H)=\infty$. Thus~$\tau(\tQ;\delta\geq
k)\leq\tau(\tQ;\diamk<\infty)\leq\tau(\tQ;\diamk\leq n+1)$ holds for
every~$\tQ$. Thus the fact that~{\eqnoInA} holds almost surely tells us that,
in a typical $Q^n$-process~$\tQ=(Q_t)_0^M$, the property of~$Q_t$ having
minimal degree at least~$k$, a trivially necessary condition for~$Q_t$ having
finite $k$-diameter, is almost always sufficient to guarantee that~$Q_t$
becomes such that~$\diamk(Q_t)\leq n+1$. Similarly, if a spanning
subgraph~$H\subset Q^n$ of~$Q^n$ has a vertex~$x$ of degree~$k$
and~$y\in\Gamma_H(x)$, then the $k$-distance~$d^{(k)}(x,y\comp)$ between~$x$
and~$y\comp=[n]\setminus y$ is at least~$n+1$. Thus, clearly, we have
that~$\tau(\tQ;\delta\geq k+1)\leq\tau(\tQ;\diamk\leq n)$. Here we prove that
the reverse inequality almost always holds (cf.~{\eqnoInB}). In fact, we prove
a little more. Namely, we show that, when~$t=\tau(\tQ;\delta\geq k+1)$, our
random graph~$Q_t$ is almost surely such that any two of its vertices are
connected by~$k$ internally vertex-disjoint paths all of which have length at 
most~$n$, except for possibly one, which may have length~$n+1$. 


Clearly, our results above imply that for almost every~$\tQ$ we have
$$
\tau(\tQ;k\hbox{-connectedness})=\tau(\tQ;\delta\geq k),  \slabel{IntroHT}
$$
which is in itself a pleasant result, although in view of the analogous result 
for ordinary random graph processes (se Bollob\'as and Thomason~{\refBT}),
and a result of Dyer, Frieze, and Foulds~{\refDFF}, it is not too unexpected.
In~{\refDFF}, the authors study the connectivity of random subgraphs of the
$n$-cube obtained by the random deletion of vertices and edges. An immediate
corollary of their main result is that the limit distribution for the
probability that~$Q_t$ should be $k$-connected is the same as the limit
distribution for the probability that~$Q_t$ should have minimal degree at
least~$k$.  Clearly~{\eqnoIntroHT} above extends this result.

This note is organised as follows. In the next section we state the basic
lemma, Lemma~{\lemmaA}, which is at the heart of our method. This lemma is
proved in~{\refBKLc}. In this section we also give a technical lemma,
Lemma~{\lemmakA}, which follows from Lemma~{\lemmaA}.  In Section~3 we state
and prove our main result, Theorem~{\kcon}. For undefined terms and notation,
the reader is referred to~{\refBBf}. Moreover, we remark that this note is a
sequel to~{\refBKLc}, from where some of the techniques used here are drawn.
Finally, for other work concerning random subgraphs of~$Q^n$ we refer the
reader to~[\refnbAKS, \refnbBBz, \refnbBKL, \refnbKSW, \refnbKSWb] and the
references therein. 
%
% sec2.tex
%
\beginsection 2. The fundamental lemma
 
For the study of random $Q^n$-processes it is often convenient to look first
at the binomial model~$Q_p$ of a random spanning subgraph of the cube~$Q^n$.
As usual, given a graph~$H$ and~$0\leq p\leq1$, we write~$\G(H,p)$ for the
space of random spanning subgraphs~$H_p$ of~$H$ such that every edge of~$H$
belongs to~$H_p$ independently with probability~$p$. Moreover, if~$0\leq t\leq
e(H)$ is an integer, we let~$\G(H,t)$ be the space of all spanning subgraphs
of~$H$ with exactly~$t$ edges, all such subgraphs being equiprobable. We
write~$H_t$ for a typical element of~$\G(H,t)$. For a set~$X$ and~$r\geq0$ we
let~$X^{(r)}$ denote the set of all $r$-subsets of~$X$.  Furthermore,
let~$\qnl$ denote a graph obtained from~$Q^n$ by the deletion of some vertices
in such a way that both~$\emptyset$ and~$[n]$ are left in~$\qnl$ and, for
every~$r$ ($1\le r<n$), no more than~$l$ vertices from~$[n]^{(r)}$ are
missing.  This section is devoted to the study of asymptotic properties of the
probability space~$\G(\qnl,p)$, where~$0\leq p=p(n)\leq1$. The key lemma in
this note is Lemma~{\lemmaA} below, which roughly states that the probability
that two large sets of vertices should not be connected by a short path
in~$\qpl=Q^{n[-l]}_p\in\G(\qnl,p)$ is superexponentially small. The proof of
this lemma appears in~{\refBKLc}, and therefore is omitted.
 
\proclaim Lemma {\lemmaA}. Let~$l\in\N$ be fixed, and
suppose that~$0<\epsilon=\epsilon(n)\leq1$ and that~$(\log\log
n)/n<p=p(n)<1$. Then, for all~$S\subset[n]^{(1)}$
and~$T\subset[n]^{(n-1)}$ with~$|S|$, $|T|\geq n^{(1+\epsilon)/2}$, the
probability that in~$\qpl\in\G(\qnl,p)$ there is no $S$---$T$~path of
length~$n-2$ is bounded from above by~$\exp\{-\epsilon pn(\log
n)/\log\log n\}$.
\endproclaimsquare

A typical application of the above lemma is as follows. We
consider~$x=\emptyset$, $y=[n]\in Q^n$ and generate their neighbourhoods
in~$Q_p$, obtaining~$\GammaQp(x)=S$ and~$\GammaQp(y)=T$, say. Then, if
both~$S$ and~$T$ are large, Lemma~{\lemmaA} tells us that~$x$ and~$y$ fail to
be connected by a path of length~$n$ in~$Q_p$ with a superexponentially small
probability only. Thus most pairs of antipodal, or in fact nearly antipodal,
vertices~$x$, $y\in Q_p$ of almost every~$Q_p$ are connected by paths of
length~$\dQn(x,y)$. However, it is technically a little harder to deal with
pairs~$x$, $y\in Q_p$ that are not so far away from each other. Roughly
speaking, their neighbourhoods in~$Q_p$ may be `facing' the `wrong way', so
that we cannot apply Lemma~{\lemmaA} directly. Lemma~{\lemmakA} below is a
variant of Lemma~{\lemmaA} that is more readily applicable.

For brevity, here and in what follows we use the following somewhat unusual
terminology.  Suppose~$P\subset Q^n$ is an $x$--$y$~path of
length~$\ell=\ell(P)$. We say that~$P$ is a {\deffont short\/} path if either
({\it i\/})~$\dQn(x,y)\geq n-n^{2/3}$ and~$\ell=\dQn(x,y)$, or ({\it
ii\/})~$n/20\leq\dQn(x,y)<n-n^{2/3}$ and~$\ell\leq\dQn(x,y)+4$, or else ({\it
iii\/})~$\dQn(x,y)<n/20$ and~$\ell\leq n/5$.

Clearly, a short $x$--$y$~path has length at most~$n$, and it has length~$n$
if and only if~$x$ and~$y$ are at distance~$n$ in~$Q^n$, that is, if and only
if~$x=y\comp=[n]\setminus y$. 

\proclaim Lemma {\lemmakA}. Let~$l\in\N$ be fixed.
Suppose~$x=\emptyset$ and~$x\neq y\in\qnl$.
Let~$N_x\subset\GammaQn(x)$, $N_y\subset\GammaQn(y)$ with~$|N_x|$,
$|N_y|\geq2n^{2/3}$ be given. Suppose~$1/\log\log\log n\leq
p=p(n)<1$. Then, with probability~$1-\exp\{-\Omega(n\log\log n)\}$,
the graph~$\qpl\in\G(\qnl,p)$ contains an $N_x$---$N_y$~path~$P$
such that~$x$, $y\notin P$ and such that if~$P'=xPy$ is the natural
$x$--$y$~path extending~$P$, then~$P'$ is a short $x$--$y$~path and, moreover, 
contains at most six vertices from~$[n]^{(r)}$ for every~$0\leq r\leq n$.  
\endproclaimsquare

The above result, which may be proved by combining Lemma~{\lemmaA} with some
arguments from Sections~2 and~3 of~{\refBKLc}, is all we shall need in the
sequel. Let us remark in passing that, as it can be easily seen,
if~$\dQn(x,y)=|y|\geq n/20$, then any short $x$--$y$~path~$P\subset Q^n$
contains at most three vertices from each layer~$[n]^{(r)}$ ($0\leq r\leq n$).
Moreover, note that above the constant implicit in the $\Omega$-notation may
depend on~$l$.  Instead of giving a detailed proof for Lemma~{\lemmakA}, as
this would not be particularly enlightening, we only remark that it can be
derived from Lemma~{\lemmaA} in the same way that Lemma~4 in~{\refBKLc} is
derived from Lemma~{\lemmaA} above.  In particular, one needs to use a
straightforward variant of Lemma~3 of~{\refBKLc} for~$\qnl$.
%
% sec3.tex
%
\beginsection 3. The main result

Our aim here is to state and prove the main result of this note,
Theorem~{\kcon}. Before we start, for tidiness, we introduce some further
definitions and notation.  Let~$H\subset Q^n$ be a spanning subgraph of~$Q^n$,
let~$x$, $y\in Q^n$ be two given vertices, and let an integer~$k\geq1$ be
fixed. Suppose~$X\subset\GammaQn(x)$ and~$Y\subset\GammaQn(y)$ are $k$-element
sets of vertices. Then we define the properties~$\cL(x,y)=\cL_k(x,y)$,
$\cL(x,Y)=\cL_k(x,Y)=\cL_k(x,y,Y)$, and~$\cL(X,Y)=\cL_k(X,Y)=\cL_k(x,y,X,Y)$
as follows.   
\item{({\it i\/})}We say that~$H$ has~$\cL(x,y)$ if there are~$k$ short, 
internally vertex-disjoint $x$--$y$~paths in~$H$.
\item{({\it ii\/})}We say that~$H$ has~$\cL(x,Y)$ if there are~$k$
short $x$--$Y$~paths~$P_1,\ldots,P_k$ in~$H-y$ satisfying~$V(P_i)\cap
V(P_j)=\{x\}$ for~$1\leq i<j\leq k$.
\item{({\it iii\/})}We say that~$H$ has property~$\cL(X,Y)$ if there
are~$k$ short, vertex-disjoint $X$---$Y$~paths in~$H-\{x,y\}$.

\noindent
Let us now define some events concerning~$H=Q_p$ and~$Q_t$.  First,
let~$k\geq1$ and~$d\geq1$ be given, and let~$W_d=W_d(H)=\{w\in Q^n:d_H(w)\geq
d\}$. We say that event~$\A(d)=\A_k(d)$ holds in~$H$ if for all~$x$, $y\in
W_d$ the graph~$H$ has~$\cL(x,y)$. Event~$\B(d)=\B_k(d)$ holds in~$H$ if, for
all~$x\in W_d$, $y\in Q^n$, and any $k$-set of vertices $Y\subset
W_d\cap\GammaQn(y)$, the graph~$H$ has~$\cL(x,Y)$. Event~$\C(d)=\C_k(d)$
holds in~$H$ if, for any two vertices~$x$, $y\in Q^n$
with~$\dQn(x,y)\geq10$ and any two $k$-sets of vertices $X\subset
W_d\cap\GammaQn(x)$, $Y\subset W_d\cap\GammaQn(y)$, the
graph~$H$ has property~$\cL(X,Y)$.

The key lemma in the proof of our main result, Lemma~{\lemmakB}, asserts that
for suitably large~$0<p=p(n)<1$ and quite small~$d=d(n)\geq1$ the
events~$\A_k(d)$, $\B_k(d)$, and~$\C_k(d)$ hold with superexponential
probability for any fixed~$k\geq1$.

In what follows, we shall often condition on the event that a certain fixed
pair of vertices of~$Q^n$ should have large degree in~$Q_p$.  Thus, for
convenience, we introduce the following notation.  Let~$x$, $y\in Q^n$ be
fixed. For all~$0\leq d\leq n$ and~$0<p=p(n)<1$, we write~$\G_{x,y,d}(Q^n,p)$
for the conditional probability space obtained from~$\G(Q^n,p)$ by
conditioning on the event $\{\dQp(x),\,\dQp(y)\geq d\}$. Similarly, given a
graph~$H$, two vertices~$x$, $y\in H$ in~$H$, and~$S\subset\Gamma_H(x)$,
$T\subset\Gamma_H(y)$, we let~$\G_{S,T}(H,p)=\G_{x,y;S,T}(H,p)$ be the
conditional space obtained from~$\G(H,p)$ by conditioning on the
event~$\{\Gamma_{H_p}(x)=S,\,\Gamma_{H_p}(y)=T\}$. We may now state and prove
Lemma~{\lemmakB}. (The constants in the $\Omega$-notation below are allowed to
depend on~$k$.)

\proclaim Lemma {\lemmakB}. Suppose an integer~$k\geq1$ is fixed, and
let~$.498<p=p(n)<1$ and~$d=d(n)=3n^{2/3}$. Then
\item{({\it i\/})}the probability that~$\A_k(d)$ holds in~$Q_p\in\G(Q^n,p)$
is~$1-\exp\{-\Omega(n\log\log n)\}$,
\item{({\it ii\/})}the probability that~$\B_k(d)$ holds in~$Q_p\in\G(Q^n,p)$
is~$1-\exp\{-\Omega(n\log\log n)\}$, 
\item{({\it iii\/})}the probability that~$\C_k(d)$ holds in~$Q_p\in\G(Q^n,p)$
is~$1-\exp\{-\Omega(n\log\log n)\}$. 
\endproclaim
\proof
({\it i\/})~Fix two vertices~$x$, $y\in\Qn$ of~$Q^n$. Consider the conditional 
space~$\G_{x,y,d}(\Qn,p)$. To prove~({\it i\/}), it is enough to show that the
probability that~$\Qp\in\G_{x,y,d}(\Qn,p)$ fails to have~$\cL(x,y)=\cL_k(x,y)$ 
is~$\exp\{-\Omega(n\log\log n)\}$.

Without loss of generality, we may assume that~$x=\emptyset$.
Let~$S\subset\GammaQn(x)$, $T\subset\GammaQn(y)$ with~$|S|$, $|T|\geq
d=d(n)=3n^{2/3}$ be fixed and consider the conditional
space~$\G_{S,T}(\Qn,p)$.  It suffices to show that
$$
\P\left\{\cL(x,y)\hbox{ fails in }\Qp\in\G_{S,T}(\Qn,p)\right\}
                            =\exp\{-\Omega(n\log\log n)\}. 
$$

To prove this estimate, first consider the subgraph~$H_0$ of~$\Qn$ spanned by
the edges of the form~$uv$, where either~$u=x$ and~$v\in S$, or else~$u=y$
and~$v\in T$. Find as many internally vertex-disjoint $x$--$y$~paths in~$H_0$
as possible, and suppose that there are $k_0$~such paths, say. Note
that~$0\leq k_0\leq 2$.  Let~$G^{(1)}=\Qnl2$ be the graph obtained from~$\Qn$
by the deletion of the internal vertices in these~$k_0$ paths. We now proceed
to find~$k'=k-k_0$ short $x$--$y$~paths
in~$G^{(1)}_p\in\G_{S_1,T_1}(G^{(1)},p)$ inductively, where~$S_1=S\cap
V(G^{(1)})$ and~$T_1=T\cap V(G^{(1)})$. To do this we use Lemma~{\lemmakA} in
several~$\qnl$. Let~$p_0=p/k'$.

Consider~$H_1=G^{(1)}_{p_0}\in\G_{S,T}(G^{(1)},p_0)$.  By Lemma~{\lemmakA}, we
have that with probability $1-\exp\{-\Omega(n\log\log n)\}$, there is a short
$x$--$y$~path~$P_1$ in~$H_1$ satisfying~$|V(P_1)\cap[n]^{(r)}|\leq6$ for
all~$r$. Assume such a path does exist in~$H_1$.  Now we
consider~$G^{(2)}=\Qnl8$ obtained from~$G^{(1)}=\Qnl2$ by the deletion of the
vertices in~$V(P_1)\setminus\{x,y\}$. Let~$S_2=S\cap V(G^{(2)})$ and
similarly~$T_2=T\cap V(G^{(2)})$.

Now let~$H_2=G^{(2)}_{p_0}\in\G_{S_2,T_2}(G^{(2)},p_0)$. Again by
Lemma~{\lemmakA}, with probability $1-\exp\{-\Omega(n\log\log n)\}$, we find a
short $x$--$y$~path~$P_2$ in~$H_2$ with~$|V(P_2)\cap[n]^{(r)}|\leq6$ for
all~$r$.  Assume such a path~$P_2\subset H_2$ exists, and
consider~$G^{(3)}=\Qnl{14}$ obtained from~$G^{(2)}=\Qnl8$ by the deletion of
the vertices in~$V(P_2)\setminus\{x,y\}$. Let~$S_3=S\cap V(G^{(3)})$
and~$T_3=T\cap V(G^{(3)})$, and proceed as above to find~$P_3$.

Iterating the above procedure~$k'$ times, we find the required
paths~$P_1,\ldots,P_{k'}$ with probability~$1-\exp\{-\Omega(n\log\log
n)\}$ in~$H_1\cup\cdots\cup H_{k'}$. This completes the proof of~({\it i\/}).
\smallskip

({\it ii\/})~A proof of Lemma~{\lemmakB}({\it ii\/}) may be obtained by
coupling the above proof of~({\it i\/}) with ideas from the proof of
Lemma~{\lemmakB}({\it iii\/}) below. Thus we omit the proof of~({\it ii\/}),
and proceed to prove~({\it iii\/}).
\smallskip

({\it iii\/})~Let~$x$, $y\in\Qn$ be such that~$\dQn(x,y)\geq10$, and
suppose that $x_1,\ldots,x_k\in\GammaQn(x)$,
$y_1,\ldots,y_k\in\GammaQn(y)$ are~$2k$ fixed vertices. We may
and shall assume that~$x=\emptyset$. Let~$S_1,\ldots,S_k$
and~$T_1,\ldots,T_k$ be such that~$x\notin
S_i\subset\GammaQn(x_i)$, $y\notin T_i\subset\GammaQn(y_i)$,
and~$|S_i|$, $|T_i|\geq3n^{2/3}-1$ ($1\leq i\leq k$). Let~$\cN$ be the
event
$$
\{\GammaQp(x_i)=S_i\hbox{ and }\GammaQp(y_i)=T_i\hbox{ for all
}1\leq i\leq k\}.
$$
To prove Lemma~{\lemmakB}({\it iii\/}), it suffices to show that 
$$
\P\big(\C(d)\hbox{ fails in }Q_p\in\G(Q^n,p)\,\big|\,\cN\big)
                                       =\exp\{-\Omega(n\log\log n)\}.
$$

Let~$G^{(0)}=Q^n-\{x,y\}=\Qnl1$. We now seek~$k$ vertex-disjoint
short paths in~$G^{(0)}$, say $P_1,\ldots,P_k$, with~$P_i$ ($1\leq i\leq k$) 
connecting~$x_i$ to~$y_i$
in~$G^{(0)}_p\in\G(G^{(0)},p\;\big|\;\cN)$, the space obtained
from~$\G(G^{(0)},p)$ by conditioning on~$\cN$. Let~$p_0=p/k$.

Let~$G^{(1)}=G^{(0)}-\{x_i,y_i:2\leq i\leq k\}$, and
pick~$H_1=G^{(1)}_{p_0}\in\G_{S_1,T_1}(G^{(1)},p_0)$, the space
obtained from~$\G(G^{(1)},p_0)$ by conditioning
on~$\{\Gamma_{G_{p_0}^{(1)}}(x_1)=S'_1,\,\Gamma_{G_{p_0}^{(1)}}(y_1)=T'_1\}$,
where~$S'_1=S_1\cap V(G^{(1)})$ and~$T'_1=T_1\cap V(G^{(1)})$. Then, with
probability~$1-\exp\{-\Omega(n\log\log n)\}$, there is a short
$x_1$--$y_1$~path in~$H_1$ with~$|V(P_1)\cap[n]^{(r)}|\leq12$ for
all~$r$. Indeed, to apply Lemma~{\lemmakA}, we first consider the
automorphism~$\varphi=\varphi_{x_1}$ of the graph~$Q^n$ given by $u\mapsto
u\symmdiff x_1=(u\cup x_1)\setminus(u\cap x_1)$.
Then~$\varphi(x_1)=\emptyset$, and we may apply 
Lemma~{\lemmakA} to obtain, with large probability, a
short $\varphi(x_1)$--$\varphi(y_1)$~path~$P_1'$ in~$\varphi(H_1)$
with~$|V(P_1')\cap[n]^{(r)}|\leq6$ for all~$r$. We then
take the short $x_1$--$y_1$~path~$P_1=\varphi(P_1')$ in~$H_1$, and note
that indeed~$|V(P_1)\cap[n]^{(r)}|\leq12$, since~$x_1$ is a singleton and
hence~$\varphi^{-1}\{[n]^{(r)}\}\subset[n]^{(r-1)}\cup[n]^{(r+1)}$ for
all~$r$. Assume we have found such a path~$P_1$ in~$H_1$.

Now consider~$G^{(2)}=G^{(0)}-\(\{x_i,y_i:1\leq i\leq n,\,i\neq2\}\cup
V(P_1)\)$, $S'_2=S_2\cap V(G^{(2)})$, $T'_2=T_2\cap V(G^{(2)})$. We now
pick~$H_2=G^{(2)}_{p_0}\in\G_{S'_2,T'_2}(G^{(2)},p_0)$ to find a suitable
short $x_2$--$y_2$~path~$P_2$. Iterating the procedure above~$k$ times we
find, with probability~$1-\exp\{-\Omega(n\log\log n)\}$, the~$k$
paths~$P_1,\ldots,P_k$ as required. This completes the proof~({\it iii\/}),
and hence of Lemma~{\lemmakB}.
\endproof

We now give a result for~$\tQ=(Q_t)_0^M$ that is analogous to
Lemma~{\lemmakB}, and proceed to state and prove our main result. 

\proclaim Lemma {\lemmakC}. Suppose an integer~$k\geq1$ is fixed,
and~$d=d(n)=4n^{2/3}$. Then the probability that~$\tQ=(Q_t)_0^M$ is such 
that~$\A_k(d)$, $\B_k(d)$, and~$\C_k(d)$ hold for all~$Q_t$ with~$t\geq.499M$ 
is~$1-\exp\{-\Omega(n\log\log n)\}$.  
\endproclaim
\proof
The argument here is similar to the one in the proof of Corollary~6 
in~{\refBKLc}, and is based on Lemma~{\lemmakB} above. 
Let~$.499\leq
t=t(n)\leq M$ and~$p=p(n)=\(1-((\log n)/M)^{1/2}\)t/M$.  
Then~$\mu=pM=\(1-((\log n)/M)^{1/2}\)t=(1+o(1))t$, and, from standard
estimates for the tail of the binomial distribution, we
have~$|e(Q_p)-\mu|\leq(1/2)((\log n)/M)^{1/2}\mu$ with
probability~$1-n^{-1/20}$.  

In particular, (*)~$t-2(M\log n)^{1/2}\leq e(Q_p)\leq t$ holds for every
fixed~$.499M\leq t\leq M$ with probability~$1-n^{-1/20}$.  Let~$\Gc(Q^n,p)$ be
the conditional probability space obtained from~$\G(Q^n,p)$ conditioning
on~(*).  Note that if~$\A$ is any event concerning~$Q_p\in\G(Q^n,p)$, 
then~$\Pc(\A)\leq(1+o(1))\P(\A)$, where~$\Pc$ denotes the probability
in~$\Gc(Q^n,p)$. Let~$d'=d'(n)=3n^{2/3}$, and let~$\A_0$ be the event
that~$\A_k(d')$, $\B_k(d')$, and~$\C_k(d')$ hold.  Then, by Lemma~{\lemmakB},
we have~$\Pc(\A_0)=1-(1+o(1))n^{-1/20}$. 
Now, we may generate~$Q_t\in\G(Q^n,t)$ by first picking~$Q_p\in\Gc(Q^n,p)$,
and then randomly adding~$t'=t-e(Q_p)$ new edges to~$Q_p$. One may check
that~$Q_{t'}\in\G(Q^n,t')$ is such that its maximal degree~$\Delta(Q_{t'})$
satisfies~$\Delta(Q_{t'})\leq n^{2/3}$ with
probability~$1-\exp\{-\Omega(n^{4/3}/\log n)\}$. Thus~$Q_t$
satisfies~$\A_k(d)$, $\B_k(d)$, and~$\C_k(d)$ with
probability~$1-\exp\{-\Omega(n\log\log n)\}$.  Thus these three properties
hold for all~$Q_t$ in~$\tQ=(Q_t)_0^M$ with~$t\geq.499M$ with
probability~$1-M\exp\{-\Omega(n\log\log n)\}=1-\exp\{-\Omega(n\log\log n)\}$.
\endproof

We have thus arrived at our main result. 
 
\proclaim Theorem {\kcon}. Let an integer~$k\ge 1$ be fixed. 
Almost every random $Q^n$-process~$\tQ=(Q_t)_0^M$ is such that
\item{({\it i\/})}
$\tmin{k}=\tau(\tQ;\delta\ge k)=\tau(\tQ;\dk\le  n+1)$,
\item{({\it ii\/})}
$\tmin{k+1}=\tau(\tQ;\delta\ge k+1)=\tau(\tQ;\dk\leq n)$.
\endproclaim
\proof
It is easily checked that if~$t_0=t_0(n)=\lceil.499M\rceil$, then
a.e.~$Q_{t_0}\in\G(Q^n,t_0)$ is such that any two vertices of degree less 
than~$d=d(n)=4n^{2/3}$ are at distance at least~$10$ and at
most~$n-10$ in~$Q^n$.  Thus we may condition our $Q^n$-process~$\tQ=(Q_t)_0^M$
on being such that (1)~$Q_t$ has this property for all~$t\geq t_0$. Now recall
that by Lemma~{\lemmakC}, for a.e.~$\tQ=(Q_t)_0^M$, we have (2)~the
events~$\A_k(d)$, $\B_k(d)$, and~$\C_k(d)$ hold in~$Q_t$ for all~$t\geq
t_0$. It now suffices to notice that, in any~$\tQ$ satisfying~(1) and~(2),
assertions~({\it i\/}) and~({\it ii\/}) must necessarily hold.

Let us check~({\it i\/}).  Suppose~$\tQ=(Q_t)_0^M$ satisfies~(1) and~(2), 
and let~$t\geq\tmink$. Let~$x$, $y\in Q^n$ be two fixed vertices
of~$Q^n$. We shall check that the $k$-distance~$d^{(k)}_{Q_t}(x,y)$
between~$x$ and~$y$ in~$Q_t$ is at most~$n+1$. If~$\dQt(x)$, $\dQt(y)\geq d$,
then~$\A_k(d)$ tells us that~$\cL_k(x,y)$ holds, and so~$d^{(k)}_{Q_t}(x,y)\leq
n$. Indeed, simply observe that any short path has length at most~$n$. Now
suppose that~$\dQt(x)\geq d$ 
and~$\dQt(y)<d$.  Pick~$k$ vertices~$y_1,\ldots,y_k\in\GammaQt(y)$ and note
that, by~(1), we have~$\dQt(y_i)\geq d$ ($1\leq i\leq k$). Now~$\B_k(d)$ tells
us that~$\cL_k(x,Y)$ holds, where~$Y=\{y_1,\ldots,y_k\}$, and
hence~$d^{(k)}_{Q_t}(x,y)\leq n+1$. In fact, more is true:
either~$d^{(k)}_{Q_t}(x,y)\leq n$, or else~$y$ has degree~$k$ in~$Q_t$
and~$x\comp\in\GammaQt(y)$, and moreover all the~$k$ internally vertex-disjoint
$x$--$y$~paths naturally given by~$\cL_k(x,Y)$ have length at most~$n$, except
for one, which has length~$n+1$. 

Finally, assume that~$\dQt(x)$, $\dQt(y)<d$.  Then by~(1) we have
that~$10\leq\dQn(x,y)\leq n-10$. Pick~$2k$
vertices~$x_1,\ldots,x_k\in\GammaQt(x)$, $y_1,\ldots,y_k\in\GammaQt(y)$. Again
by~(1) we have that~$\dQt(x_i)$, $\dQt(y_i)\geq d$ for all~$1\leq i\leq k$.
Now take~$X=\{x_1,\ldots,x_k\}$, $Y=\{y_1,\ldots,y_k\}$, and note that
then~$\C_k(d)$ tells us that~$\cL_k(X,Y)$ holds in~$Q_t$.
Thus~$d^{(k)}_{Q_t}(x,y)\leq n$. This completes the proof of~({\it i\/}). The
proof of~({\it ii\/}) is similar.
\endproof

We remark that above we in fact proved a statement stronger than~({\it i\/})
for almost every~$\tQ=(Q_t)_0^M$. Indeed, we showed that when~$t=\tmin{k}$ the
graph~$Q_t$ almost surely satisfies the following property: {\sl for any
pair~$x$, $y\in Q_t$ of vertices of~$Q_t$, either {\rm({\it
a\/})}~$d^{(k)}(x,y)\leq n$, or else {\rm({\it b\/})}~one of~$x$ and~$y$,
say~$y$, has degree~$k$ in~$Q_t$ and~$x\comp\in\GammaQt(y)$, and moreover~$x$
and~$y$ are connected by~$k$ internally vertex-disjoint paths all of which
have length at most~$n$, except for one, which has length~$n+1$.\/}

Theorem~{\kcon} has the following immediate consequence. 

\proclaim Corollary {\corkcon}. For almost every random 
$Q^n$-process~$\tQ=(Q_t)_0^M$ and fixed integer~$k\geq1$, we have
$$
\tmink=\tau(\tQ;\delta\geq k)
   =\tau(\tQ;k\hbox{{\rm-connectedness}}) \eqno\sqr
$$
\endproclaim
 
Clearly, one can also define the
{\deffont$k$-radius\/}~$\radk(G)$ of a $k$-connected graph~$G$,
a generalisation of the ordinary radius, by setting
$$
\radk(G)=\min_{x}\max_y\{d^{(k)}(x,y)\}.
$$
Then one can easily combine the arguments in the proofs of Theorem~{\kcon}
above and of Theorem~13 of~{\refBKLc} to show that in almost every random
$Q^n$-process~$\tQ=(Q_t)_0^M$ the hitting time of the property of having
$k$-radius at most~$n$ is~$\tmink=\tau(\tQ;\delta\geq k)$. We omit the
details.

\finalnotes
Acknowledgements. Part of this work was done while the first and
the third authors were visiting the Instituto de Matem\'atica e
Estat\'\i stica, Universidade de S\~ao Paulo. During their visit,
the first author was supported by FAPESP (Proc.~92/3169--8) and The
British Council, and the third author was supported by FAPESP
(Proc.~93/0232--3) and CNPq (Proc.~450293/93--9). The first author
was partially supported by the NSF under grant DMS-8806097, and the
third was partially supported by the~KBN under grant~2~1087~91~01.
\endfinalnotes
%
% \shipoutreferences
%
\firstgofalse\refno=0
\beginreferences
\paper[AKS]  \Aj, \Ko, \Sz
             Largest random component of a $k$-cube
             \Comb\vol2
             1--7, 1982
\book[BBf]  \BB
             Random Graphs
             Academic Press, London~1985, ${\it xvi}+447$pp
\paper[BBz] \BB
             Complete matchings in random subgraphs of the cube
             \RSA\vol1
             95--104, 1990
%\dammit[BK]  \BB, Kohayakawa, Y.
%             On Richardson's model in the cube, %
%             to appear
\paper[BKL] \BB, Kohayakawa, Y., \L uczak, T.
             The evolution of random subgraphs of the cube 
             \RSA\vol3
             55--90, 1992
%\dammit[BKLb] \BB, Kohayakawa, Y., \L uczak, T.
%             On the evolution of random Boolean functions, to appear
\dammit[BKLc] \BB, Kohayakawa, Y., \L uczak, T.
             On the diameter and radius of %
             random subgraphs of the cube, to appear
\dammit[BT]  \BB, Thomason, A.G.
             Random graphs of small order, in {\it Random Graphs~'83\/}, %
             Annals of Discrete Mathematics~28 %
             (Karo\'nski, M., Ruci\'nski, A., eds), %
             North-Holland, Amsterdam~1985, pp.~47--97
%\paper[Bua]  Burtin, Yu.D.
%             On extreme metric characteristics of a random graph~I. %
%             Asymptotic estimates
%             Mathematical Notes\vol19
%             710--725, 1974
%\paper[Bub]  Burtin, Yu.D.
%             On extreme metric characteristics of a random graph~II. %
%             Limit distributions
%             Mathematical Notes\vol20
%             83--101, 1975
\dammit[DFF] Dyer, M.E., Frieze, A.M., Foulds, L.R.
             On the strength of connectivity of %
             random subgraphs of the $n$-cube, %
             in {\it Random Graphs~'85\/}, %
             Annals of Discrete Mathematics~33 %
             (Karo\'nski, M., Palka, Z., eds), %
             North-Holland, Amsterdam~1987, pp.~17--40
\dammit[Fau] Faudree, R.J.
             Some strong variations of connectivity, %
             in {\it Combinatorics\/}, {\it Paul Erd\H os is Eighty\/}, %
             Volume~1 (Mikl\'os, D., S\'os, V.T., Sz\H onyi, T., eds), %
             Keszthely (Hungary)~1993, pp.~125--144
%\dammit[FP]  Fill, J.A., Pemantle, R.
%             Percolation, first-passage percolation, and covering times %
%             for Richardson's model on the $n$-cube, %
%             to appear
%\paper[Ka]   Kostochka, A.V.
%             Maximum matchings and connected components of random %
%             subgraphs of the $n$-cube (in Russian)
%             Methods Discrete Anal., Study Boolean Function Graphs\vol48
%             42--70, 1989
%\paper[Kb]   Kostochka, A.V.
%             Matchings in Random Spanning subgraphs of cubelike graphs
%             \RSA\vol1
%             277--285, 1990
\dammit[KSW] Kostochka, A.V., Sapozhenko, A.A., Weber, K.
             On random cubical graphs, in {\it Fourth %
             Czechoslovakian Symposium on Combinatorics, Graphs %
             and Complexity\/} (\Ne, Fiedler, M., eds), %
             Annals of Discrete Mathematics~51, %
             North--Holland, Amsterdam~1992, pp.~155--160
\paper[KSWb] Kostochka, A.V., Sapozhenko, A.A., Weber, K.
             Radius and diameter of random subgraphs of the hypercube
             \RSA\vol4
             215--229, 1993
\paper[LNLP] Lov\'asz, L., Neumann-Lara, V., Plummer, M.
             Mengerian theorems for paths of bounded length
             \PMH\vol9
             269--276, 1978
%\dammit[SW]  Sapozhenko, A., Weber, K.
%             Radius and diameter of random subgraphs %
%             of the hypercube, to appear
\endreferences
\bye
% Local Variables: 
% mode: tex
% TeX-master: t
% End: 
