Real Time Asymptotic Packing

Joel Spencer

                                spencer@cs.nyu.edu
                           Courant Institute, New York

Submitted: May 7, 1966. Accepted: June 12, 1996.

1

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^{c} D) of the vertices.

Let H = (V, E) be a (k + 1)-uniform hypergraph on N vertices. A packing P is a family of disjoint edges. Given P we correspond the set S = V − ⋃ P of those vertices v not in the packing, these v we call surviving vertices. We shall assume:

• H is simple. That is, any two vertices are in at most one edge.

• H is regular of degree D. That is, every vertex v lies in precisely D e ∈ E.

We are interested in the asymptotics for k fixed, D, N → ∞. We assume k ≥ 2 is fixed throughout. We show Theorem. There exists a packing with

|S| = O(ND^{−1/k} ln^{c} D)

where c depends on k. (We make no attempt to optimize c.)

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 §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.

The study of asymptotic packing can be said to date from the proof by V. Rödl [3] of a classic conjecture of Paul Erdős and Haim Hanani [2]. Rödl showed that for l < k fixed and n → ∞ there exists a “packing” P of ∼ \binom{n}{l}/\binom{k}{l} k-element subsets of an n-element universe Ω so that every l points of Ω lie in at most one of the k-sets. This was nicely generalized by N. Pippenger in work appearing [5] jointly with this author. He showed that any k-uniform hypergraph on N vertices with deg(v) ∼ 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 → ∞.) 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 ≥ 3) in our joint paper [1] by quite different techniques.

1AMS(1991) Subject Classification: Primary 05B40, Secondary 60D05

1 Two Simple Algorithms

We first define the discrete random greedy algorithm in a natural way. Randomly order e_{1}, …, e_{ω}, ω = |E|, the edges of H. Set P_{0} = ∅, S_{0} = V. For 1 ≤ i ≤ ω if e_{i} ⊆ S_{i−1} then set P_{i} = P_{i−1} ∪ {e_{i}} and S_{i} = S_{i−1} − e_{i}, 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_{ω}|] meets the bounds of our Theorem. This author [6] and, independently, V. Rödl and L. Thoma [4] have shown that E[|P_{ω}|] ∼ \frac{N}{k+1} or equivalently that E[|S_{ω}|] = 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

E[|S_{ω}|] = O(ND^{−1/k+o(1)})  (??)  (1)

Now we define the 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 − ⋃ P_{t}. We let H_{t} denote the restriction of H to S_{t}. If by time t edge e ⊆ 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′ ∩ e ≠ ∅ are no longer considered.

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 ω = ln D. We now give a heuristic guide which should motivate the full process we define later. Let deg_{t}(v) be (for v ∈ S_{t}) the degree of v in H_{t} and suppose all deg_{t}(v) ∼ f(t)D. There would be ∼ 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^{2}e^{t} \frac{dt}{kD} = e^{t}f^{2}(t)D · dt. If this is to be f(t + dt)D then we would need

f(t + dt) = f(t) − e^{t}f^{2}(t)dt
f′(t) = −e^{t}f^{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.

Suppose v has survived to time t. It lies on ∼ 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[− ∫_{0}^{t} \frac{dt}{k}] = e^{−t/k}. Since we want deg(v) ∼ De^{−t} but deg(v) is integral we can only hope to carry this approximation through time ω = ln D. At that time Pr[v ∈ S_{t}] would be e^{−t/k} = D^{−1/k}. By Linearity of Expectation we would have E[|S_{ω}|] = ND^{−1/k}.

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.

2 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 ∈ e are removed from S and all e′ containing any such v are deleted. We add two stabilization mechanisms. On certain occasions we 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 ∈ e we revive v. When this occurs v is “put back” into S and the edges e′ ≠ e containing v are put back into H. (A vertex v ∈ 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 ∈ 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.)

Here are the probabilities. Suppose deg_{t}(v) = De^{−t} − Δ with Δ ≥ 0. Then v is wasted in the time interval [t, t + dt] with probability \frac{Δ}{kDe^{−t}} dt. Suppose deg_{t}(v) = De^{−t} + Γ with Γ ≥ 0. If an edge e containing v is born then v is revived with probability \frac{Γ}{De^{−t}+Γ}. The a priori probability that v is revived is then

deg_{t}(v)\frac{dt}{kDe^{−t}} \frac{Γ}{De^{−t} + Γ} = \frac{Γ}{kD^{−t}} dt

This gives a convenient symmetry:

Pr[v revived or wasted] = \frac{| deg_{t}(v) − De^{−t}|}{kDe^{−t}}dt  (2)

Consider any v at time t. Suppose deg_{v}(t) = De^{−t} − Δ with Δ ≥ 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 Δ ≥ 0) and probability \frac{Δ}{kDe^{−t}} dt that v is wasted; so probability \frac{dt}{k} that v ∉ S_{t+dt}. Suppose deg_{t}(v) = De^{−t} + Γ with Γ ≥ 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{Γ}{De^{−t}+Γ}) = \frac{dt}{k}. That is, for any value H_{t} of the process at time t with v ∈ S_{t}

Pr[v ∉ S_{t+dt} | H_{t}] = \frac{dt}{k}  (3)

Indeed, (3) is the purpose of our stabilization. We deduce

Pr[v ∈ S_{t}] = e^{− ∫_{0}^{t} \frac{dt}{k}} = e^{−t/k}  (4)

Let X be any random variable that depends only on the history of the process up to time s. Then

E[X|w ∈ S_{t}] = E[X|w ∈ S_{s}]  (5)

The reason is that any history up to time s with w ∈ S_{s} has precisely the same probability e^{−(t−s)/k} of being extended to a history up to time t with w ∈ S_{t}.

3 The Big Picture

We set

ω = ln D − K ln ln D  (6)

(K a suitably large constant) and continue the process (starting at time zero) to time ω. Call e a false birth if e is born at time t but at some time t′ < t some v′ ∈ 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 − ⋃ P^{∗}.

For each vertex w let SURV_{w} be the indicator for w ∈ S_{ω}; W AST E_{w} the number of times (zero or one) that w is wasted; REV IV E_{w} the number of times w is revived. S^{∗} consists of surviving vertices, wasted vertices, and vertices in false births so

|S^{∗}| ≤ ∑_{w} SURV_{w} + W AST E_{w} + (k + 1)REV IV E_{w}

As constants do not concern us we define

LOSS_{w} = W AST E_{w} + REV IV E_{w}

so we can bound more conveniently

|S^{∗}| ≤ ∑_{w} SURV_{w} + (k + 1)LOSS_{w}

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 (4)

E[SURV_{w}] = Pr[w ∈ S_{ω}] = e^{−ω/k} = D^{−1/k} ln^{K/k} D

Now it suffices to show

E[LOSS_{w}] = O(D^{−1/k} ln^{c} D)  (7)

Fix w and consider E[LOSS_{w}]. For every t (2) gives the probability w is wasted or revived. However, this is conditional on w ∈ S_{t} which occurs with probability e^{−t/k}. Thus

E[LOSS_{w}] = ∫_{t=0}^{ω} \frac{e^{−t/k}}{kDe^{−t}} E[| deg_{t}(w) − De^{−t}| | w ∈ S_{t}]dt

We shall show

E[| deg_{t}(w) − De^{−t}| | w ∈ S_{t}] = O((D(t + 1)e^{−t})^{1/2})  (8)

We note that (t + 1)^{1/2}(De^{−t})^{−1/2}e^{−t/k} is maximized at t = ω where it is at most ln^{1/2} D so that, given (8), (7) holds with c = \frac{3}{2}.

4 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 ∈ e, v ≠ 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.

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 phantom edge which then experiences exponential decay. Formally we define

P HAN_{t} = ∑_{t′} e^{−(t−t′)}  (9)

where the sum is over all those times t′ ≤ t when w has been revived. (If w hasn’t been revived P HAN_{t} = 0.) Note P HAN is never negative. We define the adjusted degree X_{t} by

X_{t} = deg_{t}(w) + P HAN_{t}

and normalize by setting

Z_{t} = e^{t}X_{t}  (10)

so that

| deg_{t}(w) − De^{−t}| ≤ e^{−t}|Z_{t} − D| + P HAN_{t}

so that (8) will follow from

E[|Z_{t} − D| | w ∈ S_{t}] = O((D(t + 1)e^{t})^{1/2})  (11)

and the relatively easier

E[P HAN_{t} | w ∈ S_{t}] = O((D(t + 1)e^{−t})^{1/2})  (12)

We show (11) by employing the general inequality E[|W |] ≤ E[W^{2}]^{1/2} and showing

E[(Z_{t} − D)^{2} | w ∈ S_{t}] = O(D(t + 1)e^{t})  (13)

We think of (13) 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 (6) of ω since we want the difference of one in the degree to have negligible effect.

5 Almost a Martingale

We want to show (13) for a given t ≤ ω. We shall examine X_{s} for 0 ≤ s ≤ t. Claim: Let 0 ≤ s < t and let H_{s} be any value with w ∈ H_{s}. Then

E[X_{s+ds} − X_{s} | H_{s}, w ∈ S_{t}] = −X_{s}ds + αX_{s}ds

with 0 ≤ α ≤ \frac{1}{De^{−s}}.

The α represents an “error term” caused by the effective degree loss. Applying (5) it suffices to show

E[X_{s+ds} − X_{s} | H_{s}, w ∈ S_{s+ds}] = −X_{s}ds + αX_{s}ds  (14)

with 0 ≤ α ≤ \frac{1}{De^{−s}}.

If an edge e with w ∈ e is born and w is revived then the new term in P HAN_{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

P HAN_{s+ds} = P HAN_{s}e^{−ds} = P HAN_{s} − P HAN_{s}ds

so P HAN has no error term. Dealing with deg_{s+ds}(w) is somewhat more technical.

Let v be a vertex sharing a common edge e with w. Suppose deg_{s}(v) = De^{−s} − Δ with Δ ≥ 0. There are deg_{s}(v) − 1 edges e′ ≠ 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} + Γ with Γ ≥ 0. There are deg_{s}(v) − 1 edges e′ ≠ 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}+Γ}) of being removed. In any case it has probability \frac{dt}{k}(1 − α) of being removed with 0 ≤ α ≤ \frac{1}{De^{−s}}.

Let e be an edge containing w. No event (we’ve excluded the birth of e already) can remove two v, v′ ∈ e since they share only the one common edge e. (H is simple.) Thus e is removed with probability (1 − α)dt with 0 ≤ α ≤ \frac{1}{De^{−s}}. By Linearity of Expectation

E[deg_{s+ds}(w) − deg_{s}(w)] = − deg_{s}(w)(1 − α)ds

with 0 ≤ α ≤ \frac{1}{De^{−s}}. As P HAN is positive or zero, deg_{s}(w) ≤ X_{s} and

E[X_{s+ds} − X_{s}] = −X_{s}ds + α deg_{s}(w)ds = −X_{s}ds + αX_{s}ds

where the new α still satisfies 0 ≤ α ≤ \frac{1}{De^{−s}}. This completes (14) and hence the Claim. Remark. The above claim can also be stated and proven without the use of infinitesimals, giving a bound on E[X_{s+Δs} − X_{s}]. In that case there would be an additional additive term O_{H}((Δs)^{2}) with the implicit constant dependent on the hypergraphs H. Letting Δs → 0 the results below would be the same.

We normalize with Z_{s} given by (10). Then

E[Z_{s+ds} − Z_{s}] = (e^{s} + e^{s}ds)(X_{s} − X_{s}ds + αX_{s}ds) − e^{s}X_{s} = αZ_{s}ds  (15)

which, as α 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 α is always nonnegative E[Z_{t+dt}|Z_{t}] ≥ Z_{t} for all t so for any s′ ≤ s

E[Z_{s}|Z_{s′}] ≥ Z_{s′}

As α ≤ \frac{1}{De^{−t}} we have in the other direction

E[Z_{t+dt}|Z_{t}] ≤ Z_{t} (1 + \frac{dt}{De^{−t}} ) ≤ Z_{t} exp (\frac{dt}{De^{−t}} )

so for any s′ ≤ s

Z_{s′} ≤ E[Z_{s}|Z_{s′}] ≤ Z_{s′} exp[∫_{s′}^{s} \frac{dt}{De^{−t}}] = Z_{s′}e^{(e^{s}−e^{s′})/D}  (16)

Our choice of ω assures that (e^{s} − e^{s′})/D is small so employing the inequality e^{x} ≤ 1 + 2x valid for 0 ≤ x < 1 we rewrite (16) as

Z_{s′} ≤ E[Z_{s}|Z_{s′}] ≤ Z_{s′}[1 + 2\frac{e^{s} − e^{s′}}{D}]  (17)

and our choice of ω further assures

Z_{s′} ≤ E[Z_{s}|Z_{s′}] ≤ Z_{s′}[1 + O(ln^{−K} D)]

for all s′, s. Recall Z_{0} = D. This assures the very rough, but useful

E[Z_{s}] ≤ 2D  (18)

6 The Variance

Our object here will be to show (13) in the form

E[(Z_{t} − D)^{2}] ≤ cD(t + 1)e^{t}  (19)

where, for definiteness, we set

c = 80

We actually show the following. Lemma: If E[(Z_{s} − D)^{2}] ≤ cD(s + 1)e^{s} for all s ≤ t then E[(Z_{t} − D)^{2}] < cD(t + 1)e^{t}.

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 ≤ t ≤ ω 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) ≤ 0 for s ≤ t so f(t) < 0, a contradiction. Hence all f(t_{1}) ≤ 0, which is precisely (19).

Note Z_{0} = D, constant. Our idea is that Z_{s}, 0 ≤ s ≤ t, is almost a continuous time martingale.

6.1 The SplitUp

We split [0, t] into intervals [s, s + ds] and write

Z_{t} − D = ∑_{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 Δs and letting Δs → 0 at the end.) Squaring and taking expectation

E[(Z_{t} − D)^{2}] = V AR + COV

where the squared terms give the “variance”

V AR = ∑_{s} E[(Z_{s+ds} − Z_{s})^{2}]  (20)

and the crossterms give the “covariance”

COV = 2 ∑_{s} ∑_{s<s′} E[(Z_{s+ds} − Z_{s})(Z_{s′+ds′} − Z_{s′})]

For fixed s the inner sum over s′ telescopes giving

COV = 2 ∑_{s} E[(Z_{s+ds} − Z_{s})(Z_{t} − Z_{s+ds})]  (21)

6.2 The Variance Terms

Here we bound V AR 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 ∈ e is removed so in total there is probability at most deg_{s}(w)ds ≤ X_{s}ds that deg(w) goes down. We come to a key point called 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)^{2}X_{s}ds = (k + 1)^{2}e^{s}Z_{s}ds. That is,

E[(Z_{s+ds} − Z_{s})^{2}] ≤ (k + 1)^{2}e^{s}Z_{s}ds

and “summing” gives

V AR ≤ (k + 1)^{2} ∫_{0}^{t} e^{s}E[Z_{s}]ds ≤ 2(k + 1)^{2}De^{t}

employing the rough bound (18).

6.3 The Covariance Terms

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.

Here we bound COV. Consider a term of (21) with s < t. We first bound E[|Z_{s+ds} − Z_{s}|]. As E[Z_{s+ds} − Z_{s}] ≥ 0 we bound by twice the contribution with Z_{s+ds} ≥ Z_{s}. This occurs when “nothing” happens and deg(w) remains the same. Then Z_{s+ds} ≤ Z_{s}e^{ds} = Z_{s} + Z_{s}ds (neglecting the squared infinitesimal terms) so that

E[|Z_{s+ds} − Z_{s}|] ≤ 2Z_{s}ds

We employ (17) to give

0 ≤ E[Z_{t} − Z_{s+ds}] ≤ Z_{s+ds} \frac{2(e^{t} − e^{s+ds})}{D} ≤ Z_{s} \frac{4e^{t}}{D}  (22)

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 (22) holds for any H we bound

E[|(Z_{s+ds} − Z_{s})(Z_{t} − Z_{s+ds})|] ≤ 2Z_{s}^{2} \frac{4e^{t}}{D} ds

and hence

COV ≤ \frac{8e^{t}}{D} ∑_{s} E[Z_{s}^{2}]ds

We need a bound on E[Z_{s}^{2}] for s ≤ t. We first bound

E[Z_{s}^{2}] ≤ E[Z_{s}]^{2} + V ar[Z_{s}] ≤ 4D^{2} + E[(Z_{s} − D)^{2}]

using (18) and the bound V ar[Z] ≤ E[(Z −a)^{2}] valid for any a. Now the assumption of our Lemma gives

E[Z_{s}^{2}] ≤ 4D^{2} + cD(s + 1)e^{s} ≤ 5D^{2}

since s ≤ ω. Therefore

COV ≤ \frac{8e^{t}}{D} ∫_{0}^{t} 5D^{2} · dt ≤ 40te^{t}D

so that

E[(Z_{t} − D)^{2}] ≤ V AR + COV ≤ 80(t + 1)e^{t}D

completing the Lemma.

7 Few Phantoms

Bounding E[P HAN_{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} ≥ 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) ≤ De^{−s} then w cannot be revived and otherwise |X_{s} − De^{−s}| = X_{s} − De^{−s} ≥ deg_{s}(w) − De^{−s}.

We condition on w ∈ S_{t}. For s ≤ t our main (8) (combined with general principle (5)) 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 P HAN_{t} so that

E[P HAN_{t}] = O (∫_{s=0}^{t}(D(s + 1)e^{−s})^{−1/2}e^{s−t}ds)

But then E[P HAN_{t}] = O(D^{−1/2}(t + 1)^{−1/2}e^{t/2}) which is actually o(1) so that (12) holds with room to spare. This completes our proof.

References

[1] N. Alon, J.-H. Kim and J. Spencer, Nearly perfect matchings in regular simple hypergraphs, Israel J. Math. (to appear)

[2] P. Erdős and H. Hanani, On a limit theorem in combinatorial analysis, Publ. Math. Debrecen, 10 (1963), 10-13.

[3] V. Rödl, On a packing and covering problem, European Journal of Combinatorics, 5 (1985), 69-78.

[4] V. Rödl and L. Thoma, Asymptotic packing and the random greedy algorithm, Random Structures & Algorithms 8 (1996), 161-178

[5] N. Pippenger and J. Spencer, Asymptotic Behavior of the Chromatic Index for Hypergraphs, J. Comb. Th. - Ser. A 51 (1989), 24-42.

[6] J. Spencer, Asymptotic packing via a branching process, Random Structures & Algorithms 7 (1995), 167-172