%%%  hamming.tex
%%%  The second largest component in the supercritical 2D Hamming graph
%%%  Remco van der Hofstad, Malwina J. Luczak and Joel Spencer


\documentclass[12pt,reqno,tbtags]{amsart}
%\usepackage{amsmath}
\usepackage{amssymb}
%\usepackage[notcite,notref]{showkeys-hara} % shows labels
\numberwithin{equation}{section}

\oddsidemargin -8mm
\evensidemargin -8mm
\topmargin -4mm
%\headheight 4mm
%\headsep 3mm
\textheight 650pt
\textwidth 500pt

%\setcounter{secnumdepth}{1}

\newcommand{\halmos}{\rule{1ex}{1.4ex}}
\newcommand{\proofbox}{\hspace*{\fill}\mbox{$\halmos$}}
%\newcommand{\qed}{\hfill\mbox{$\;\;\;\Box$}}
%%%%% THEOREMS ETC %%%%%
%\newenvironment{proof}{\noindent {\bf
%Proof}.}{\proofbox\par\smallskip\par}
\newenvironment{proofof}[1]{\noindent {\it
Proof of #1}.}{\proofbox\par\smallskip\par}
\newenvironment{prf}{\noindent {\it
Proof}.}{\proofbox\par\smallskip\par}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{assumption}[theorem]{Assumption}
\newtheorem{condition}[theorem]{Condition}
%\newtheorem{Alg}[theorem]{Algorithm}

\theoremstyle{definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{definition}{Definition}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{remarks}[theorem]{Remarks}
%\newtheorem*{personal}{Personal remark}
\newtheorem{tom}{}
\newtheorem*{acks}{Acknowledgements}
\newtheorem*{ack}{Acknowledgement}

\theoremstyle{remark}

%\newenvironment{acks}{\section*{Acknowledgement}}{}
%\newenvironment{algo}{\begin{enumerate}}{\end{enumerate}}

\newenvironment{romenumerate}{\begin{enumerate}% gives (i), (ii) etc.
 \renewcommand{\labelenumi}{\textup{(\roman{enumi})}}%
 \renewcommand{\theenumi}{\textup{(\roman{enumi})}}%
 }{\end{enumerate}}

\newenvironment{thmxenumerate}{\begin{enumerate}% gives (i), (ii) etc.
 \renewcommand{\labelenumi}{\textup{(\roman{enumi})}}%
 \renewcommand{\theenumi}{\textup{(\roman{enumi})}}%
\setlength{\leftmargin}{0pt}
\setlength{\itemindent}{0pt}
 }{\end{enumerate}}

\newcounter{thmenumerate}
\newenvironment{thmenumerate}
{\setcounter{thmenumerate}{0}%
 \def\item{\ifnum\thethmenumerate=0\else\par\fi %\noindent\fi
 \addtocounter{thmenumerate}{1}\textup{(\roman{thmenumerate})\enspace}}}
{}


\newcounter{xenumerate}
\newenvironment{xenumerate}
  {\begin{list}
    {\upshape(\roman{xenumerate})}
    {\setlength{\leftmargin}{0pt}
     \setlength{\rightmargin}{0pt}
     \setlength{\labelwidth}{0pt}
     \setlength{\itemindent}{\labelsep}
     \setlength{\topsep}{0pt}
     \usecounter{xenumerate}} }
  {\end{list}}

\newcommand\pfitem[1]{\par(#1):}

\newcommand\step[2]{\smallskip\noindent\emph{Step #1: #2} \noindent}

\newcommand{\m}[1]{\marginpar{\tiny{#1}}}
%\newcommand{\halmos}{\rule{1ex}{1.4ex}}
%\newcommand{\proofbox}{\hspace*{\fill}\mbox{$\halmos$}}
%\newenvironment{proofof}[1]{\noindent {\bf
%Proof of #1}.}{\proofbox\par\smallskip\par}

\newcommand\REM[1]{\texttt{[#1]}\marginal{XXX}}
\newcommand{\refT}[1]{Theorem~\ref{#1}}
\newcommand{\refC}[1]{Corollary~\ref{#1}}
\newcommand{\refCN}[1]{Condition~\ref{#1}}
\newcommand{\refL}[1]{Lemma~\ref{#1}}
\newcommand{\refR}[1]{Remark~\ref{#1}}
\newcommand{\refS}[1]{Section~\ref{#1}}
\newcommand{\refA}[1]{Assumption~\ref{#1}}
\newcommand{\refP}[1]{Problem~\ref{#1}}
\newcommand{\refE}[1]{Example~\ref{#1}}
\newcommand{\refF}[1]{Figure~\ref{#1}}
%\newcommand{\refConj}[1]{Conjecture~\ref{#1}}
\newcommand{\refand}[2]{\ref{#1} and~\ref{#2}}


\begingroup
  \count255=\time
  \divide\count255 by 60
  \count1=\count255
  \multiply\count255 by -60
  \advance\count255 by \time
  \ifnum \count255 < 10 \xdef\klockan{\the\count1.0\the\count255}
  \else\xdef\klockan{\the\count1.\the\count255}\fi
\endgroup

% further AmSTeX adaptions
\newcommand\nopf{\qed}   % for theorem without proof
\newcommand\noqed{\renewcommand{\qed}{}} % for proof with explicit \qed
\newcommand\qedtag{\tag*{\qedsymbol}}



%\DeclareMathOperator*{\sumsum}{\sum\sum}
\DeclareMathOperator*{\sumx}{\sum\nolimits^{*}}
\DeclareMathOperator*{\sumxx}{\sum\nolimits^{**}}
\DeclareMathOperator*{\sumy}{\sum\nolimits^{*}}
\DeclareMathOperator*{\sumyq}{\sum\nolimits^{*\!\!\!}}
\newcommand{\sumi}{\sum_{i=0}^\infty}
\newcommand{\sumj}{\sum_{j=0}^\infty}
\newcommand{\sumk}{\sum_{k=0}^\infty}
\newcommand{\summ}{\sum_{m=0}^\infty}
\newcommand{\sumn}{\sum_{n=0}^\infty}
\newcommand{\sumr}{\sum_{r=0}^\infty}
\newcommand{\sumoo}{\sum^\infty}
\newcommand{\sumin}{\sum_{i=1}^n}

\newcommand\set[1]{\ensuremath{\{#1\}}}
\newcommand\bigset[1]{\ensuremath{\bigl\{#1\bigr\}}}
\newcommand\Bigset[1]{\ensuremath{\Bigl\{#1\Bigr\}}}
\newcommand\biggset[1]{\ensuremath{\biggl\{#1\biggr\}}}
\newcommand\xpar[1]{(#1)}
\newcommand\bigpar[1]{\bigl(#1\bigr)}
\newcommand\Bigpar[1]{\Bigl(#1\Bigr)}
\newcommand\biggpar[1]{\biggl(#1\biggr)}
\newcommand\bigsqpar[1]{\bigl[#1\bigr]}
\newcommand\Bigsqpar[1]{\Bigl[#1\Bigr]}
\newcommand\biggsqpar[1]{\biggl[#1\biggr]}
\def\rompar(#1){\textup(#1\textup)}    % usage: \rompar(...)
\newcommand\xfrac[2]{#1/#2}
\newcommand\xpfrac[2]{(#1)/#2}
\newcommand\parfrac[2]{\Bigpar{\frac{#1}{#2}}}
\newcommand\expX[1]{\exp\Bigl(#1\Bigr)}
\newcommand\expx[1]{\exp\bigl(#1\bigr)}
\newcommand\expQ[1]{e^{#1}}
\def\xexp(#1){e^{#1}}
\newcommand\ceil[1]{\lceil#1\rceil}
\newcommand\floor[1]{\lfloor#1\rfloor}
\newcommand\fract[1]{\{#1\}}
%\newcommand\setx[1]{\set{1,\dots,#1}}
\newcommand\setn{\set{1,\dots,n}}
\newcommand\ntoo{\ensuremath{{n\to\infty}}}
\newcommand\Ntoo{\ensuremath{{N\to\infty}}}
\newcommand\asntoo{\text{as }\ntoo}
\newcommand\ktoo{\ensuremath{{k\to\infty}}}
\newcommand\xtoo{\ensuremath{{x\to\infty}}}
\newcommand\bmin{\wedge}
\newcommand\norm[1]{\|#1\|}
\newcommand\bignorm[1]{\bigl\|#1\bigr\|}
\newcommand\Bignorm[1]{\Bigl\|#1\Bigr\|}
\newcommand\downto{\searrow}

\newcommand\iid{i.i.d.\spacefactor=1000}
\newcommand\ie{i.e.\spacefactor=1000}
\newcommand\eg{e.g.\spacefactor=1000}
\newcommand\viz{viz.\spacefactor=1000}
\newcommand{\as}{a.s.\spacefactor=1000}
\newcommand{\aex}{a.e.\spacefactor=1000}
\renewcommand{\ae}{\vu}  % som felkoll

\newcommand\ii{\mathrm{i}}
\newcommand\tN{\ensuremath{\tilde{N}}}
\newcommand\tvep{\ensuremath{\tilde{\vep}}}

\newcommand{\tend}{\longrightarrow}
\newcommand\dto{\overset{\mathrm{d}}{\tend}}
\newcommand\pto{\overset{\mathrm{p}}{\tend}}
\newcommand\asto{\overset{\mathrm{a.s.}}{\tend}}
\newcommand\eqd{\overset{\mathrm{d}}{=}}
\newcommand\neqd{\overset{\mathrm{d}}{\neq}}

\newcommand\Op{O_{\mathrm p}}
\newcommand\op{o_{\mathrm p}}


\newcommand\bbR{\mathbb R}
\newcommand\bbC{\mathbb C}
\newcommand\bbN{\mathbb N}
\newcommand\bbT{\mathbb T}
\newcommand\bbZ{\mathbb Z}

\renewcommand\Re{\operatorname{Re}}

\newcommand\E{\operatorname{\mathbb E{}}}
\renewcommand\P{\operatorname{\mathbb P{}}}
\newcommand\Var{\operatorname{Var}}
\newcommand\Cov{\operatorname{Cov}}
\newcommand\Corr{\operatorname{Corr}}
\newcommand\Exp{\operatorname{Exp}}
\newcommand\Po{\operatorname{Po}}
\newcommand\Bi{\operatorname{Bi}}
\newcommand\Be{\operatorname{Be}}
\newcommand\Ge{\operatorname{Ge}}
\newcommand\NBi{\operatorname{NegBin}}
%\newcommand\PD{\operatorname{PD}}
\newcommand\Res{\operatorname{Res}}
\newcommand\fall[1]{^{\underline{#1}}}
\newcommand\rise[1]{^{\overline{#1}}}
%\newcommand\Int{\operatorname{Int}}
%\newcommand\arg{\operatorname{arg}}

\newcommand\ga{\alpha}
\newcommand\gb{\beta}
\newcommand\gd{\delta}
\newcommand\gD{\Delta}
\newcommand\gf{\varphi}
\newcommand\gam{\gamma}
\newcommand\gG{\Gamma}
\newcommand\gk{\varkappa}
\newcommand\gl{\lambda}
\newcommand\gL{\Lambda}
\newcommand\go{\omega}
\newcommand\gO{\Omega}
\newcommand\gs{\sigma}
\newcommand\gss{\sigma^2}
%\newcommand\gt{\tau}
\newcommand\eps{\varepsilon}
\newcommand\ep{\varepsilon}
\renewcommand\phi{\varphi}

\newcommand\bJ{\bar J}

%\newcommand\cA{\mathcal A}
\newcommand\cB{\mathcal B}
%\newcommand\cC{\mathcal C}
\newcommand\cD{\mathcal D}
\newcommand\cE{\mathcal E}
%\newcommand\cF{\mathcal F}
%\newcommand\cG{\mathcal G}
%\newcommand\cH{\mathcal H}
%\newcommand\cI{\mathcal I}
%\newcommand\cJ{\mathcal J}
\newcommand\cL{{\mathcal L}}
%\newcommand\cM{\mathcal M}
%\newcommand\cN{\mathcal N}
\newcommand\cP{\mathcal P}
%\newcommand\cR{{\mathcal R}}
%\newcommand\cQ{\mathcal Q}
\newcommand\cS{{\mathcal S}}
\newcommand\cT{{\mathcal T}}
\newcommand\cV{\mathcal V}
%\newcommand\cX{{\mathcal X}}

%\newcommand\tJ{{\tilde J}}

\newcommand\F{\ensuremath F(\cn,p)}

\newcommand\ett[1]{\boldsymbol1[#1]}
%\newcommand\ett{\mathbf1}
\newcommand\etta{\boldsymbol1}
\def\[#1]{[\![#1]\!]}

\newcommand\limn{\lim_{n\to\infty}}
\newcommand\limN{\lim_{N\to\infty}}

\newcommand\qq{^{1/2}}
\newcommand\qqi{^{-1/2}}
\newcommand\qi{^{-1}}
\newcommand\qii{^{-2}}
%\newcommand\gsi{\sigma^{-1}}

\renewcommand{\=}{:=}

\newcommand\intoi{\int_0^1}
\newcommand\intoo{\int_0^\infty}
\newcommand\intoooo{\int_{-\infty}^\infty}
\newcommand\oi{[0,1]}
\newcommand\ooo{[0,\infty)}

\newcommand\dtv{d_{\mathrm{TV}}}

\newcommand\dd{\,d}

\newcommand{\pgf}{probability generating function}
\newcommand{\mgf}{moment generating function}
\newcommand{\chf}{characteristic function}
\newcommand{\ui}{uniformly integrable}
\newcommand\rv{random variable}
\newcommand\lhs{left hand side}
\newcommand\rhs{right hand side}

\newcommand\PB{\textup{\textsf{PB}}}
\newcommand\UD{\textup{\textsf{UD}}}
\newcommand\ED{\textup{\textsf{ED}}}
\newcommand\dw{d_W}
\newcommand\ltx{<\!}
\newcommand\gex{\ge\!}
\newcommand\kcore{$k$-core}
\newcommand\gnp{\ensuremath{G(n,p)}}
\newcommand\gnm{\ensuremath{G(n,m)}}
\newcommand\gnl{\ensuremath{G(n,\gl/n)}}
\newcommand\gnd{\ensuremath{G(n,(d_i)_1^n)}}
\newcommand\gndx{\ensuremath{G^*(n,(d_i)_1^n)}}
\newcommand\crk{\ensuremath{\mathrm{Core}_k}}
\newcommand\crkx{\ensuremath{\mathrm{Core}^*_k}}
\newcommand\nn{^{(n)}}
\newcommand\et{e^{-t}}
%\newcommand\tij{T_i^{(j)}}
\newcommand\tij{T_i}
%\newcommand\blp{B_{lp}}
\newcommand\psij{\psi_{j}}
\newcommand\psik{\psi_{k}}
\newcommand\psiki{\psi_{k-1}}
\newcommand\gamk{\gamma_{k}}
\newcommand\glk{\lambda_{k}}
\newcommand\muxx[1]{\mu^{#1}}
\newcommand\pmax{\widehat p}
\newcommand\tnxt{N^{(\ceil x)}}
\newcommand\Cv{\ensuremath{C({\bf v})}}
\newcommand\cv{\ensuremath{|C({\bf v})|}}

\newcommand{\vv}{\ensuremath {\bf v}}


\newcommand\whp{\textbf{whp}}
\newcommand\wvhp{\textbf{wvhp}}
%QQQ

\newcommand{\Holder}{H\"older}
\newcommand\CS{Cauchy--Schwarz}
\newcommand\CSineq{\CS{} inequality}
\newcommand{\Levy}{L\'evy}
%\newcommand{\Takacs}{Tak\'acs}

\newcommand{\maple}{\texttt{Maple}}

% Marginal notes and labelling macros
%\newcommand\marginal[1]{\marginpar{\raggedright\parindent=0pt\tiny #1}}

\newcommand\MJL{\marginal{MJL}}
\newcommand{\ind}{\mathbb{I}}

\newcommand\marginal[1]{\marginpar{\raggedright\parindent=0pt\tiny #1}}
%\newcommand\SJ{\marginal{SJ}}
%\newcommand\MJL{\marginal{MJL}}

%\def\nomarginal{%
% \def\marginal##1{\ignorespaces}%
% \overfullrule=0pt \message{*** no marginals or black boxes ***}}

\newcommand\XXX{XXX \marginal{XXX}}
%\newcommand{\mer}[1]{\texttt{[#1]}\marginal{MER!}}
%\newcommand\REV{\marginal{Revidera!!}}
%\newcommand\REM[1]{\texttt{[#1]}\marginal{XXX}}
\newcommand\REMM[1]{{\raggedright\texttt{[#1]}\par\marginal{XXX}}}
\newenvironment{OLD}{\Small \REM{Old stuff to be edited:}\par}{}
\newcommand\REMRM[1]{}
\newenvironment{comment}{\setbox0=\vbox\bgroup}{\egroup} %deletes!
%\newc

%\def\nomarginal{%
% \def\marginal##1{\ignorespaces}%
% \overfullrule=0pt \message{*** no marginals or black boxes ***}}

%\newcommand\XXX{XXX \marginal{XXX}}
%\newcommand{\mer}[1]{\texttt{[#1]}\marginal{MER!}}
%\newcommand\REV{\marginal{Revidera!!}}
%\newcommand\REM[1]{\texttt{[#1]}\marginal{XXX}}
%\newenvironment{OLD}{\Small \REM{Old stuff to be edited:}\par}{}
%\newcommand\kolla[1]{\marginal{KOLLA!}}

%\newcommand\citex{\REM}
%\newcommand\citex[1]{\texttt{[#1]}}
%\newcommand\refx[1]{\texttt{[#1]}}
%\newcommand\xref[1]{\texttt{(#1)}}


%Macros Remco

\newcommand\Vto{\ensuremath{{V \to\infty}}}
\newcommand{\gr}{{\mathbb G}}
\newcommand{\eq}{\begin{equation}}
\newcommand{\en}{\end{equation}}
\newcommand{\lbeq}[1]{\label{#1}}
\newcommand{\refeq}[1]{(\ref{#1})}
\newcommand{\Cmax}{{\mathcal C}_{\rm max}}
\newcommand{\eqn}[1]{\eq #1 \en}
\newcommand{\cn}{\Omega}
\newcommand{\vep}{\varepsilon}
\newcommand{\prob}{{\mathbb P}}
\newcommand{\expec}{{\mathbb E}}
\newcommand{\R}{{\mathbb R}}
\newcommand{\var}{{\rm Var}}
\newcommand{\sss}{\scriptscriptstyle}
\newcommand{\rembox}[1]{
\[
\boxed{\mbox{{\bf #1}}}
\]}
\newcommand{\sT}{{\sss T}}

\newcommand{\eqan}[1]
{\begin{align}
#1
\end{align}
}
\newcommand{\conn}{\longleftrightarrow}
\newcommand{\conns}{\leftrightarrow}
\newcommand{\nc}  { \conn  {\hspace{-2.7ex} /} \hspace{1.8ex}   }
\newcommand{\ncs}  { \conns  {\hspace{-1.0ex} /} \hspace{0.3ex}   }
\renewcommand{\Pr}{{\mathbb P}_p}
\newcommand{\Zbar}{{\bar Z}}
\newcommand{\sV}{{\sss V}}


\newcommand{\een}{\end{enumerate}}
\newcommand{\noi}{\noindent}
\newcommand{\ra}{\rightarrow}
\newcommand{\sig}{\sigma}
%\newcommand{\eps}{\varepsilon}
\newcommand{\del}{\delta}
\newcommand{\Del}{\Delta}
\newcommand{\TREE}{\mbox{TREE}}
\newcommand{\lam}{\lambda}
\newcommand{\ah}{\alpha}
%\newcommand{\gam}{\gamma}
\newcommand{\ben}{\begin{enumerate}}
\newcommand{\beq}{\begin{equation}}
\newcommand{\eeq}{\end{equation}}
\newcommand{\bec}{\begin{center}}
\newcommand{\ece}{\end{center}}
\newtheorem{conjecture}{Conjecture}
%\newtheorem{definition}{Definition}
\newtheorem{define}{Definition}
%\newtheorem{theorem}{Theorem}[section]
\newtheorem{claim}{Claim}[theorem]
\newtheorem{prop}[theorem]{Proposition}
%\newtheorem{remark}[theorem]{Remark}
%\newtheorem{lemma}[theorem]{Lemma}
%\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{guess}[theorem]{Conjecture}


\begin{document}
\title{The second largest component in the supercritical 2D Hamming graph}
%\linebreak The supercritical phase}

\date{April 28, 2008 (\today)}

\author{Remco van der Hofstad}
\address{Department of Mathematics and
        Computer Science, Eindhoven University of Technology,
        5600 MB Eindhoven, The Netherlands.}
\email{rhofstad@win.tue.nl}
\urladdr{http://www.win.tue.nl/$\sim$rhofstad}

\author{Malwina J. Luczak}
\address{Department of Mathematics, London School of Economics,
  Houghton Street, London WC2A 2AE, United Kingdom}
\email{m.j.luczak@lse.ac.uk}
\urladdr{http://www.lse.ac.uk/people/m.j.luczak@lse.ac.uk/}

\author{Joel Spencer}
\address{Computer Science and Mathematics Departments, New York
University, Mercer Street,
         New York City, United States of America.}
\email{spencer@courant.nyu.edu}
\urladdr{http://cs.nyu.edu/cs/faculty/spencer/}

\keywords{random graphs, percolation, phase transition, scaling window}
\subjclass[2000]{05C80}
%{60C05 (68P10,68W40)} %%{Primary: <subject>; Secondary: <subject>}


\begin{abstract}
The $2$-dimensional Hamming graph $H(2,n)$ consists of the $n^2$
vertices $(i,j)$, $1\leq i,j\leq n$, two vertices being adjacent
when they share a common coordinate.   We examine random
subgraphs of $H(2,n)$ in percolation with edge probability $p$, so that the average
degree $2(n-1)p=1+\varepsilon$.  Previous work~\cite{hl} had shown that
in the barely supercritical region $n^{-2/3}\ln^{1/3}n\ll \varepsilon
\ll 1$ the largest component has size $\sim 2\varepsilon n$. Here we
show that the second largest component has size bounded by 
$\varepsilon^{-2}\log(n^2 \varepsilon^3)$, so that the dominant component 
has emerged. This result also suggests that a {\it discrete duality
principle} may hold, whereby, after removing the largest connected component
in the supercritical regime, the remaining random subgraphs behave as in
the subcritical regime.

% We study random subgraphs of the
%2-dimensional Hamming graph $H(2,n)$, which is the Cartesian product
%of two complete graphs on $n$ vertices. Let $p$ be the edge
%probability, and write $p=\frac{1+\vep}{2(n-1)}$ for some $\vep\in
%\R$. A law of large numbers for the largest connected component size
%in the supercritical phase was obtained in~\cite{hl}, and that
%component turns out to have $2 \vep n^2 (1+o(1))$ vertices with high
%probability.
%
%In this paper we prove that, when $\vep\gg (\log{V})^{1/3} V^{-1/3}$,
%then the second largest connected component has size close to $\vep^{-2}$
%with high probability.

\end{abstract}

\maketitle

\section{Introduction and main result}\label{S:intro}


In their seminal work~\cite{er}, Paul Erd\H{o}s and Alfred R\'enyi
noted with surprise the development of a {\em giant component} in
the independent random graph $G(n,p)$.  When the average degree is
$(n-1)p=1+\vep$, and $\vep$ is positive and fixed (independent of
$n$), then the largest component will contain a positive proportion
of the vertices while the size of the second largest component is
only logarithmic in $n$. Today we see this as a phase transition
phenomenon exhibiting what mathematical physicists call `mean-field'
behaviour.

For many years, there has been great interest in the {\em barely
supercritical} phase of $G(n,p)$, that is the range of $p$ values
given by $p=\frac{1+\vep}{n}$ where $\vep=\vep(n)$ satisfies
$n^{-1/3}\ll \vep = o(1)$.  For convenience, we also write
$\vep=\lambda n^{-1/3}$, where $\lambda\rightarrow +\infty$, but does
so more slowly than $n^{1/3}$. In this phase the {\em dominant
component} has already appeared. We actually know quite precisely
that the largest component, $C_{\sss (1)}$, satisfies $|C_{\sss (1)}|\sim
2\vep n=2\lambda n^{2/3}$ with probability tending to 1 as $n \to
\infty$; and that the second largest component, $C_{\sss (2)}$, satisfies
$|C_{\sss (2)}| = \Theta(\vep^{-2}\log(n\vep^3))=
\Theta(n^{2/3}\lambda^{-2}\ln\lambda)$ with probability tending to 1
as $n \to \infty$. Also, we know that $|C_{\sss (2)}|\ll n^{2/3} \ll
|C_{\sss (1)}|$. Further, as $\lambda$ increases, the largest component
increases in size while the second largest diminishes in size.  
(Actually, the second largest component is being frequently 
`gobbled up' by the dominant component, usually leaving 
a smaller component as the new second component.)  
We feel, speaking quite generally, that an intensive
study of the second largest component is vital to enhancing our
understanding of percolation phenomena.

The second largest component, we feel, should grow until the random
structure reaches a {\em critical window}.  In that critical window,
which, for $G(n,p)$, means $\lambda$ fixed, the first and second
largest components exhibit complex chaotic behaviour. But in the
barely supercritical phase, just after the critical window, the
dominant, or `giant', component will have asserted itself.


%In this paper our object of study is the $2$-dimensional Hamming
%graph $H(n,2)$.  This graph has $n^2$ vertices $(i,j)$, $1\leq i,j
%\leq n$.  Vertices $(i,j),(i',j')$ are adjacent if and only if
%either $i=i'$ or $j=j'$. Pictorially, $H(2,n)$ consists of the
%$n\times n$ lattice with each horizontal and vertical line being a
%complete graph. We set $\cn =2(n-1)$ to be the vertex degree in
%$H(2,n)$. We examine the random subgraph of $H(2,n)$ with
%probability $p$. We parametrise $p= \frac{1+\varepsilon}{2(n-1)}$ so
%that a vertex will have average degree $1+\varepsilon$.

In the present paper, our object of study is the $2$-dimensional
Hamming graph $H(2,n)$.  The $n^2$ vertices of this graph can be
represented as ordered pairs $(i,j)$, $1\leq i,j \leq n$.  Vertices
$(i,j)$ and $(i',j')$ are adjacent if and only if either $i=i'$ or $j=j'$.
Pictorially, $H(2,n)$ consists of an $n\times n$ lattice with each
horizontal and vertical line being a complete graph. We write $\cn
=2(n-1)$ for the vertex degree in $H(2,n)$. We examine random
subgraphs of $H(2,n)$ in independent percolation with edge probability
$p$; that is, each edge is kept with probability $p$ and removed
with probability $1-p$, independently of all other edges. We set
$p_c=\frac{1}{\cn}$, which will act as our critical probability;
a justification for this definition of critical probability lies in
the recent results in~\cite{bchss1,bchss2,hl}. We parametrise $p=
\frac{1+\vep}{\cn}$ so that the average vertex degree is $1+\vep$.
Throughout the rest of the paper $C_{\sss (1)}, C_{\sss (2)}$ will refer to the
largest and second largest components respectively of the Hamming
graph $H(2,n)$. Also, we shall use the phrase `with high probability'
(\whp{}) to mean `with probability $1-o(1)$ as $n \to \infty$'.

This work continues the exploration of van der Hofstad and
Luczak~\cite{hl}. It was shown therein that, when $n^{-2/3}(\log
n)^{1/3} \ll \vep \ll 1$, the largest component has size $\sim
2\vep n^2$.   The general sense of a mean-field percolation event in
percolation on a graph with $V$ vertices is that there is a critical
probability $p_c$, and that the barely supercritical phase occurs
when $p=p_c(1+\vep)$ and $V^{-1/3} \ll \vep \ll 1$. This is the case
in the Erd\H{o}s-R\'enyi phase transition with $V=n$. For the
$H(2,n)$ phase transition, $V=n^2$, and so the above results, up to a
logarithmic term, fit the mean-field paradigm. Here we study the
second largest component in percolation on $H(2,n)$ in the barely
supercritical region.  In this aspect we are also able to, again up to
a logarithmic term, fit the mean-field paradigm. In the mean-field 
picture of random graphs, the structure remaining when the dominant
component is removed for $p=\frac{1+\vep}{n}$ where $\vep=\vep(n)
\rightarrow \infty$  is like  the largest connected component in 
the subcritical regime with $p=\frac{1-\vep}{n}$. It is well known
that in this regime in $G(n,p)$, the second largest component
is of order $\vep^{-2} \log (n \varepsilon^3)$. An analogous upper bound 
for the graph $H(2,n)$ is the content of our main result.

\begin{theorem}
[The second component in the supercritical phase for $H(2,n)$]
\label{thm-main} Consider the 2-dimensional Hamming graph %\linebreak
$H(2,n)$. Let $p=p_c +\frac{\vep}{\cn}$ and let
$n^{-2/3}(\log{n})^{1/3}\ll \vep \ll 1$. Then with high probability
    \eqn{
    |C_{\sss (2)}| \le 2^4 \vep^{-2} \log (n^2\varepsilon^3).
    }
\end{theorem}

In particular, this result implies that the ratio of the sizes of
the second and first largest components tends to zero in this regime, a salient
feature of the barely supercritical phase.  We feel that this
feature should hold even without the logarithmic separation from
criticality. That is, parametrise $2(n-1)p=1+\varepsilon$ and assume
only $n^{-2/3}\ll \varepsilon \ll 1$. We conjecture,
following~\cite{hl}, that the largest component will have size $\sim
2\varepsilon n^2$.  We further conjecture that the second largest
component will have size $\ll n^{2/3}$, asymptotically smaller than
the largest component. Let us note at this point that the
logarithmic gap from the critical window (defined as
in~\cite{bchss1,bchss2,bchss3}) has recently been removed by Asaf
Nachmias~\cite{n07}; however, he does not establish a law of large
numbers for the giant component, and he does not consider the second
largest component.

\section{Preliminaries}

In this section, 
we establish a lemma for a class of branching processes that
will play a key role in our proofs.

We start with an inequality concerning deviations of binomial
%and Poisson
random variables below their mean.
%\begin{lemma}
%\label{lem.bin}
%If $X$ is a binomial %or Poisson
%random variable with mean $\mu$, then for each $0 \le
%\varepsilon \le 1$ we have
%\begin{equation} %\label{binpo1}
% \P (X -\mu \le - \varepsilon \mu) \le  e^{- \frac12 \varepsilon^2 \mu}
%\end{equation}
%and
%\begin{equation} %\label{binpo2}
% \P (X -\mu \ge \varepsilon \mu) \le  e^{-\frac13 \varepsilon^2 \mu};
%\end{equation}
%and if $x \geq 2e \mu$ then
%\begin{equation} \label{binpo3}
% \P (X \ge x) \le  2^{-x}.
%\end{equation}
%\end{lemma}
%For the results in Lemma~\ref{lem.bin}, see for example Theorem 2.3
%(b) and inequalities (2.7) and (2.8) in~\cite{cmcd98}.
%
%
%Another useful inequality for binomial random variables is the
%following.
If $X\sim \Bi(k,p)$, then
(see for instance~\cite{Jans02})
    \eqn{
    \lbeq{Binbd}
    \prob(X\leq kp-t) \leq e^{-\frac{t^2}{2(kp+\frac{t}{3})}}.
}

We consider Galton-Watson processes where each individual's
offspring is a random variable $Z$ such that $\E[Z^2] < \infty$. We
always assume that our process begins with one individual. Sometimes
we shall take $Z$ to have a binomial distribution $\Bi (N,p)$, with
$p$ the Hamming graph edge probability, and $N$ a suitable positive
integer. We will write $\prob_{N,p}$ for the probability measure
corresponding to this process.
We will also need Galton-Watson processes that are
`inhomogeneous', in that the offspring size may vary depending on
the parent's `location' in the Galton-Watson tree.


\medskip


A Galton-Watson process can be thought of as a 2-dimensional Markov
chain $(Q_t,G_t)$, where $Q_t$ is the total progeny born until time
$t$, and $G_t$ is the total number of `active' population members,
that is those that are yet to have offspring. To be precise, we
think of a Galton-Watson process as an evolving tree that is
explored one node at a time; then $Q_t$ is the total number of nodes
in that tree at time $t$, and $G_t$ is the total number of
unexplored nodes at time $t$. At each time $t$, if $G_t
> 0$, then we choose one active member of the population and decide
the number of its offspring. In a homogeneous Galton-Watson process,
all population members have the same offspring distribution, in our
case binomial distribution $\Bi (N,p)$, where $N \in \bbN$ and $p
\in [0,1]$ is the Hamming graph edge probability. Then, on the event
$\{ \omega: G_t (\omega) \ge 1\}$, 
    \eqan{
    Q_{t+1} &= Q_t + Z_t,\\
    G_{t+1} &= G_t + Z_t-1,
    }
where the $Z_t$ are i.i.d.\ $\Bi (N,p)$. We always assume $Q_0=G_0=1$; we
let $\phi_0 = \emptyset$ and 
    \eqn{
    \phi_t = \sigma (Z_s: s \le t), \quad \quad \quad t=1,2, \ldots,
    }
the $\sigma$-field generated by $Z_s$ ($s=1,2, \ldots$).

Note that, by the above,
    \eqan{
    \ind_{G_{t-1} \ge 1} Q_t &= \ind_{G_{t-1} \ge 1}(1 + Z_0 + \ldots + Z_{t-1}),\\
    \ind_{G_{t-1} \ge 1} G_t &= \ind_{G_{t-1} \ge 1}(1+ Z_0 + \ldots + Z_{t-1}-t).
    }
Letting $T_0 = \inf \{t: G_t =0\}$, we further see that
    \eqan{
    Z_0 + \ldots + Z_{T_0-1}=T_0-1.
    }


For convenience, we shall instead assume that our Galton-Watson
processes have a continuation in that the random variables $Z_t$
continue to be generated even after $G_t$ has hit 0. With this
assumption, we may simply write, for each $t$, 
    \eqan{
    Q_t &= 1 + Z_0 + \ldots + Z_{t-1},\\
    G_t &= 1+ Z_0 + \ldots + Z_{t-1}-t.
    }



We shall now generalise this setting to a branching
process where $Z_t$ are not i.i.d., but where each $Z_t$ is Binomial
$\Bi (N_t,p)$. Here, $p$ is the edge probability of the Hamming
graph $H(2,n)$, and each $N_t$ is a random variable independent of
the $Z_t$, and such that, for each $t$, conditional on $\phi_{t-1}$,
    \begin{equation}
    \label{narrow-band} N_t p \in [1+\vep/2,1+\vep]  \quad \quad
    \mbox{with probability } 1.
    \end{equation}
Any such branching process will be called generically a {\it
narrow-banded (discrete) birth process}, and in the lemma below we
use $\prob$ to denote the corresponding probability measure -- with
a slight abuse of notation, since in fact there is a whole class of
processes satisfying property~(\ref{narrow-band}).

\begin{lemma}[Large finite progeny for narrow-banded processes]
\label{lem.key}
Let $Q$ be the
total population size of a narrow-banded birth process as
defined above.
Then, for $\alpha > 0$ sufficiently large,
    \begin{eqnarray*}
    \prob [\alpha \vep^{-2} \le Q <\infty] < C \vep e^{-\alpha/2^8}
    \end{eqnarray*}
\end{lemma}
\begin{proof}
As described above, at each time $t$ we generate $Z_t$, a binomial
$\Bi (N_t,p)$, where
    $$p=\frac{1+ \vep}{2(n-1)},$$
and 
    \eqn{ 
    \prob (N_t p\in [1+ \vep/2,1 + \vep]  \mid \phi_{t-1})=1.
    }


As earlier in this section, let $G_0=1$, and let
$G_t=1+Z_0+\ldots+Z_{t-1}-t$ for $t=1,2, \ldots$. In other words, we
assume our narrow-banded Galton-Watson process to have a
continuation; clearly, this does not in any way affect the statement
of the lemma.
%I find it convenient to allow fictitious continuation, this is defined
%for all $t$ even though if $Y_t=0$ the process actually stops.

Let ${\mathcal E}$ be the event
    $$
    \Big \{G_{\lfloor \alpha \vep^{-2}/2 \rfloor } < \frac{1}{16} \alpha
    \vep^{-1}; \quad G_t > 0 \mbox{ for all } t\leq \alpha
    \vep^{-2}/2\Big \}.
    $$
Thus, on the event ${\mathcal E}^c$, one of the following must be true:
    \begin{enumerate}
    \item
    $G_t  = 0$ for some $t \le \alpha \vep^{-2}/2$;
    \item
    $G_{\lfloor \alpha \vep^{-2}/2 \rfloor } \geq \frac{1}{16}\alpha
    \eps^{-1}$.
    \end{enumerate}

In case (1), let $T_0$ be the first time $t$ such that $G_t=0$. Then
$T_0 \le \alpha \vep^{-2}/2$, and $G_{T_0-1}=1$, so it follows that
    \begin{eqnarray*}
    Q = Q_{T_0-1}  = G_{T_0-1} + T_0-1  \le  \alpha \vep^{-2}/2 < \alpha
    \vep^{-2}.
    \end{eqnarray*}
% So this case need not be considered.
So we need not estimate the probability that case (1) occurs.

Otherwise, on the event ${\mathcal E}^c$, $G_{\lfloor \alpha
\vep^{-2}/2 \rfloor } \geq \lceil \frac{1}{16}\alpha \vep^{-1}
\rceil$, and $G_t > 0$ for all $t \le \alpha \vep^{-2}/2$. Let us
call this event $\tilde{\mathcal E}$.

Then, on the event $\tilde{\mathcal E}$, for $t \ge \alpha
\vep^{-2}/2$, we couple our narrow-banded birth process with the
standard Galton-Watson process where the offspring distribution is
binomial
    $$\Bi \Big (\Big \lfloor \frac{2(n-1)(1+ \vep/2)}{1+ \vep}\Big \rfloor, \frac{1+
    \vep}{2(n-1)} \Big ),$$ 
with mean less than or equal to $1+\vep/2$. Let
$Q^{-}_t$ and $G^{-}_t$ respectively be the total progeny and total
number of active members at time $t$ for this process; assume also
that $Q^{-}_{\lfloor \alpha \vep^{-2}/2\rfloor } =\lceil
\frac{1}{16} \alpha \vep^{-1} \rceil$. Let $t_0 = \lfloor \alpha
\vep^{-2}/2 \rfloor $, and for $t \ge t_0+1$ let us write 
    \eqan{
    Q^-_t &= \lceil \frac{1}{16} \alpha \vep^{-1} \rceil +Z^-_{t_0} +
    \ldots +
    Z^-_{t-t_0-1}\\
    G^-_t & = \lceil \frac{1}{16} \alpha \vep^{-1} \rceil + Z^-_{t_0} +
    \ldots + Z^-_{t-t_0-1}-(t-t_0), 
    }
where the $Z^-_t$ are i.i.d.\ $\Bi
\lfloor (2(n-1) (1+ \vep/2)/(1+ \vep) \rfloor, (1+ \vep)/2(n-1))$.
Let $\prob^-$ denote the probability measure corresponding to this
process.

The coupling is between the corresponding tree exploration
processes, step-by-step, as is standard (and as used, for instance, in~\cite{hl}), so that
$Z_t \ge Z^-_t$, $Q_t \ge Q^{-}_t$ and $G_t \ge G^{-}_t$ for all $t
\ge \lfloor \alpha \vep^{-2}/2 \rfloor$. This implies that 
    \eqn{
    \prob (\{\sup_t Q_t < \infty \} \mid \tilde{\mathcal E} ) \le
    \prob^- (\sup Q^{-}_t < \infty).
    }

Further, a standard calculation shows that 
    \eqn{ \prob^- (\sup
    Q^{-}_t < \infty) = (1-\vep + O(n^{-1}+ \eps^2))^{\lceil \alpha
    \vep^{-1}/16 \rceil } \le e^{-\alpha /16}(1+O(\vep + (\vep n)^{-1})),
    }
for all $\vep \in (0,1)$ and $\alpha >0$. But 
    \eqan{ 
    \Pr
    (\tilde{\mathcal E}) & = \Pr (G_{\lfloor \alpha \vep^{-2}/2 \rfloor
    } \ge \lceil \alpha
    \vep^{-1}/16 \rceil, \quad G_t > 0 \quad \forall t \le \lfloor \alpha \vep^{-2}/2 \rfloor )\nonumber\\
    & \le \Pr (G_t > 0 \quad
    \forall t \le \alpha \vep^{-2}/2 )\nonumber\\
    & \le 2 \vep (1+o(1)),
    }
so that
    \begin{eqnarray*}
    \Pr ({\mathcal E}^c \cap \{ \alpha \vep^{-2} \le Q < \infty \})=\Pr
    (\tilde {\mathcal E} \cap \{\alpha \vep^{-2} \le Q < \infty \}) \le
    2 \vep e^{-\alpha /16}(1+o(1)).
    \end{eqnarray*}
%and so
%\begin{eqnarray*}
%\Pr ({\mathcal E}^c \cap \{ \alpha \vep^{-2} \le Q < \infty \}) \le 2 \vep
%e^{-\alpha /16}(1+o(1)).
%\end{eqnarray*}

Now we shall show that ${\mathcal E}$ is very unlikely to happen,
that is we shall upper bound $\Pr ({\mathcal E})$ (ignoring what
happens after time $ \alpha \eps^{-2}/2$).

For this, we also need an upper bounding Galton-Watson process
$(Q^+_t,G^+_t)$, where
the offspring distribution is binomial
$$\Bi \Big (2(n-1), \frac{1+ \vep}{2(n-1)} \Big ),$$
with mean $1+\vep$.  Let $Q^{+}_t$ and $G^{+}_t$ respectively be the
total progeny and total number of active members at time $t$ for this process;
assume also that the initial population size is $Q^{+}_0 =1$. Let us write
    \eqan{
    Q^+_t &= 1 +Z^+_0 + \ldots +
    Z^+_{t-1},\\
    G^+_t & = 1 + Z^+_0 + \ldots + Z^+_{t-1}-t,
    }
where the $Z^+_t$ are
i.i.d.\ $\Bi (2(n-1), (1+ \vep)/2(n-1))$. We use $\prob^+$ to denote the
corresponding probability measure.

Similarly, we use a lower bounding Galton-Watson process
$(Q^-_t,G^-_t)$ (but this time starting from time 0, rather than
from time $t_0 = \lfloor \alpha \vep^{-2}/2 \rfloor $), where the
offspring distribution is binomial $\Bi (\lfloor 2(n-1)(1+
\vep/2)/(1+ \vep) \rfloor, (1+ \vep)/2(n-1))$, with mean at most
$1+\vep/2$. Let $Q^{-}_t$ and $G^{-}_t$ be the total progeny and
total number of active members at time $t$ for this process; assume
also that the initial population size is $Q^{-}_0 =1$. Let us write
    \eqan{ Q^-_t &= 1 +Z^-_0 + \ldots +
    Z^-_{t-1},\\
    G^-_t & = 1 + Z^-_0 + \ldots + Z^-_{t-1}-t, } 
where the $Z^-_t$ are
i.i.d.\ $\Bi (\lfloor 2(n-1)(1+ \vep/2)/(1+ \vep) \rfloor, (1+
\vep)/2(n-1))$. Once again, we use $\prob^-$ to denote the
corresponding probability measure.

Now we couple $Z_t$ with $Z^-_t$ and $Z^+_t$, so that for all $t = 0,1
\ldots$,
    \eqn{
    Z^-_t \le Z_t \le Z^+_t.
    }
A suitable coupling can be achieved thanks to standard results about
stochastic domination between binomial random variables with different
parameters. Explicitly, for $n$ large enough, we may generate
independent binomial random variables $Z^-_t$ such that
    $$
    Z^-_t \sim \Bi
    (\lfloor 2(n-1)(1+ \vep/2)/(1+ \vep) \rfloor, (1+ \vep)/2(n-1)),
    $$
and independent binomial
random variables $W_t$ such that
    $$
    W_t \sim \Bi (2(n-1) -\lfloor 2(n-1)(1+ \vep/2)/(1+ \vep)\rfloor,
    (1+ \vep)/2(n-1)).
    $$
We can then set $Z^+_t = Z^-_t + W_t$ for all $t$. We let
$\prob^{+,-}$ denote the coupling measure.


Let ${\mathcal A}$ be the event that $G^+_t > 0$ for all $t \le
t_0$.
%(We assume that if $G_t^+=0$ for some $t$, than $G^+_s =0$
%for all $s \ge t$, and the same for $G_t,G^-_t$.)
Let ${\mathcal B}$ be the event that $G^-_{t_0} <
\frac{1}{16}\alpha \eps^{-1}$.
Note that, under the coupling,
    \eqn{
    {\mathcal E} \subseteq {\mathcal A} \cap {\mathcal B}.
    }
%Then the events ${\mathcal A}, {\mathcal B}$ are events in a
%product probability space. (In fact, the event ${\mathcal B}$ only
%depends on the $Z^-_t$, while the event ${\mathcal A}$ depends
%on both the $Z^-_t$ and $W_t$.) The event ${\mathcal B}$ is monotone
%decreasing in the variables $Z^-_t,W_t$, while the event ${\mathcal
%A}$ is monotone increasing. Then the FKG inequality implies that
%${\mathcal A}$ and ${\mathcal B}$ are negatively correlated, that is
%Also,
%\eqn{
%\Pr^{+,-} ({\mathcal A} \cap {\mathcal B}) = \Pr^{+,-} ({\mathcal A})
%\Pr^{+,-} ({\mathcal
%B}  \mid {\mathcal A}).
%}
But now it is easily seen that, as $\alpha \to \infty$, 
    \eqn{
    \Pr^{+,-}
    ({\mathcal A}) \le 2 \vep (1+o(1)).
    }
Also, using
inequality~(\ref{Binbd}) 
    \eqan{ \Pr^{+,-} ({\mathcal B}) & \le \Pr
    \Big (\Bi (\lfloor 2(n-1)(1+ \vep/2)/(1+\vep) \rfloor \lfloor \alpha
    \vep^{-2}/2 \rfloor, (1+ \vep)/2(n-1)) < \alpha \vep^{-2}/2 +
    \frac{1}{16}
    \alpha \vep^{-1} \Big )\nonumber\\
    & \le \exp \big (-\alpha/2^8\big),
    }
for all $\vep$ satisfying $\vep \gg n^{-2/3} (\log n)^{1/3}$, and all $\alpha$ and
$n$ sufficiently large, since $\alpha \vep^{-1} \gg 1$ and $\alpha
\vep^{-1} \gg \alpha \vep^{-2}/n$.

Now, the event ${\mathcal A}$ is increasing, and the event ${\mathcal B}$ is
decreasing, and both are events on the same probability space,
corresponding to a family of independent random variables. It then
follows from the FKG inequality that they are negatively correlated.
Hence, 
    \eqn{ \Pr ({\mathcal E} ) \leq \Pr^{+,-} ({\mathcal A} \cap
    {\mathcal B}) \leq \Pr^{+,-}  ({\mathcal A}) \Pr^{+,-}( {\mathcal
    B}) \le
      2 \vep e^{-\alpha /2^8},
    } and hence \eqn{ \Pr (\alpha \vep^{-2} \le Q < \infty) \le \Pr
    (\alpha \vep^{-2} \le Q < \infty, {\mathcal E}^c) + \Pr ({\mathcal
    E}) \le 4 \vep e^{-\alpha /2^8} (1+o(1)).
    }
\end{proof}

\section{Proof of main result}

Recall that $\Omega = 2(n-1)$. Let $N \gg \vep^{-2}$. Let $Q({\bf
v})$ denote the component of vertex ${\bf v}$. Our first lemma is
\cite[Proposition 2.1]{hl}.
\begin{lemma}[Cluster tail equals the survival probability]
\label{lem.large-clusters} 
Let $\vep$ satisfy $\vep^{-2} \log n \ll
\vep n^2$. Let $p=p_c +\frac{\vep}{\cn}$. Then, for any vertex ${\bf
v}_0=(i_0,j_0)$, 
    \eqn{
    \Pr \Big ( |Q({\bf v}_0)| \ge N  \Big ) = 2 \vep (1+o(1)).
    }
\end{lemma}


\medskip
Our next lemma upper bounds the variance of $Z_{\sss \ge N}$, the number of vertices
in components at least $N$. This result is a
special case of \cite[Corollary 2.3]{hl}.

\begin{lemma}[Concentration of vertices in large clusters]
\label{lem.variance} Let $\vep$ satisfy $\vep^3 n^2 \gg \log n$.
Let $p=p_c+\frac{\vep}{\cn}$. Let $N \gg \vep^{-2}$. Then, for every
$\delta > 0$, 
    \eqn{
    \Pr (|Z_{\sss \ge N} - \E_p [Z_{\sss \ge N}]| \ge \delta \vep n^2)=o(1).
    }
\end{lemma}



\medskip
We now show that, with high probability, there are no components of
`medium' size; that is, if $\alpha = \alpha (n) \to \infty$ as $n
\to \infty$, then any component of size at least
 $\alpha\vep^{-2}$, \whp{} will in fact be of size at least
$\frac{\varepsilon n^2}{5}$. This is the content of our next lemma:

%\begin{lemma}
%\label{lem.no-middle-ground} [`No middle ground'.] Let $\vep$
%satisfy $\vep^{-2}\log n  \ll \vep n^2$. Let $p=p_c
%+\frac{\vep}{\cn}$. Then for $n$ large enough \eqn{
%    \Pr \Big ( 2^{10} \vep^{-2} \log n \le |Q({\bf v_0})| < \frac{ \varepsilon
%n^2}{5}\Big ) \le n^{-3}.
%    }
%Hence the probability that there is some vertex ${\bf v_0}$ in such a
%component is $O(n^{-1})$.
%\end{lemma}

\begin{lemma}[No middle ground]
\label{lem.no-middle-ground} 
Let $\vep$ satisfy $\vep^{-2}\log n  \ll \vep n^2$. Let $p=p_c
+\frac{\vep}{\cn}$. Let $\alpha = \alpha (n) \to \infty$ as $n \to
\infty$. Then there exists a constant $C$ such that, for $n$ large
enough, 
    \eqn{
    \lbeq{no-middle-ground}
    \Pr \Big ( \alpha \vep^{-2}  \le |Q({\bf v_0})| < \frac{ \varepsilon
    n^2}{5}\Big ) \le C \vep e^{-\alpha/2^8} +O(n^{-6}).
    }
Hence, the probability that there is some vertex ${\bf v_0}$ such
that its component $Q({\bf v_0})$ satisfies 
    \eqn{
    \lbeq{no-comp}
    2^8 \vep^{-2} \log
    (n \vep^3) \le |Q({\bf v_0})| < \frac{\vep n^2}{5}
    } 
is $o(1)$ as $n \to \infty$.
\end{lemma}

Before giving the proof of Lemma~\ref{lem.no-middle-ground}, let us
state two more results from~\cite{hl}, which compare the size of the
cluster of a vertex to the total progeny of suitable Galton-Watson
processes.


The first of these is essentially \cite[Lemma 4.1]{hl}, proved
by standard methods, and gives an upper bound. Let $\prob_{\cn,p}$
be the probability measure corresponding to a standard Galton-Watson
process where the family size is a binomial with parameters $\cn$
and $p$, and the initial population size is 1.

\begin{lemma}
[Stochastic domination of cluster size by
branching process progeny size]
\label{lem-upper}
For every
$\ell \in \bbN$,
    \begin{align*}
    \Pr (|Q({\bf v}_0)|\geq \ell) \leq
    \prob_{\cn,p}(Q\geq \ell).
    \end{align*}
\end{lemma}

The second one is a slight extension of \cite[Lemma 4.3]{hl},
and establishes a lower bound. Let $\cn'= \cn - \frac{5}{2} \max
\{\ell n^{-1},C \log n\}$ and note that $\cn' \ge 2(n-1)-\frac12
\varepsilon n$ for $n$ sufficiently large. It turns out that the
cluster size can be stochastically bounded from below using a
Galton-Watson process where the family size is a binomial with
parameters $\cn'$ and $p$, and the initial population size is 1. For
$n$ sufficiently large, this process is supercritical, with mean
population size at least $1+\vep/2$, since $\cn' \ge 2(n-1)-\frac12
\varepsilon n$.

\begin{lemma}
[Stochastic domination of cluster size over
branching process progeny size] 
\label{lem-lower}
There is a constant $C > 0$ such that the following holds. For every $\ell \le
\vep n^2/5$,
    \begin{align}
    \label{eqn.lower-1}
    \Pr (|C({\bf v}_0)|\geq \ell) \geq
    \prob_{\cn',p}(Q\geq \ell)+O(n^{-6}),
    \end{align}
where $\cn'= \cn - \frac{5}{2} \max \{\ell n^{-1},C \log n\} \ge 2(n-1)-\frac12 \varepsilon n$.
\end{lemma}
Lemma~\ref{lem-lower} can be proved in exactly the same way as
\cite[Lemma 4.3]{hl}, using an
extension of \cite[Proposition 5.1]{hl} concerning the number of
elements per line in large clusters from $\eta \ll \vep$ to $\eta
\le \vep/5$ (which is exactly the same, again, since the proof of
\cite[Proposition 5.1]{hl} does not in any way rely on $\eta$
being of a smaller order than $\vep$).

In fact, Lemmas~\ref{lem-upper} and~\ref{lem-lower} are not
sufficient for our purposes, and we refine them in the following.
Let $Q_t ({\bf v_0}), G_t ({\bf v_0})$ will denote the total number
of vertices and the number of unexplored vertices at time $t$ in the
exploration of the cluster of vertex ${\bf v_0}$. Also, $Q_t$ and $G_t$,
respectively, will denote the total number of nodes and the number of
unexplored nodes at time $t$ in the Galton-Watson tree when the
offspring is binomial $\Bi (\cn,p)$; and let $Q'_t$ and $G'_t$,
respectively, denote the total number of nodes and the number of
unexplored nodes at time $t$ in the Galton-Watson tree when the
offspring is binomial $\Bi (\cn',p)$.
Let ${\mathcal E}_t$
be the event that, for every $i$, no more than $m$ vertices $(i,x)$
and no more than $m$ vertices $(x,i)$ have been included in the
cluster of a vertex ${\bf v_0}$ up to time $t$ during its exploration 
process. Also, let ${\mathcal E}'_t$ be the event that $Q'_t \le Q_t ({\bf v_0}) \le
Q_t$ and $G'_t \le G_t ({\bf v_0}) \le G_t$. 

\begin{lemma}[Sandwiching the cluster exploration]
\label{lem.couple}
Let $\ell= \vep n^2/5$, and let $m =  \frac{5}{2}\ell n^{-1}$. 
Then, if $n$ is large
enough, on the event
${\mathcal E}_t \cap {\mathcal E}'_t$, there exists a coupling of the cluster
exploration process and the upper and lower bounding Galton-Watson
processes $\prob_{\cn,p},\prob_{\cn',p}$ in such a way that
$Q'_{t+1} \le Q_{t+1} ({\bf v_0}) \le
Q_{t+1}$ and $G'_{t+1} \le G_{t+1} ({\bf v_0}) \le G_{t+1}$
a.s.
\end{lemma}
It is easy to prove Lemma~\ref{lem.couple} using
standard component exploration and coupling methods, in a similar
way to \cite[Lemmas 4.1 and 4.3]{hl}, and so we
%its proof is not included here.
omit the details.

\smallskip
We are now ready to prove that there is indeed no middle ground:

\begin{proofof}{Lemma~\ref{lem.no-middle-ground}}
Lemma~\ref{lem.couple} implies that, on the event ${\mathcal E}_t
\cap {\mathcal E}'_t$, the $(t+1)^{\rm th}$ step of the exploration
process of the cluster of vertex ${\bf v_0}$ can be coupled with the
$(t+1)^{\rm th}$ step of a narrow-banded process in Lemma~\ref{lem.key}.
Since $[2(n-1)-\frac12 \vep n] p \ge 1 + \vep/2$ for $n$ large
enough, the family size of the narrow-banded branching process in
question (i.e., the component exploration process) falls into the
interval $[1+\vep/2,1+\vep]$, as required. Now observe that, if
$Q({\bf v_0}) \ge \ell$ then also  $Q_{\ell } ({\bf v_0}) \ge \ell$;
thus $Q({\bf v_0}) \ge \ell$ if and only if  $Q_{\ell } ({\bf v_0})
\ge \ell$. We use this fact, first with $\ell = 2^8 \vep^{-2}
\log n$, and then with $\ell = \vep^2 n/5$.
Then the first claim follows directly from Lemma~\ref{lem.key}, %with
%$\alpha = 2^{10} \log n$,
also noting that $\prob_p ({\mathcal E}_t^c) = O(n^{-6})$ for all $t
\le \vep n^2/5$, see \cite[Proposition 4.4 and its proof]{hl}.
% couplings of the component exploration
%process with upper and lower bounding binomial Galton-Watson
%processes described in~\cite{hl}, using Lemmas~\ref{prop-couplingUB}
%and~\ref{prop-couplingLB}.

As for the second claim, note that for every $x, y$, the number of
components of size in between $x$ and $y$, where $0\leq x\leq y$, is given by
    \eqn{
    N_{x,y} = \sum_{{\bf v}} \frac{1}{|Q({\bf v})|} \ind_{x\leq |Q({\bf v})| < y}.
    }
Let $x = 2^4 \vep^{-2} \log (n^2\vep^3)$ and $y=\frac{\vep n^2}{5}$.
Then, for any vertex ${\bf
v}$,
    \begin{eqnarray}
    \E \Big (\frac{1}{|Q({\bf v})|} \ind_{x\leq |Q({\bf v})| < y} \Big ) &
    \le & 2^{-4} \vep^2 \frac{1}{\log (n^2\vep^3)} 
    \prob_p \Big (2^4 \vep^{-2} \log (n^2\vep^3)\leq |Q({\bf
    v})|
    <\frac{\vep n^2}{5}\Big )\nonumber\\
    &  \le &  2^{-4} \vep^2 \frac{1}{\log (n^2\vep^3)} C \vep e^{-\log
    (n^2\vep^3)} + O(n^{-6})\nonumber\\
    & \le & C n^{-2}\frac{1}{\log (n^2\vep^3)} + O(n^{-6}),
    \end{eqnarray}
where, for the second inequality, we have used \refeq{no-middle-ground} in
Lemma \ref{lem.key}.
Summing over all vertices ${\bf v}$, we see that $\E [N_{x,y}]=o(1)$,
and hence $\prob_p (N_{x,y} \ge 1) =o(1)$, as required.

\end{proofof}
\smallskip

\noindent
We now complete the proof of Theorem~\ref{thm-main}:

\begin{proofof}{Theorem~\ref{thm-main}}
By Lemma~\ref{lem.variance}, the number of vertices in components of
size at least $2^4 \vep^{-2} \log (n^2\vep^3)$, $Z_{\sss \geq 2^4
\vep^{-2} \log (n^2\vep^3)}$, is concentrated around $2\vep n^2$. In
other words, the number of vertices in connected components of size
at least $2^4 \vep^{-2} \log (n^2\vep^3)$ is close to $2\vep n^2$
\whp. Now, from~\cite{hl}, we know that, \whp{},
there is a giant component of size $2 \vep n^2 (1+\op (1))$. This
implies that, \whp{}, there is no other cluster of
size at least $\vep n^2/5$. Further, by \refeq{no-comp} in 
Lemma~\ref{lem.no-middle-ground}, \whp{}, there are no
components of size at least $2^4 \vep^{-2} \log (n^2\vep^3)$ and less
than $\vep n^2/5$. Hence, \whp{}, the second largest component must be at
most $2^4 \vep^{-2} \log (n^2\vep^3)$, as claimed.
\end{proofof}

\subsection*{Acknowledgement}
This work was started during a visit by MJL to NYU, and continued
during a visit by MJL and JS to Georgia Tech, and during a visit by
MJL to Eurandom. The hospitality of the three institutions is
gratefully acknowledged. Also, the work of RvdH was supported in 
part by Netherlands Organisation for
Scientific Research (NWO), and the work of MJL 
by the Nuffield Foundation.



\newcommand\AAP{\emph{Adv. Appl. Probab.} }
\newcommand\JAP{\emph{J. Appl. Probab.} }
\newcommand\JAMS{\emph{J. \AMS} }
\newcommand\MAMS{\emph{Memoirs \AMS} }
\newcommand\PAMS{\emph{Proc. \AMS} }
\newcommand\TAMS{\emph{Trans. \AMS} }
\newcommand\AnnMS{\emph{Ann. Math. Statist.} }
\newcommand\AnnPr{\emph{Ann. Probab.} }
\newcommand\CPC{\emph{Combin. Probab. Comput.} }
\newcommand\JMAA{\emph{J. Math. Anal. Appl.} }
\newcommand\RSA{\emph{Random Struct. Alg.} }
\newcommand\SPA{\emph{Stoch. Proc. Appl.} }
\newcommand\ZW{\emph{Z. Wahrsch. Verw. Gebiete} }
\newcommand\PTRF{\emph{Probab. Theor. Relat. Fields}}
%\newcommand\DMTCS{\jour{Discrete Mathematics and Theoretical Computer
% Science} }
\newcommand\DMTCS{\jour{Discr. Math. Theor. Comput. Sci.} }

\newcommand\AMS{Amer. Math. Soc.}
\newcommand\Springer{Springer}
%\newcommand\Springer{Springer-Verlag}
\newcommand\Wiley{Wiley}
%\newcommand\Wiley{John Wiley \& Sons}

\newcommand\vol{\textbf}
\newcommand\jour{\emph}
\newcommand\book{\emph}
%\newcommand\inbook{In \emph}
\newcommand\inbook{\emph}
\def\no#1#2,{\unskip#2, no. #1,} %(typeset after year)
%\def\no#1{\unskip:#1} %(typeset after volume)

\newcommand\webcite[1]{\hfil\penalty0\texttt{\def~{\~{}}#1}\hfill\hfill}


\def\nobibitem#1\par{}

\begin{thebibliography}{99}

%\bibitem{AS00}
%N.\ Alon and J.\ Spencer.
%\newblock The Probabilistic Method, 2nd Edition.
%\newblock John Wiley and Sons, New York, 3rd ed., 2008.

%\bibitem{an72}
%K.B. Athreya and P.E. Ney, Branching Processes, Springer, Berlin, 1972.

%\bibitem{bhj}
%A.D. Barbour, L. Holst, S. Janson, Poisson Approximation, OUP, Oxford, 1992.


\bibitem{bchss1}
C. Borgs, J.T. Chayes, R. van der Hofstad, G. Slade and J. Spencer,
Random subgraphs of finite graphs: I. The scaling window under the
triangle condition. \RSA \vol{27} (2005) 137-184.

\bibitem{bchss2}
C. Borgs, J.T. Chayes, R. van der Hofstad, G. Slade and J. Spencer,
Random subgraphs of finite graphs: II.The lace expansion and the
triangle condition. \AnnPr \vol{33} (2005)  1886--1944.


\bibitem{bchss3}
C. Borgs, J.T. Chayes, R. van der Hofstad, G. Slade and J. Spencer,
Random subgraphs of finite graphs: III. The phase transition on the
$n$-cube. {\em Combinatorica}, {\bf 26}(4) (2006) 395--410.

%\bibitem{BCKS99}
%C.~Borgs, J.~T.~Chayes, H.~Kesten and J.~Spencer.
%\newblock Uniform boundedness of critical crossing probabilities implies hyperscaling.
%\newblock {\em Random Struct.\ Alg.}, {\bf 15}:368--413 (1999).

%\bibitem{BCKS01}
%C.~Borgs, J.~T.~Chayes, H.~Kesten and J.~Spencer.
%\newblock The birth of the infinite cluster: finite-size scaling in percolation.
%\newblock {\em Commun.\ Math.\ Phys.}, {\bf 224}:153--204 (2001).


%\bibitem{cs}
%L.S. Chandran and C.R. Subramanian, A spectral lower bound for the
%treewidth of a graph and its consequences, preprint, available at
%www.mpi-sb.mpg.de/~sunil/applyspectree.ps

%\bibitem{devroye}
%L. Devroye, Branching Processes and Their Applications in the Analysis
%of Tree Structures and Tree Algorithms, in Probabilistic Methods for
%Algorithmic Discrete Mathematics, ed. M.Habib, C. McDiarmid,
%J. Ramirez-Alfonsin and B. Reed, 249--314, Springer-Verlag, Berlin, 1998.

%\bibitem{dwass}
%M. Dwass, The total progeny in a branching process, \JAP{} \vol{6}
%(1969), 682--686.

\bibitem{er}
P. Erd\H{o}s and A. R\'enyi, {\em On the Evolution of the Random
Graph}, {\em Magyar Tud. Akad. Mat. Kutat\'o Int. Kozl.} {\bf 5}
(1960) 17--61.

%\bibitem{HeHof05}
%M.~Heydenreich and R.~van der Hofstad.
%\newblock Random graph asymptotics on high-dimensional tori.
%\newblock To appear in {\em Commun.\ Math.\ Phys.}

\bibitem{hl}
R.~van der Hofstad and M. J. Luczak.
\newblock Random subgraphs of the 2D
Hamming graph: the supercritical phase.
\newblock Preprint 2007, to appear in {\em Probab. Theor. Related Fields}.

%\bibitem{HS04a}
%R.~van~der Hofstad and G.~Slade.
%\newblock Expansion in $n^{-1}$ for percolation critical values on the $n$-cube
%  and ${\mathbb Z}^n$: the first three terms.
%\newblock {\em Combin.\ Probab.\ Comput.} \vol{15} (2006), 695--713.

%\bibitem{cycle}
%S. Janson, Cycles and unicyclic components in random graphs, \CPC{}
%\vol{12} (2003), 27--52.

\bibitem{Jans02}
S.~Janson, On concentration of probability, Contemporary Combinatorics, ed. B. Bollob\'as,
Bolyai Soc.\ Math.\ Stud.\ \vol{10} (2002), J\'anos Bolyai Mathematical Society, Budapest, 289--301.


%\bibitem{giant}
%S. Janson, D.E. Knuth, T. {\L}uczak \& B. Pittel,
%The birth of the giant component,
%\RSA
%\vol3 (1993),
%233--358.


%\bibitem{JLR}
%S. Janson, T. \L uczak \& A. Ruci\'nski,
%\book{Random Graphs},
%\Wiley, New York, 2000.

%\bibitem{kolchin}
%V.F. Kolchin, Moments of degeneration of a branching process and
%height of a random tree, Mathematical Notes of the Academy of Sciences
%of the USSR \vol{6} (1978), 954--961.

%\bibitem{lmu03}
%M.J. Luczak, C. McDiarmid and E. Upfal, On-line routing of random
%calls in networks, \PTRF{} \vol{125} (2003), 457--482.


%\bibitem{cmcd98}
%C. McDiarmid, Concentration, in Probabilistic Methods for
%Algorithmic Discrete Mathematics, ed. M.Habib, C. McDiarmid,
%J. Ramirez-Alfonsin and B. Reed, 195--248, Springer-Verlag, Berlin, 1998.

\bibitem{n07}
A. Nachmias, Mean-field conditions for percolation on finite graphs,
Preprint 2007.


%\bibitem{otter}
%R. Otter, The multiplicative process, \AnnMS{} \vol{20} (1949) 206--224.

\end{thebibliography}

\end{document}
