%%%%%%% LaTeX File, 12 Pages     %%%%%%
%%%%% Accepted as R19 %%%%%
%%%%% Revised June 10 %%%%%%
%%%%%%% Author email: spencer@cs.nyu.edu %%%%%%
%%%% Submitted to Electronic Journal of Combinatorics %%%%%%
\documentstyle[11pt]{article}
\textwidth 6.5in
\hoffset -.7in
\begin{document}
\pagestyle{myheadings}
           \markright{\sc the electronic journal of combinatorics 4 (no. 2)
(1997), \#R19 \hfill}
           \thispagestyle{empty}
\begin{center}{\Large\bf Real Time Asymptotic Packing
}\\ Joel Spencer\\ {\tt spencer@cs.nyu.edu} \\ {\tt Courant Institute, New
York} \\ Submitted: May 7, 1966.  Accepted: June 12, 1996. \\
\end{center}
\footnote{AMS(1991) Subject Classification: Primary $05B40$, Secondary
$60D05$}
\newcommand{\lnai}{\lim_{n\rightarrow\infty}}
\newcommand{\eps}{\epsilon}
\newcommand{\del}{\delta}
\newcommand{\gam}{\gamma}
\newcommand{\alp}{\alpha}
\newcommand{\abound}{0\leq\alpha\leq \frac{1}{De^{-s}}}
\newcommand{\beq}{\begin{equation}}
\newcommand{\eeq}{\end{equation}}
\newcommand{\rin}{\rightarrow\infty}
\newcommand{\oho}{O_{H}(1)}
\newcommand{\ohd}{O_H(\Delta s)}
\newcommand{\ohs}{O_H((\Delta s)^2)}
\begin{abstract}
A random greedy algorithm, somewhat modified, is analyzed
by using a real time context and showing that the variables remain
close to the solution of a natural differential equation.  Given
a $(k+1)$-uniform simple hypergraph on $N$ vertices, regular of
degree $D$, the algorithm gives a packing of disjoint hyperedges
containing all but $O(ND^{-1/k}\ln^cD)$ of the vertices. 
\end{abstract}
Let $H=(V,E)$ be a $(k+1)$-uniform hypergraph on $N$ vertices.  A 
{\em packing} $P$ is a family of disjoint edges.  Given $P$ we correspond
the set $S=V-\bigcup P$ of those vertices $v$ not in the packing, these
$v$ we call surviving vertices.  We shall assume:
\\ $\bullet$  $H$ is simple.  That is, any two vertices are in at most
one edge.
\\ $\bullet$  $H$ is regular of degree $D$.  That is, every vertex $v$
lies in precisely $D$ $e\in E$.
\par We are interested in the asymptotics for $k$ fixed, $D,N\rin$.
We assume $k\geq 2$ is fixed throughout.  We show
\\ {\bf Theorem.}  
There exists a packing with
\[ |S| = O(ND^{-1/k}\ln^cD)  \]
where $c$ depends on $k$.  (We make no attempt to optimize $c$.) 
\par Our approach is to give a real time random process that produces 
a packing with $E[|S|]$ meeting these bounds.  The process, as described
in \S 1,2, can be thought of as the random greedy algorithm with some
``stabilization mechanisms'' added.  Placing the algorithm in a real time
context allows for simulation of the variables by a differential equation
and the analysis of our discrete, albeit asymptotic, procedure becomes
quite continuous in nature.  
\par The study of asymptotic packing can be said to date from the
proof by V. R\"odl \cite{R} of a classic conjecture of Paul Erd\H{o}s and 
Haim Hanani \cite{EH}.  R\"odl showed that for $l<k$ fixed and $n\rightarrow
\infty$ there exists a ``packing'' $P$ of $\sim {n\choose l}/{k\choose l}$
$k$-element subsets of an $n$-element universe $\Omega$ so that every
$l$ points of $\Omega$ lie in at most one of the $k$-sets.  This
was nicely generalized by N. Pippenger in work appearing \cite{PS}
jointly with this author.  He showed that  any $k$-uniform
hypergraph on $N$ vertices with $\deg(v)\sim D$ for every $v$ and
any two vertices $v,w$ having $o(D)$ common edges has a packing $P$
with $|S|=o(n)$.  (Here $k$ is fixed,
$N,D\rightarrow\infty$.)  Recent work has centered on lowering the
size of $|S|$ in terms of $D$.  Our main result has also been
shown (indeed, without the logarithmic term for $k\geq 3$) in
our joint paper \cite{AKS}  by quite different techniques.  
\section{Two Simple Algorithms}
We first define the {\em discrete random greedy algorithm} in a natural
way.  Randomly order $e_1,\ldots,e_{\omega}$, $\omega=|E|$, the edges of
$H$.  Set $P_0=\emptyset, S_0=V$.  For $1\leq i\leq \omega$ {\em if}
$e_i\subseteq S_{i-1}$ then set $P_i=P_{i-1}\cup\{e_i\}$ and 
$S_i=S_{i-1}- e_i$, {\em else} keep $P_i=P_{i-1}$ and $S_i=S_{i-1}$.
That is, consider the edges in random sequential order and add each to
the packing if you can.  We conjecture that $E[|S_{\omega}|]$ meets the
bounds of our Theorem.  This author \cite{S} and, independently, V.
R\"odl and L. Thoma \cite{RT} have shown that $E[|P_{\omega}|] \sim
\frac{N}{k+1}$ or  equivalently that $E[|S_{\omega}|]=o(N)$.
Viewed in this light we are now looking at a second order term, just
how close to a ``perfect packing'' can we get.  
Unfortunately, this natural algorithm has eluded more refined
analysis.  We feel it would be most interesting even to prove that
the exponent of $D$ is the correct one, that 
\beq\label{conj}
E[|S_{\omega}|] = O(ND^{-1/k+o(1)})\hspace*{2cm}         (??)
\eeq
\par Now we define the {\em realtime random greedy algorithm}.  We
let time $t$ go continuously starting from zero.  The packing $P=P_t$
will vary with time as will $S_t=V-\bigcup P_t$.  We let $H_t$ denote
the restriction of $H$ to $S_t$.  If by time $t$ edge 
$e\subseteq S_t$ has not yet been born then it is born in the next $dt$
with probability $e^t\frac{dt}{kD}$. When $e$ is born it is added
to $P$.  In particular, all $e'$ with $e'\cap e\neq \emptyset$ are
no longer considered.
\par Observe that the edges are being born in a random order.  Thus
if we continue this process until $H$ has no edges the distribution
of $S$ will be precisely that of the discrete random greedy algorithm.
It will be more convenient, however, to stop the process at time
$\omega = \ln D$. We now give a heuristic guide which should motivate
the full process we define later.  Let $\deg_t(v)$ be (for $v\in S_t$)
the degree of $v$ in $H_t$ and {\em suppose} all $\deg_t(v)\sim f(t)D$.
There would be $\sim kf^2(t)D^2$ pairs $(e,e')$ where $e$ is an edge
containing $v$ and $e'$ is an edge intersecting $e$, but not at $v$.
Each $e'$ is born in the next $dt$ with probability $e^t\frac{dt}{kD}$
and if born diminishes $\deg(v)$ by one for each $(e,e')$.
(If $e$ itself is born then $v$ is removed from $H$.)   On
average $\deg(v)$ is decreased by $kf^2(t)D^2e^t\frac{dt}{kD} =
e^tf^2(t)D\cdot dt$. If this is to be $f(t+dt)D$ then we would need
\[ f(t+dt) = f(t) - e^tf^2(t)dt  \]
\[  f'(t) = -e^tf^2(t)  \]
so that, as $f(0)=1$, we would have $f(t)=e^{-t}$.  Indeed, the choice of
birth intensity was designed so that $f(t)$ would have this particularly
convenient form.  
\par Suppose $v$ has survived to time $t$.  It lies on $\sim De^{-t}$
edges, each is born with probability $e^t\frac{dt}{Dk}$ in the next 
$dt$ so $v$ is removed from $S$ with probability $\frac{dt}{k}$.  
The probability that $v$ survives to time $t$ starting at time zero 
would then be $\exp[-\int_0^t \frac{dt}{k}] = e^{-t/k}$.
Since we want $\deg(v)\sim De^{-t}$ but $\deg(v)$ is integral we
can only hope to carry this approximation through time $\omega=\ln D$.  At
that time $\Pr[v\in S_t]$ would be $e^{-t/k}= D^{-1/k}$.  By Linearity
of Expectation we would have $E[|S_{\omega}|]= ND^{-1/k}$. 
\par As we said earlier we are unable to make this argument rigorous and
it is only conjecture that the result is correct.  We see the basic 
problem as one of stability of a random system.  The values $\deg_t(v)$
are random variables that will naturally oscillate around their means.
The difficulty is that once some $\deg_t(v')$ are abnormally off their
mean then it affects the change in $\deg_t(v)$.  (If $v',v$ have a 
common edge $e$ then $\deg(v')$ affects the number of $(e,e')$ which
affects the expected change of $\deg(v)$.)  The $N$ different $\deg_t(v)$
are all oscillating off their means and the oscillation of one can have
an adverse affect on the oscillations of another.  To handle this
problem we modify the realtime random greedy algorithm by what we
think of as stabilization mechanisms.
\section{Stabilization}  
As before the basic event is the birth of an edge $e$.  If by time $t$ $e$
has not yet been born it is born in the next $dt$ with probability
$e^t\frac{dt}{kD}$.  That edge is added to $P$, all $v\in e$ are
removed from $S$ and all $e'$ containing any such $v$ are deleted.
We add two stabilization mechanisms.  On certain occasions we {\em waste}
a vertex $v$.  When this occurs $v$ is removed from $S$ and all edges $e$
containing $v$ are deleted.  On certain occasions when an edge $e$ has
been born and $v\in e$ we {\em revive} $v$.  When this occurs $v$ is
``put back'' into $S$ and the edges $e'\neq e$ containing $v$ are
put back into $H$.  (A vertex $v\in e$ is revived at the moment $e$ is
born or not at all. More formally we can say that when $e$ is born $e$
is deleted and all nonrevived $v\in e$ are removed from $S$ as are all
edges $e'$ containing such $v$.  The term ``revive'' gives the sense we
aim for that this occurs rarely.)
\par Here are the probabilities.  Suppose $\deg_t(v)=De^{-t}-\Delta$
with $\Delta\geq 0$.  Then $v$ is wasted in the time interval
$[t,t+dt]$ with probability $\frac{\Delta}
{kDe^{-t}}dt$.  Suppose $\deg_t(v)=De^{-t}+\Gamma$ with $\Gamma\geq 0$.
If an edge $e$ containing $v$ is born 
then $v$ is revived with probability
$\frac{\Gamma}{De^{-t}+\Gamma}$.  The a priori probability that $v$ is
revived is then
\[ \deg_t(v) \frac{dt}{kDe^{-t}}\frac{\Gamma}{De^{-t}+\Gamma} = 
\frac{\Gamma}{kD^{-t}}dt  \]
This gives a convenient symmetry:
\beq\label{row}
\Pr[v\mbox{ revived or wasted}]=\frac{|\deg_t(v)-De^{-t}|}{kDe^{-t}}dt
\eeq
\par Consider any $v$ at time $t$.  Suppose $\deg_v(t)=De^{-t}-\Delta$ with
$\Delta\geq 0$.  In the next $dt$ there is probability $\frac{\deg_t(v)}
{kDe^{-t}}dt$ that some $e$ containing $v$ is born (and $v$ can't be 
revived as $\Delta\geq 0$) and probability $\frac{\Delta}{kDe^{-t}}dt$
that $v$ is wasted; so probability $\frac{dt}{k}$ that $v\not\in S_{t+dt}$.
Suppose $\deg_t(v)=De^{-t}+\Gamma$ with $\Gamma\geq 0$.  Then $v$ cannot
be wasted and the probability that some $e$ containing $v$ is born and
$v$ is not revived is $\frac{\deg_t(v)}{kDe^{-t}}
(1-\frac{\Gamma}{De^{-t}+\Gamma}) = \frac{dt}{k}$.  That is, for {\em any}
value $H_t$ of the process at time $t$ with $v\in S_t$
\beq\label{star} \Pr[v\not\in S_{t+dt}\mid H_t] = \frac{dt}{k} \eeq
Indeed, (\ref{star}) is the purpose of our stabilization.  We deduce
\beq\label{surv}  \Pr[v\in S_t] = e^{-\int_0^t \frac{dt}{k}} = e^{-t/k}  \eeq
Let $X$ be any random variable that depends only on the history of the 
process up to time $s$.  Then
\beq\label{bttf} E[X|w\in S_t] = E[X|w\in S_s] \eeq
The reason is that any history up to time $s$ with $w\in S_s$ has precisely
the same probability $e^{-(t-s)/k}$ of being extended to a history up to
time $t$ with $w\in S_t$.
\section{The Big Picture}
We set
\beq\label{omega} \omega = \ln D - K\ln\ln D \eeq
($K$ a suitably large constant)
and continue the process (starting at time zero) to time $\omega$.  
Call $e$ a {\em false birth}
if $e$ is born at time $t$ but at some time $t'<t$ some $v'\in e$ was
revived  when some $e'$ was born.  The number of false births is at
most the number of revivals since we can associate $e$ with that
revival $t',v'$ with $t'<t$ maximal and this association is injective.
False births actually do overlap previous births.  (Anthropomorphically
speaking, though, the process does not know that a birth is false.)
The set of born edges $e$ which are not false births gives 
the packing $P^*$ that we desire.  Set $S^*=V-\bigcup P^*$.
\par For each vertex $w$ let $SURV_w$ be the indicator for $w\in S_{\omega}$;
$WASTE_w$ the number of times (zero or one) that $w$ is wasted; $REVIVE_w$
the number of times $w$ is revived.  $S^*$ consists of surviving vertices,
wasted vertices, and vertices in false births so
\[ |S^*|\leq \sum_w SURV_w+WASTE_w+(k+1)REVIVE_w \]
As constants do not concern us we define
\[
LOSS_w = WASTE_w + REVIVE_w
\]
so we can bound more conveniently
\[
|S^*| \leq \sum_w SURV_w + (k+1)LOSS_w
\]
\par Now Linearity of Expectation comes into play.  The expectation of
this sum is the sum of the expectations so that it suffices to appropriately
bound $E[SURV_w]$, $E[LOSS_w]$ for a given $w$.  From (\ref{surv})
\[ E[SURV_w] = \Pr[w\in S_{\omega}] = e^{-\omega/k} = D^{-1/k}
\ln^{K/k}D  \]
Now it suffices to show
\beq\label{twostar}
E[LOSS_w] = O(D^{-1/k}\ln^cD)
\eeq
Fix $w$ and consider $E[LOSS_w]$.  For every $t$ (\ref{row}) gives the 
probability $w$ is wasted or revived.  However, this is conditional on
$w\in S_t$ which occurs with probability $e^{-t/k}$.  Thus
\[
 E[LOSS_w] = \int_{t=0}^{\omega} \frac{e^{-t/k}}{kDe^{-t}}
E[|\deg_t(w)-De^{-t}|\mid w\in S_t]dt  
\]
We shall show
\beq\label{main}
E[|\deg_t(w)-De^{-t}|\mid w\in S_t] = O((D(t+1)e^{-t})^{1/2})
\eeq
We note that $(t+1)^{1/2}(De^{-t})^{-1/2}e^{-t/k}$ is maximized at
$t=\omega$ where it is at most $\ln^{1/2}D$ so that, given (\ref{main}),
(\ref{twostar}) holds with $c=\frac{3}{2}$.
\section{Phantom Edges}
Given $\deg_t(w)$ what do we expect of $\deg_{t+dt}(w)$?  Let $e$ be
an edge containing $w$ at time $t$.  Roughly speaking each $v\in e$,
$v\neq w$ is removed with probability $\frac{dt}{k}$ so $e$ is
removed with probability $dt$.  Then $\deg_t(w)$ would drop by
$\deg_t(w)dt$ in time $dt$ giving exponential decay.  Renormalizing,
$e^t\deg_t(w)$ would be a martingale.
\par Well, not exactly.  The condition that $w$ itself survives has
a (small) effect.  For one thing, it may happen that an $e$ containing
$w$ is born and $w$ is revived.  It is helpful then to think of that
$e$ as a {\em phantom edge} which then experiences exponential decay.
Formally we define
\beq\label{phan} PHAN_t = \sum_{t'}e^{-(t-t')} \eeq
where the sum is over all those times $t'\leq t$ when $w$ has been
revived. (If $w$ hasn't been revived $PHAN_t=0$.)  
Note $PHAN$ is never negative.
We define the adjusted degree $X_t$ by
\[  X_t = \deg_t(w) + PHAN_t  \]
and normalize by setting
\beq\label{defz}  Z_t = e^tX_t  \eeq
so that
\[
|\deg_t(w)-De^{-t}| \leq e^{-t}|Z_t-D| + PHAN_t
\]
so that (\ref{main}) will follow from
\beq\label{maina}
E[|Z_t-D|\mid w\in S_t] = O((D(t+1)e^t)^{1/2})
\eeq
and the relatively easier
\beq\label{mainb}
E[PHAN_t\mid w\in S_t] = O((D(t+1)e^{-t})^{1/2})
\eeq
We show (\ref{maina}) by employing the general inequality
$E[|W|]\leq E[W^2]^{1/2}$ and showing
\beq\label{mainc}
E[(Z_t-D)^2\mid w\in S_t] = O(D(t+1)e^t) 
\eeq
\par We think of (\ref{mainc}) as the core of our argument.  The idea
will be that $Z_t$ is a continuous time martingale.  But not
exactly.  Essentially, conditioning on $w$ surviving means
the edges $e$ containing $w$ are not born so the vertices $v$ on such edges
have slightly less chance of being removed.  But it will be close enough.
Indeed, this motivates our choice (\ref{omega}) of $\omega$ since we want
the difference of one in the degree to have negligible effect.


\section{Almost a Martingale}
We want to show (\ref{mainc}) for a given $t\leq\omega$.  We shall examine
$X_s$ for $0\leq s \leq t$.
\\ {\bf Claim:}  Let $0\leq s <t$ and let $H_s$ be any value with $w\in H_s$.
Then
\[  E[X_{s+ds}-X_s\mid H_s, w\in S_t] = -X_sds + \alpha X_s ds \]
with $\abound$. 
\par The $\alpha$ represents an ``error term'' caused by the effective
degree loss. Applying (\ref{bttf}) it suffices to show
\beq\label{claim1} E[X_{s+ds}-X_s\mid H_s, w\in S_{s+ds}] = -X_sds +
\alpha X_sds \eeq
with $\abound$.
\par If an edge $e$ with $w\in e$ is born and $w$ is revived then
the new term in $PHAN_{s+ds}$ balances the loss in $\deg_{s+ds}w$.
(The edge is counted as a phantom edge.)  
Now consider the contribution to the expectation when no
such $e$ is born.  Automatically
\[ PHAN_{s+ds}=PHAN_se^{-ds}=PHAN_s-PHAN_sds \]
so $PHAN$ has no error term.  Dealing with $\deg_{s+ds}(w)$ is 
somewhat more technical.
\par Let $v$ be a vertex sharing a common edge $e$ with $w$.  Suppose
$\deg_s(v)=De^{-s}-\Delta$ with $\Delta\geq 0$.  There are $\deg_s(v)-1$
edges $e'\neq e$ containing $e$ that might be born and $v$ might be 
wasted so $v$ has probability $\frac{dt}{k}(1-\frac{1}{De^{-s}})$ of
being removed.  Suppose $\deg_s(v)=De^{-s}+\Gamma$ with $\Gamma\geq 0$.
There are $\deg_s(v)-1$ edges $e'\neq e$ containing $v$ that might be
born and $v$ then must not be revived so $v$ has probability
$\frac{dt}{k}(1-\frac{1}{De^{-s}+\Gamma})$ of being removed.  In any
case it has probability $\frac{dt}{k}(1-\alpha)$ of being removed
with $\abound$. 
\par Let $e$ be an edge containing $w$.  No event (we've excluded the
birth of $e$ already) can remove two $v,v'\in e$ since they share only
the one common edge $e$.  ($H$ is simple.)  Thus $e$ is removed with
probability $(1-\alpha)dt$ with $\abound$.  By Linearity of Expectation
\[ E[\deg_{s+ds}(w)-\deg_s(w)] = -\deg_s(w)(1-\alpha)ds \]
with $\abound$. As $PHAN$ is positive or zero, $\deg_s(w)\leq X_s$
and
\[ E[X_{s+ds}-X_s] = -X_sds + \alpha\deg_s(w)ds = -X_sds +\alpha X_sds \]
where the new $\alpha$ still satisfies $\abound$.  This completes
(\ref{claim1}) and hence the Claim.
\\ {\em Remark.} The above claim can also be stated and proven without
the use of infinitesimals, giving a bound on $E[X_{s+\Delta s}-X_s]$.  In
that case there would be an additional additive term $\ohs$ with the
implicit constant dependent on the hypergraphs $H$.  Letting $\Delta
s\rightarrow 0$ the results below would be the same.  
\par We normalize with $Z_s$ given by (\ref{defz}).  Then
\beq\label{plus} E[Z_{s+ds}-Z_s] = (e^s+e^sds)(X_s-X_sds+\alpha X_sds)
-e^sX_s = \alpha Z_sds 
\eeq
which, as $\alpha$ is small, justifies our statement that $Z_s$ is almost a
martingale.  We close with two rough upper bounds that shall be convenient
later.  As $\alpha$ is always nonnegative $E[Z_{t+dt}|Z_t]\geq Z_t$ for all
$t$ so for any $s'\leq s$
\[ E[Z_s|Z_{s'}] \geq Z_{s'}  \]
As $\alpha\leq \frac{1}{De^{-t}}$ we have in the other direction
\[ E[Z_{t+dt}|Z_t]\leq Z_t\left(1+\frac{dt}{De^{-t}}\right) \leq
Z_t \exp\left(\frac{dt}{De^{-t}}\right) \]
so for any $s'\leq s$
\beq\label{imp}
Z_{s'} \leq E[Z_s|Z_{s'}] \leq Z_{s'}\exp[\int_{s'}^s \frac{dt}{De^{-t}}]
=  Z_{s'} e^{(e^{s}-e^{s'})/D}
\eeq

\par Our choice of $\omega$ assures that
$(e^{s}-e^{s'})/D$ is small so employing the
inequality $e^x\leq 1+2x$ valid for $0\leq x < 1$
we rewrite (\ref{imp}) as

\beq\label{ub1}
Z_{s'} \leq E[Z_s|Z_{s'}]\leq Z_{s'}[1+ 2\frac{e^{s}-e^{s'}}{D}]
\eeq
and our choice of $\omega$ further assures
\[
Z_{s'} \leq E[Z_s|Z_{s'}]\leq Z_{s'}[1+O(\ln^{-K}D)]
\]
for all $s',s$.  Recall $Z_0=D$.  This assures the very
rough, but useful
\beq\label{ub3} E[Z_s] \leq 2D \eeq


\section{The Variance}
Our object here will be to show (\ref{mainc}) in the form 
\beq\label{varbound}
E[(Z_t-D)^2] \leq  cD(t+1)e^t  \eeq
where, for definiteness, we set
\[  c=80 \]
We actually show the following.
\\{\bf Lemma:} {\em If} $E[(Z_s-D)^2] \leq  cD(s+1)e^s$ for all $s\leq t$
{\em then} $E[(Z_t-D)^2] < cD(t+1)e^t$.
\par Assume this Lemma and consider the
function $f(t)=E[(Z_t-D)^2]-cD(t+1)e^t$. $f$ is a continuous function for
$0\leq t\leq \omega$ and $f(0)=-cD < 0$. If some $f(t_1)>0$
then by the Intermediate Value Theorem some $f(t_2)=0$
and by continuity there would be a minimal $t$ with $f(t)=0$.
But then $f(s)\leq 0$ for $s\leq t$ so $f(t)<0$, a contradiction.
Hence all $f(t_1)\leq 0$, which is precisely (\ref{varbound}).
\par Note $Z_0=D$, constant.  Our idea is that $Z_s$, $0\leq s\leq t$, 
is almost a continuous time martingale.  
\subsection{The SplitUp}
We split $[0,t]$ into intervals $[s,s+ds]$
and write
\[ Z_t-D = \sum_s (Z_{s+ds}-Z_s) \]
with $s$ from $0$ to $t-ds$ in steps of $ds$.  
(Again we can avoid infinitesimals by making these
steps $\Delta s$ and letting $\Delta s \rightarrow
0$ at the end.)
Squaring and taking expectation
\[  E[(Z_t-D)^2] = VAR + COV  \]
where the squared terms give the ``variance''
\beq\label{VAR} 
VAR = \sum_s E[(Z_{s+ds}-Z_s)^2] 
\eeq
and the crossterms give the ``covariance''
\[ COV = 2\sum_s \sum_{s<s'} E[(Z_{s+ds}-Z_s)(Z_{s'+ds'}-Z_{s'})]  \]
For fixed $s$ the inner sum over $s'$ telescopes giving
\beq\label{COV} 
COV = 2\sum_s E[(Z_{s+ds}-Z_s)(Z_t-Z_{s+ds})] 
\eeq 

\subsection{The Variance Terms}
Here we bound $VAR$ by bounding each term.
When $\deg_{s+ds}(w)=\deg_s(w)$ or when
an edge $e$ containing $w$ was born but $w$ was revived then
$Z_{s+ds}- Z_s$ is a $ds$ term and since it is squared we
can ignore it.  For each edge $e$ containing
$w$ there is probability at most $ds$ that some
$v\in e$ is removed so in total there is probability at 
most $\deg_s(w)ds \leq X_sds$ that $\deg(w)$ goes
down.  We come to a key point called {\em limited effect}.  The
birth of a single edge $e'$ can only decrease $\deg(w)$ by at most
$k+1$.  The reason is that $e'$ has only $k+1$ vertices $v$ and
each $v$ can lie on at most one common edge $e$ with $w$.  (Here
we make critical use of $H$ being simple.)  Such a birth will
decrease $Z$ by at most $e^s(k+1)$.  Therefore the contribution
to $E[(Z_{s+ds}-Z_s)^2]$ from such births is at most
$e^{2s}(k+1)^2X_sds = (k+1)^2e^sZ_sds$.  That is,
\[
E[(Z_{s+ds}-Z_s)^2] \leq (k+1)^2e^sZ_sds
\]
and ``summing'' gives
\[
VAR \leq (k+1)^2\int_0^t e^sE[Z_s]ds \leq 2(k+1)^2De^t  
\]
employing the rough bound (\ref{ub3}).

\subsection{The Covariance Terms}
 {\em Remark.}  It is here that our approach differs from previous
sequential approaches (including our own!) to asymptotic packing.
With sequential approaches at each step there are random  oscillations
and the degrees move from what they should be.  With previous approaches
the total ``error'' for a degree is basically the sum of the errors.
But here we create a martingale (almost) environment so that the
errors are basically independent of each other.  With that the
square of the total error will be close to
the sum of the squares of the
individual errors.
\par Here we bound $COV$. Consider a term of (\ref{COV}) with $s<t$.  
We first bound $E[|Z_{s+ds}-Z_s|]$.
As $E[Z_{s+ds}-Z_s] \geq 0$ 
we bound by twice the contribution with $Z_{s+ds}\geq Z_s$.
This occurs when ``nothing'' happens and $\deg(w)$ remains
the same.  Then $Z_{s+ds}\leq Z_se^{ds} = Z_s + Z_sds$
(neglecting the squared infinitesimal terms) so that
\[
E[|Z_{s+ds}-Z_s|]\leq 2Z_sds
\]
We employ (\ref{ub1}) to give
\beq\label{restok}
0\leq E[Z_t-Z_{s+ds}] \leq Z_{s+ds}
\frac {2(e^t-e^{s+ds})}{D}\leq Z_s\frac{4e^t}{D}
\eeq
for any value of $H_{s+ds}$.  Unfortunately, the
two variables $Z_{s+ds}-Z_s$, $Z_t-Z_{s+ds}$ are
not necessarily independent.  But since (\ref{restok}) holds
for any $H$ we bound
\[
E[|(Z_{s+ds}-Z_s)(Z_t-Z_{s+ds})|]\leq
2Z_s^2\frac{4e^t}{D}ds
\]
and hence
\[
COV \leq \frac{8e^t}{D}\sum_s E[Z_s^2]ds
\]

\par We need a bound on $E[Z_s^2]$ for $s\leq t$.  We first bound
\[ E[Z_s^2]\leq E[Z_s]^2+Var[Z_s] \leq 4D^2 + E[(Z_s-D)^2] \]
using (\ref{ub3}) and the bound $Var[Z]\leq E[(Z-a)^2]$ valid for
any $a$.  Now the {\em assumption} of our Lemma gives
\[ E[Z_s^2] \leq 4D^2 + cD(s+1)e^s\leq 5D^2  \]
since $s\leq\omega$.  Therefore
\[
COV \leq \frac{8e^t}{D}\int_0^t 5D^2\cdot dt\leq
40te^tD
\]
so that
\[
E[(Z_t-D)^2] \leq VAR+COV \leq 80(t+1)e^tD
\]
completing the Lemma.







\section{Few Phantoms}
Bounding $E[PHAN_t]$ is eased by the rough idea that the revival of $w$
at time $s$ makes revivals at later times less likely as it lowers the
degree.  More formally, as $X_s\geq \deg_s(w)$ the probability $w$ is
revived at time $s$ is at most
\[ \frac{|X_s-De^{-s}|}{kDe^{-s}}ds  \]
For if $\deg_s(w)\leq De^{-s}$ then $w$ cannot be revived and otherwise
$|X_s-De^{-s}|= X_s-De^{-s}\geq \deg_s(w)-De^{-s}$.  
\par We condition on $w\in S_t$.  For $s\leq t$ our main (\ref{main})
(combined with general principle (\ref{bttf})) gives
\[ \frac{E[|X_s-De^{-s}|]}{kDe^{-s}} = O((D(s+1)e^{-s})^{-1/2})  \]
A revival at time $s$ has weight $e^{s-t}$ in $PHAN_t$ so that
\[
 E[PHAN_t]=O\left( \int_{s=0}^t (D(s+1)e^{-s})^{-1/2}e^{s-t}ds\right)
\]
But then $E[PHAN_t]=O(D^{-1/2}(t+1)^{-1/2}e^{t/2})$  which is actually
$o(1)$ so that (\ref{mainb}) holds with room to spare.  This completes our
proof.

\begin{thebibliography}{99}
 
\bibitem{AKS} N. Alon, J.-H. Kim and J. Spencer,
Nearly perfect matchings in regular simple hypergraphs, {\em
Israel J. Math.} (to appear)

\bibitem{EH} P. Erd\H{o}s and H. Hanani, On a limit theorem in
combinatorial analysis, {\em Publ. Math. Debrecen}, 10 (1963),
10-13.
 
\bibitem{R} V. R\"odl, On a packing and covering problem,
{\em European Journal of Combinatorics}, 5 (1985), 69-78.
 

\bibitem{RT} V. R\"odl and L. Thoma,
{\em Asymptotic packing and the random greedy algorithm},
Random Structures \& Algorithms 8 (1996), 161-178

\bibitem{PS} N. Pippenger and  J. Spencer,
 Asymptotic Behavior of the Chromatic Index for Hypergraphs, {\em J. Comb.
Th. - Ser. A} 51 (1989), 24-42.
 
\bibitem{S} J. Spencer,
{\em Asymptotic packing via a branching process},
Random Structures \& Algorithms 7 (1995), 167-172 

\end{thebibliography}

\end{document}