Perfect Matchings in Random s-Uniform Hypergraphs

Alan Frieze^{∗}  Svante Janson^{†}

October 10, 1997

1 Introduction

Let E = {X_{1}, X_{2}, …, X_{m}} where the X_{i} ⊆ V for 1 ≤ i ≤ m are distinct. The hypergraph G = (V, E) is said to be s-uniform if |X_{i}| = s for 1 ≤ i ≤ m. Thus, for example, a 2−uniform hypergraph is a graph. A set of edges M = {X_{i} : i ∈ I} is a perfect matching if

(i) i ≠ j ∈ I implies X_{i} ∩ X_{j} = ∅, and

(ii) ⋃_{i∈I} X_{i} = V.

In this paper we consider the question of whether a random s-uniform hypergraph contains a perfect matching. More precisely, where [k] = {1, 2, …, k}, we consider the random hypergraph G = G(n, m, s) = (V = [n], E = {X_{1}, X_{2}, …, X_{m}}) where the X_{i} are chosen randomly (without replacement) from the set \binom{V}{s} of all s-subsets of V. Equivalently we choose a hypergraph

∗Department of Mathematics, Carnegie Mellon University, Pittsburgh PA15213, U.S.A., Supported by NSF grant CCR-9225008

†Department of Mathematics, Uppsala University, PO Box 480, S-751 06 Uppsala, Sweden, Supported in part by the Göran Gustafsson Foundation for Research in Natural Sciences and Medicine.

Much of this work was done at the IMA Workshop on Emerging Applications of Probability at The University of Minnesota

uniformly at random from the set G(n, m, s) of all \binom{\binom{n}{s}}{m} s-uniform hypergraphs with vertex set [n] and m distinct edges.

To avoid trivialities we assume from now on that n → ∞ in steps of size s so that s | n always.

One of the most interesting and difficult problems in Probabilistic Combinatorics is to determine the threshold growth for m = m(n) so that when s is fixed

lim_{n→∞} Pr(G(n, m, s) has a perfect matching) = 1.  (1)

The case s = 2 was solved completely by Erdős and Rényi [6]. This is the question of when does the random graph G_{n,m} have a perfect matching whp.^{1} The first serious work on this problem for s ≥ 3 was done by Schmidt and Shamir [10]. Using the second moment method directly, they show that if m/n^{3/2} → ∞ then G(n, m, s) has a perfect matching whp. Since then, determining the threshold for (1) has become known as Shamir’s problem which seems to ignore Schmidt’s contribution.

Cooper, Frieze, Molloy and Reed [5] considered the problem of perfect matchings in random r-regular, s-uniform hypergraphs. Surprisingly, this seems to be an easier problem and is solvable by the Analysis of Variance method of Robinson and Wormald [8, 9]. In that paper they make the following conjecture which we repeat here:

CONJECTURE. Assume s is a positive integer constant and let

m = n(log n + c_{n})/s.

Then

lim_{n→∞} Pr(G has a perfect matching ) = \{ \begin{matrix}0 & c_{n} → −∞, \\ e^{−e^{−c}} & c_{n} → c, \\ 1 & c_{n} → ∞. \end{matrix}

The right-hand side of the above expression is simply the limiting probability that ⋃_{i=1}^{m} X_{i} = V.

1An event E_{n} is said to occur whp (with high probability) if Pr(E_{n}) = 1 − o(1) as n ⟶ ∞.

There has been no other progress on this problem as far as we can tell. Our main result is an improvement of the upper bound of Schmidt and Shamir to

Theorem 1 Let s ≥ 3 be fixed. If m/n^{4/3} → ∞, then the random hypergraph G(n, m, s) contains a perfect matching whp.

(The result and the proof below hold also for s = 2, but then the result by Erdős and Rényi [6] is much stronger.) Our proof is also by the second moment method, but we obtain some reduction in variance by sampling randomly from hypergraphs with a fixed degree sequence.

Schmidt and Shamir also considered the s-partite version of the problem. Here V = [n] is partitioned into s equally large sets V_{1}, V_{2}, …, V_{s} and the edges X_{i}, i = 1, 2, … m are chosen randomly from {X : |X| = s and |X ∩ V_{t}| = 1, t = 1, 2, …, s} i.e. each edge contains a single member of each V_{i}. Let G^{∗}(n, m, s) denote the random hypergraph produced. We will sketch a proof of

Theorem 2 Let s ≥ 3 be fixed. If m/n^{4/3} → ∞, then the random hypergraph G^{∗}(n, m, s) contains a perfect matching whp.

2 Proof of Theorem 1

We will consider (multi)hypergraphs with a fixed degree sequence. As an interim model we let G̃(n, m, s) be defined as follows: let x = x_{1}, x_{2}, …, x_{sm} be chosen randomly from [n]^{sm} i.e. x is a random sequence of integers from [n] (sampled with replacement). Let G(x) be the (multi)hypergraph with vertex set [n] and edges Ẽ_{i} = {x_{(i−1)s+1}, …, x_{is}} for 1 ≤ i ≤ m. Note that G(x) may contain repeated edges and deficient edges with fewer than s vertices. Let Ĝ = Ĝ(x) be obtained from G(x) by deleting edge repetitions and deficient edges.

Observe that if Ĝ has m̂ ≤ m edges then Ĝ is distributed as G(n, m̂, s), since each member of G(n, m̂, s) arises from the same number of x ∈ [n]^{sm} in this way. We define a perfect matching of G(x) to consist of n disjoint edges of size s and so we see that any perfect matching of G(x) is also a perfect matching of Ĝ. Since m̂ ≤ m and having a perfect matching is a monotone property we have

Pr(G(n, m, s) has a perfect matching) ≥ Pr(G(x) has a perfect matching)

and we can concentrate on showing that

G(x) has a perfect matching whp if m/n^{4/3} → ∞.  (2)

The degree deg_{x}(i) of i ∈ [n] in the hypergraph G(x) is simply |{j : x_{j} = i}|. For a fixed degree sequence d = d_{1}, d_{2}, …, d_{n} we let

X(d) = {x ∈ [n]^{sm} : deg_{x} = d},

where m = s^{−1} ∑_{i} d_{i} (we assume that this is an integer).

Schmidt and Shamir worked directly with G(n, m, s). We will work with G(x) where x is chosen randomly from X(d). This will eliminate some of the variability in the number of perfect matchings and enable us to improve their result.

A degree sequence is said to be ϵ-smooth if it satisfies properties P1–P4 below. The notation used is

d_{min} = min{d_{i} : 1 ≤ i ≤ n},
d = \frac{1}{n} ∑_{i=1}^{n} d_{i},
R = ∑_{i=1}^{n} d_{i}^{−1},
Q = ∑_{i=1}^{n} d_{i}^{−2}.

The properties are

P1 d_{min} > 0.

P2 d ≤ ϵn.

P3  |R − \frac{n}{d} | ≤ ϵ (\frac{n}{d})^{1/2}.

P4 Q ≤ ϵR.

Note that Jensen’s inequality (or the arithmetic-harmonic inequality) implies R ≥ n/d. Moreover, Cauchy-Schwarz’ inequality yields R^{2} ≤ nQ, and thus n/d ≤ R ≤ nQ/R or d ≥ R/Q. Hence P4 implies

P5 d ≥ 1/ϵ.

Our proof of (2) is divided into two lemmas. Since the probability of G(n, m, s) having a perfect matching increases with m, there is no loss in assuming that m = o(n).

Lemma 1 If x is chosen uniformly at random from [n]^{sm} where m = ωn^{4/3}, ω(n) → ∞ and ω(n) = o(n^{2/3}), then whp deg_{x} is ϵ(n)-smooth for some ϵ(n) → 0.

Lemma 2 Let (for each n) d be an ϵ(n)-smooth degree sequence where ϵ(n) → 0. Let x be chosen uniformly at random from X(d). Then whp

G(x) has a perfect matching.

2.1 Configuration Model

To analyse G(x) where x is chosen uniformly from X(d) we generalise the models of Bender and Canfield [1] and Bollobás [2] for the case of graphs with a fixed degree sequence (s = 2).

Let W_{i} = {i} × {d_{i}} for i = 1, 2, …, n and W = ⋃_{i=1}^{n} W_{i}. A configuration is a partition of W into m disjoint subsets of size s. Let Ω = Ω(d) be the set of all such configurations, and let F be chosen randomly from Ω.

For x = (v, i) ∈ W we let σ(x) = v. If F ∈ Ω and S ∈ F we let σ(S) = {σ(x) : x ∈ S}. We define the multihypergraph μ(F) = (V, E_{μ} = {σ(S) : S ∈ F }). It is not difficult to see that μ(F) and G(x), x ∈ X(d) have the same distribution. (We can generate x ∈ X(d) by taking d_{i} ”copies” of i for 1 ≤ i ≤ n and then placing these sm copies in random order. The relationship with μ(F) should be clear.) This idea was used in Bollobás and Frieze [3] and Bollobás, Fenner and Frieze [4] to analyse random graphs with minimum degree bounded from below.

Before continuing with the proofs of Lemmas 1 and 2 we need to define a perfect matching in F ∈ Ω(d).

A perfect matching M of F is a set {S_{i} : i ∈ I} ⊆ F such that

(i) |σ(S_{i})| = s, i ∈ I,

(ii) i, j ∈ I, i ≠ j implies σ(S_{i}) ∩ σ(S_{j}) = ∅, and

(iii) ⋃_{i∈I} σ(S_{i}) = V.

Thus F contains a perfect matching if and only if μ(F) contains one. If M is a perfect matching of F we let σ(M) = {σ(E_{i}) : i ∈ I} be the partition of [n] into s-sets that it induces.

We can now begin the proof proper.

2.2 Proof of Lemma 1

We first note that d = sm/n = sωn^{1/3}, which shows P2.

Next, d_{1}, d_{2}, … d_{n} are random variables, each having the binomial distribution Bi(sm, n^{−1}) = Bi(nd, n^{−1}). By standard estimates, whp

d_{min} ≥ sωn^{1/3}/2,

which will account for P1 and P4.

For P3 we have already observed that Jensen’s inequality implies R ≥ n/d. For an upper bound, we note that if d_{min} ≥ d/2, then

\frac{1}{d_{i}} = \frac{1}{d} + \frac{d − d_{i}}{dd_{i}} = \frac{1}{d} + \frac{d − d_{i}}{d^{2}} + \frac{(d − d_{i})^{2}}{d^{2}d_{i}} ≤ \frac{1}{d} + \frac{d − d_{i}}{d^{2}} + 2\frac{(d − d_{i})^{2}}{d^{3}}

and thus

R ≤ \frac{n}{d} + \frac{2}{d^{3}} ∑_{i=1}^{n}(d_{i} − d)^{2}.

Consequently, if δ = ω^{−1} then, Pr (|R − \frac{n}{d}| ≥ δ (\frac{n}{d})^{1/2}) ≤

≤ Pr (\frac{2}{d^{3}} ∑_{i=1}^{n}(d_{i} − d)^{2} ≥ δ (\frac{n}{d})^{1/2}) + Pr (d_{min} < \frac{d}{2})

≤ δ^{−1} (\frac{n}{d})^{−1/2} \frac{2}{d^{3}} E (∑_{i=1}^{n}(d_{i} − d)^{2}) + o(1)

= 2δ^{−1}n^{−1/2}d^{−5/2}nnd\frac{1}{n} (1 − \frac{1}{n}) + o(1)

< 2δ^{−1}n^{1/2}d^{−3/2} + o(1) = 2s^{−3/2}ω^{−1/2} + o(1) = o(1).

This verifies P3 and the Lemma follows.

2.3 Proof of Lemma 2

We will work with the configuration model and show that if F is chosen randomly from Ω(d) then whp

μ(F) has a perfect matching.  (3)

Let Y (F) denote the number of perfect matchings of F. Since

Pr(Y (F) > 0) ≥ \frac{E(Y)^{2}}{E(Y^{2})}

we can prove (3) by showing that

\frac{E(Y^{2})}{E(Y)^{2}} → 1 as n → ∞.

For positive integers a, b with a = sb let

ψ(a) = \frac{a!}{b!(s!)^{b}}

denote the number of ways of partitioning [a] into b s-subsets.

Then

E(Y) = d_{[n]}ψ(n)\frac{ψ(sm − n)}{ψ(sm)},

where

d_{S} = ∏_{i∈S} d_{i}  for S ⊆ [n].

Explanation: there are ψ(n) choices for the sets σ(S_{i}), i ∈ I of the perfect matching. There are then d_{[n]} choices for the sets S_{i}, i ∈ I and the remaining factor is the probability that F contains a particular matching.

Furthermore, where ν = n/s,

E(Y^{2}) = ∑_{k=0}^{ν} ∑_{|S|=ks} ψ(sk)ψ(n − sk)^{2}d_{[n]} ( ∏_{x∉S}(d_{x} − 1)) \frac{ψ(sm − 2n + sk)}{ψ(sm)}.

Explanation: we have to sum over the probabilities that two matchings M_{1}, M_{2} exist in F. In the above sum k denotes the size of M_{1} ∩ M_{2} and S = {x : x ∈ E ∈ σ(M_{1}) ∩ σ(M_{2})} ⊆ [n] is the set of σ images of elements of common edges. Having fixed k, S we determine σ(M_{1} ∩ M_{2}), σ(M_{1} \ M_{2}) and σ(M_{2} \ M_{1}). This gives ψ(sk)ψ(n − sk)^{2} choices. We then have to actually choose M_{1}, M_{2}. If x ∈ S there are d_{x} choices of w such that σ(w) = x and otherwise we must choose two distinct elements to map onto x which gives us a factor d_{x}(d_{x} − 1) for x ∈ S̄ = [n] \ S. The final factor is the probability that F contains the two matchings.

Hence,

\frac{E(Y^{2})}{E(Y)^{2}} = ∑_{k=0}^{ν} \frac{(sk)!}{k!} \frac{(n − sk)!^{2}}{(ν − k)!^{2}} \frac{(s(m − 2ν + k))!}{(m − 2ν + k)!} \frac{(sm)!}{m!} \frac{ν!^{2}}{n!^{2}} \frac{(m − ν)!^{2}}{(sm − n)!^{2}} D_{n−sk}

(4) where

D_{j} = d_{[n]}^{−1} ∑_{|A|=j} ∏_{x∈A}(d_{x} − 1), 0 ≤ j ≤ n.

Denote the combination of factorials in (4) by a_{k}, so that

\frac{E(Y^{2})}{E(Y)^{2}} = ∑_{k=0}^{ν} a_{k}D_{n−sk}.  (5)

By Stirling’s formula,

a_{k} = s^{1/2}k^{k(s−1)}(ν − k)^{2(s−1)(ν−k)}(m − 2ν + k)^{(s−1)(m−2ν+k)}
m^{(s−1)m}ν^{−2(s−1)ν}(m − ν)^{−2(s−1)(m−ν)}(1 + ε_{k}),  (6)

where ε_{k} = O (\frac{1}{k+1} + \frac{1}{ν−k+1}). Let x = k/ν, then (6) can be written, using m/ν = sm/n = d,

a_{k} = \sqrt{s}(1 + ε_{k}) [x^{x}(1 − x)^{2(1−x)}(d − 2 + x)^{d−2+x}d^{d}(d − 1)^{−2(d−1)}]^{(s−1)ν}
= \sqrt{s}(1 + ε_{k})e^{ν(s−1)f(x)}  (7)

with

f(x) = x log x + 2(1 − x) log(1 − x) + (d − 2 + x) log(d − 2 + x)
+ d log d − 2(d − 1) log(d − 1).

We have

f′(x) = log x − 2 log(1 − x) + log(d − 2 + x),
f′′(x) = \frac{1}{x} + \frac{2}{1 − x} + \frac{1}{d − 2 + x} > 0,  (8)

and find after simple calculations

f(1/d) = f′(1/d) = 0.

(This is thus the minimum of f.) We turn to the term D_{n−sk} in (5).

Lemma 3 If P1–P4 hold, then

D_{n−j} ≤ c_{j} exp(j − R − j log(j/R)),  (9)

with c_{j} = c_{j}(n) = O((j + 1)^{−1/2} + R^{−1/2}) (uniformly in j and n) and c_{j} ∼ (2πn/d)^{−1/2} for any sequence j = j(n) with j ∼ n/d.

Proof : Define the generating function

D(z) = ∑_{0}^{n} D_{n−j}z^{j} = ∏_{1}^{n} d_{k}^{−1} ∏_{1}^{n}(z + (d_{k} − 1)) = ∏_{1}^{n} (1 + \frac{z − 1}{d_{k}})

By Cauchy’s formula,

D_{n−j} = \frac{1}{2πi} ∮_{γ} D(z)z^{−j−1}dz

for any simple closed curve γ around the origin. We let γ be the circle |z| = r, where r will be chosen later, and obtain by taking absolute values

D_{n−j} ≤ \frac{1}{2π} ∫_{−π}^{π} |D(re^{it})|r^{−j}dt.  (10)

We next observe that if 0 ≤ r ≤ 1 and 0 ≤ a ≤ 1, then

|1 + a(re^{it} − 1)|^{2} = (1 − a(1 − r cos t))^{2} + a^{2}r^{2} sin^{2} t
= (1 − a(1 − r) − ar(1 − cos t))^{2} + a^{2}r^{2} sin^{2} t
= (1 − a(1 − r))^{2} − 2(1 − a(1 − r))ar(1 − cos t) +
a^{2}r^{2}(1 − 2 cos t + cos^{2} t + sin^{2} t)
≤ (1 − a(1 − r))^{2} − 2(1 − a(1 − r))ar(1 − cos t) +
a^{2}r(1 − a(1 − r))2(1 − cos t)
≤ (1 − a(1 − r) − ar(1 − cos t) + a^{2}r(1 − cos t))^{2}

and thus if 0 ≤ r ≤ 1,

|1 + a(re^{it} − 1)| ≤ 1 − a(1 − r) − (a − a^{2})r(1 − cos t).  (11)

(The right hand side is always ≥ 0, since it is so when r = 0 and r = 1).

If r > 1 we use (11) and the triangle inequality to obtain

|1 + a(re^{it} − 1)| ≤ |1 + a(e^{it} − 1)| + |ae^{it}(r − 1)|
≤ 1 − (a − a^{2})(1 − cos t) + a(r − 1),  r > 1

Hence we obtain, for every r and d_{j} ≥ 1,

|1 + d_{j}^{−1}(re^{it} − 1)| ≤ 1 + d_{j}^{−1}(r − 1) − (d_{j}^{−1} − d_{j}^{−2})(1 ∧ r)(1 − cos t)
≤ exp [d_{j}^{−1}(r − 1) − (d_{j}^{−1} − d_{j}^{−2})(1 ∧ r)(1 − cos t)]

and

|D(re^{it})| ≤ exp [∑_{j} d_{j}^{−1}(r − 1) − ∑_{j}(d_{j}^{−1} − d_{j}^{−2})(1 ∧ r)(1 − cos t)]
= exp[R(r − 1) − (R − Q)(1 ∧ r)(1 − cos t)].  (12)

We substitute the estimate (12) in (10) and pause for another lemma. Lemma 4 Let

φ(b) = \frac{1}{2π} ∫_{−π}^{π} e^{−b(1−cos t)}dt, b ≥ 0.

Then φ(b) = O(1 ∧ b^{−1/2}), and φ(b) = \frac{1}{\sqrt{2π}}b^{−1/2}(1 + o(1)) as b → ∞. Proof : Clearly φ(b) ≤ 1. On the other hand,

\sqrt{b}φ(b) = \frac{1}{2π} ∫_{−π\sqrt{b}}^{π\sqrt{b}} e^{−b(1−cos(u/\sqrt{b}))}du → \frac{1}{2π} ∫_{−∞}^{∞} e^{−u^{2}/2}du = \frac{1}{\sqrt{2π}}

as b → ∞ by dominated convergence

(exp(−b(1 − cos(u/\sqrt{b}))) ≤ exp (−\frac{2}{π^{2}} u^{2}) when |u| ≤ π\sqrt{b}) .

□

We may now complete the proof of Lemma 3. With φ as in Lemma 4, (10) and (12) yield

D_{n−j} ≤ r^{−j}φ((R − Q)(1 ∧ r)) exp(Rr − R).

We choose r = j/R and obtain

D_{n−j} ≤ φ ((1 − Q/R)(R ∧ j)) exp (j − R − j log(j/R)) ,

which is (9) with c_{j} = φ ((1 − Q/R)(R ∧ j)). The estimates for c_{j} follow from Lemma 4 because by assumptions P2–P4, n/d → ∞, R ∼ n/d and Q/R → 0. □

Continuing with the proof of Lemma 2, we define

g(x) = sx − R/ν − sx log(nx/R)

and obtain by Lemma 3 D_{n−sk} ≤ c_{sk} exp(νg(k/ν)) and thus by (5) and (7)

\frac{EY^{2}}{(EY)^{2}} ≤ ∑_{k=0}^{ν} \sqrt{s}(1 + ε_{k})c_{sk} exp (ν(s − 1)f(k/ν) + νg(k/ν)) .

Here we may absorb the factor 1+ε_{k} into c_{sk} without changing the estimates given in Lemma 3.

We also define

h(x) = (s − 1)f(x) + g(x)

and obtain

\frac{EY^{2}}{(EY)^{2}} ≤ ∑_{k=0}^{ν} \sqrt{s}c_{sk} exp(νh(k/ν)).  (13)

Differentiation yields, cf. (8),

g′(x) = −s log(nx/R)
g′′(x) = −\frac{s}{x}
h′′(x) = (s − 1)f′′(x) + g′′(x) = −\frac{1}{x} + \frac{2(s − 1)}{1 − x} + \frac{s − 1}{d − 2 + x} (14)

and (for d > 3)

h′′′(x) = \frac{1}{x^{2}} + \frac{2(s − 1)}{(1 − x)^{2}} − \frac{s − 1}{(d − 2 + x)^{2}} > 0.  (15)

Moreover, g(x) = sx (log \frac{R}{nx} − \frac{R}{nx} + 1)) ≤ 0, and so, using P3 again,

h(1/d) = g(1/d) = O (\frac{s}{d} (\frac{dR}{n} − 1)^{2}) = o (\frac{1}{ν} ) ,  (16)

h′(1/d) = g′(1/d) = s log(Rd/n) = o ((\frac{d}{ν} )^{1/2}) ,  (17)
h′′(1/d) = −d + O(1).  (18)

If all d_{i} are equal to d, R = n/d and h has a (local) maximum 0 at 1/d; in general h has a small positive maximum close to 1/d.

As we will see shortly, the main contribution to the sum in (13) indeed comes from terms with k/ν close to 1/d. Note, however, that for larger x, h(x) has a minimum and then increases again, and we have to check that h(x) is small for large x. We argue as follows, assuming that n, and thus d, is large enough (note that P5 shows that d → ∞).

By (14) and (15), h′′ increases from −∞ to +∞ on (0, 1); hence h′′ is negative, and h concave, on (0, x_{0}] while h is convex on [x_{0}, 1) for some x_{0} ∈ (0, 1). By (14), h′′(1/2s) < 0 and thus x_{0} > 1/2s. Moreover, if x ∈ (0, 2/d), then (14) yields

h′′(x) < −d/2 + O(1) < −d/3  (19)

and thus by a Taylor expansion and the inequality ab ≤ 3a^{2} + \frac{1}{12}b^{2} (a case of the arithmetic-geometric inequality), using (16) and (18),

h(x) ≤ h (\frac{1}{d}) + (x − \frac{1}{d}) h′ (\frac{1}{d}) − \frac{1}{2} (x − \frac{1}{d})^{2} \frac{d}{3}
≤ 0 + \frac{3}{d} |h′ (\frac{1}{d})|^{2} + \frac{1}{12}d (x − \frac{1}{d})^{2} − \frac{1}{6}d (x − \frac{1}{d})^{2}
= −\frac{1}{12}d (x − \frac{1}{d})^{2} + o (\frac{1}{ν} ) ,  0 ≤ x ≤ \frac{2}{d}.  (20)

In particular, h(2/d) ≤ −\frac{1}{12d} + \frac{1}{ν}.

By (17) and (19), also

h′ (\frac{2}{d}) ≤ h′ (\frac{1}{d}) − \frac{d}{3} · \frac{1}{d} = −\frac{1}{3} + o ((\frac{d}{ν} )^{1/2}) < −\frac{1}{4},

and since h′ is decreasing on [0, x_{0}], we obtain

h(x) ≤ h (\frac{2}{d}) − \frac{1}{4} (x − \frac{2}{d}) ≤ −\frac{1}{12d} − \frac{1}{4} (x − \frac{2}{d}) + \frac{1}{ν}, \frac{2}{d} ≤ x ≤ x_{0}.

It follows that the sum of the terms in (13) with 2/d ≤ k/ν ≤ x_{0} is at most, for some C < ∞

C ∑_{j=0}^{∞} exp (−\frac{ν}{12d} − \frac{1}{4}j + 1) = O (e^{−ν/12d}) = o(1).

We also obtain

h(x_{0}) ≤ −\frac{x_{0}}{4} + O (\frac{1}{d}) ≤ −\frac{1}{9s},

while

f(1) = d log d−(d−1) log(d−1) = log d+(d−1) log (1 + \frac{1}{d − 1}) < log d+1

and, using P3 again,

g(1) = s − R/ν + s log(R/n) = O(1) − s log d + s log(Rd/n)
= −s log d + O(1)

whence

h(1) = (s − 1)f(1) + g(1) < − log d + O(1).

Since h is convex on [x_{0}, 1] we thus find h(x) ≤ max(h(x_{0}), h(1)) ≤ −\frac{1}{9s} on [x_{0}, 1], and the contribution to (13) from terms with k/ν > x_{0} is exponentially small.

Let Σ_{1} denote the sum of the remaining terms in (13), i.e. the sum of the terms with k < 2ν/d. Defining k(y) = ⌊ν/d + y\sqrt{ν/d}⌋ = ν(1/d + y/\sqrt{νd} + O(1/ν)), we rewrite the sum as an integral,

Σ_{1} = ∫_{−\sqrt{ν/d}}^{\sqrt{ν/d}+θ\sqrt{d/ν}}\sqrt{s}c_{sk(y)}e^{νh(k(y)/ν)}\sqrt{\frac{ν}{d}} dy,  (21)

where 0 ≤ θ ≤ 1. For any fixed real y, P2 yields k(y) ∼ ν/d; hence c_{sk(y)} ∼ (2πn/d)^{−1/2} by Lemma 3. A Taylor expansion yields

h(k(y)/ν) = h(1/d) + (y/\sqrt{νd} + O (\frac{1}{ν} )) h′(1/d)
− \frac{1}{2} (y/\sqrt{νd} + O (\frac{1}{ν} ))^{2} h′′ (\frac{1}{d}) + O ((\frac{1}{\sqrt{νd}})^{3} d^{2})

= −\frac{y^{2}}{2ν} + o (\frac{1}{ν} ) .

Hence the integrand in (21) is asymptotically equal to

s^{1/2}(2πn/d)^{−1/2}(ν/d)^{1/2}e^{−y^{2}/2} = (2π)^{−1/2}e^{−y^{2}/2}.

We can use dominated convergence in (21), because (20) yields

h(k(y)/ν) ≤ −\frac{d}{12} (\frac{y}{\sqrt{νd}})^{2} + O (\frac{1}{ν} ) = −\frac{y^{2}}{12ν} + O (\frac{1}{ν} )

while P2 and P3 yield R^{−1} = O(d/ν) and thus, rather crudely

c_{j} = O ((\frac{d}{ν} )^{1/2} + (1 − \frac{dj}{n} )_{+}) ,

which implies \sqrt{\frac{ν}{d}}c_{sk(y)} = O (1 + |y|), so the integrand is O((1 + |y|)e^{−y^{2}/12}). We thus get

Σ_{1} → ∫_{−∞}^{∞}(2π)^{−1/2}e^{−y^{2}/2}dy = 1,

which completes the proof of Lemma 2. □

3 Sketch proof of Theorem 2

We obtain the same expressions for E(Y) and E(Y)^{2} as before, except that n! = (sν)! is replaced by ν!^{s}, and similarly (sm)! by m!^{s} and (n − sm)! by (ν − m)!^{s}; moreover, D_{s(ν−k)} is replaced by ∏_{ℓ=1}^{s} D_{ν−k}^{(ℓ)}, where D_{i}^{(ℓ)} = ∏_{i=1}^{ν} d_{ℓi} ∑_{|A|=j} ∏_{i∈A}(d_{ℓi} − 1), (d_{ℓi})_{i} being the degrees in the ℓ’th partition.

This gives

\frac{E(Y^{2})}{E(Y)^{2}} = ∑_{k=0}^{ν} a_{k} ∏_{ℓ} D_{ν−k}^{(ℓ)}

where Stirling’s formula yields

a_{k} = (2πνx(1 − x)^{2}d(d − 2 + x)(d − 1)^{−2})^{(s−1)/2} (1 + ε_{k})e^{ν(s−1)f(x)}

with the same f(x) as before.

Let us define R^{(ℓ)} = ∑_{i=1}^{ν} d_{ℓi}^{−1} and R = ∑_{ℓ=1}^{s} R^{(ℓ)}. Since log x is concave, ∑_{ℓ=1}^{s} log R^{(ℓ)} ≤ s log(R/s), and Lemma 3 yields

∏_{ℓ=1}^{s} D_{ν−j}^{(ℓ)} ≤ ∏_{ℓ=1}^{s} c_{j}^{(ℓ)} exp (sj − R − sj log(sj/R))

or

∏_{ℓ=1}^{s} D_{ν−k}^{(ℓ)} ≤ ∏_{ℓ=1}^{s} c_{k}^{(ℓ)} exp(νg(k/ν)).

The proof is completed as before with minor differences; the important fact is that for x ∼ 1/d,

a_{k} ∼ (2πν/d)^{(s−1)/2}e^{ν(s−1)f(x)}

and

∏_{ℓ=1}^{s} c_{k}^{(ℓ)} ∼ (\frac{2πν}{d} )^{−s/2} ,

while we get a final factor (2πν/d)^{1/2} from the integration over y as before.□

4 Complements

4.1 The number of perfect matchings

In the case m/n^{4/3} → ∞ but m = O(n^{3/2}) (exactly the case not covered by Schmidt and Shamir [10]), our method also yields the asymptotic distribution of the number Y of perfect matchings, which turns out to be log-normal. For simplicity we consider only the multihypergraph G̃(n, m, s); we believe that the result carries over to G(n, m, s) and G^{∗}(n, m, s) (with slightly different constants) but we have not investigated this in detail. We conjecture also that the result below remains true when m/n^{3/2} → ∞, which in that case would yield an asymptotic normal distribution of Y, but that cannot be proved by the present method.

Theorem 3 Let s ≥ 2 be fixed. If m/n^{4/3} → ∞ but m = O(n^{3/2}), then, for the model G̃(n, m, s),

\frac{m}{n^{3/2}} (ln Y − α_{n}) →^{d} N (0, \frac{1}{2s^{2}} ) ,

where

α_{n} = \frac{n}{s} ln \frac{sm}{n} − (1 − \frac{1}{s}) n − \frac{n^{2}}{2s^{2}m} − \frac{(3s + 2)n^{3}}{12s^{3}m^{2}} + \frac{1}{2} ln s.

This result is new also for the case s = 2 (graphs), although Janson [7] has obtained similar results for G(n, m) = G(n, m, 2) when m/n^{3/2} is bounded below. In the overlapping case m ≍ n^{3/2}, the result of [7] can be written as above with α_{n} replaced by α_{n} + 3/4; in other words, the distributions of Y for G(n, m, 2) and G̃(n, m, 2) differ asymptotically by a shift by a factor e^{3/4}. (It can be shown that the deficient edges (loops) in G̃(n, m, 2) contribute a factor e^{−1/2} and the multiple edges a further factor e^{−1/4}.)

Proof The proof of Lemma 2 shows that if d is an ϵ(n)-smooth degree sequence where ϵ(n) → 0, then for the model G(x) with x chosen uniformly at random from X(d),

Var (\frac{Y}{EY} ) = \frac{E(Y^{2})}{E(Y)^{2}} − 1 → 0.

Moreover,

EY = b_{n} ∏_{i=1}^{n} d_{i}

with

b_{n} = \frac{ψ(n)ψ(sm − n)}{ψ(sm)} = \frac{n! (sm − n)! m!}{ν! (m − ν)! (sm)!}.

Hence,

\frac{Y}{b_{n} ∏_{i} d_{i}} →^{p} 1  (22)

and thus

ln Y − ln (b_{n} ∏_{i} d_{i}) →^{p} 0.  (23)

It follows by Lemma 1 that (22) and (23) hold also for G(x) with x chosen uniformly at random from [n]^{sm}. In the remainder of the proof we will use this model, i.e. G̃(n, m, s), and it suffices to show that for this model

\frac{m}{n^{3/2}} (ln (b_{n} ∏_{i} d_{i}) − α_{n}) →^{d} N(0, \frac{1}{2}s^{−2}),  (24)

or, equivalently, using again d = sm/n,

\frac{d}{n^{1/2}} (ln(∏_{i} d_{i}) + ln b_{n} − α_{n}) →^{d} N(0, \frac{1}{2}).  (25)

We first note that Stirling’s formula yields

ln b_{n} = (s − 1)ν ln ν + (s − 1)(m − ν) ln(m − ν) − (s − 1)m ln m
+ \frac{1}{2} ln s + o(1)
= (s − 1)ν((d − 1) ln(d − 1) − d ln d) + \frac{1}{2} ln s + o(1)
= (1 − s^{−1})n(− ln d − 1 + \frac{1}{2d} + \frac{1}{6d^{2}} + O(d^{−3})) + \frac{1}{2} ln s + o(1). (26)

Next, by the proof of Lemma 1 whp d_{min} > d/2, and then a Taylor expansion yields

ln ∏_{i=1}^{n} d_{i} − n ln d = ∑_{i=1}^{n} ln (1 + \frac{d_{i} − d}{d})

= ∑_{i=1}^{n} (∑_{k=1}^{5} \frac{(−1)^{k−1}}{k} (\frac{d_{i} − d}{d})^{k} + O ((\frac{d_{i} − d}{d})^{6}))

= ∑_{k=1}^{5} \frac{(−1)^{k−1}}{k} d^{−k}S_{k} + O (d^{−6}S_{6}) ,  (27)

where

S_{k} = ∑_{i=1}^{n}(d_{i} − d)^{k}.

It remains to analyse these random variables. Note first that

S_{1} = 0.  (28)

We claim that, for each k ≥ 2,

ES_{k} = O (nd^{⌊k/2⌋}) ,  (29)
VarS_{k} = O (nd^{k});  (30)

more precisely

ES_{2} = nd(1 − \frac{1}{n}) = nd + O(d),  (31)
ES_{3} = nd + O(d),  (32)
ES_{4} = 3nd^{2} + O(nd),  (33)

and, moreover,

n^{−1/2}d^{−1}(S_{2} − ES_{2}) →^{d} N(0, 2).  (34)

Postponing the proof of these claims, we find

Var (dn^{−1/2}d^{−k}S_{k}) = O(d^{2−k}) = o(1),  k ≥ 3,  (35)

and thus

dn^{−1/2} (d^{−k}S_{k} − d^{−k}ES_{k}) →^{p} 0,  k ≥ 3.  (36)

Moreover, if k ≥ 5, then

dn^{−1/2}d^{−k}ES_{k} = O (n^{1/2}d^{1−k+⌊k/2⌋}) = O (n^{1/2}d^{−2}) = o(1),  (37)

and thus also

dn^{−1/2}d^{−k}S_{k} →^{p} 0,  k ≥ 5.  (38)

Using (28), (38) and (36) in (27), we obtain

dn^{−1/2} (ln ∏_{i} d_{i} − (n ln d − \frac{1}{2}d^{−2}S_{2} + \frac{1}{3}d^{−3}ES_{3} − \frac{1}{4}d^{−4}ES_{4})) →^{p} 0, (39)

and, by (31)–(33),

dn^{−1/2} (ln ∏_{i} d_{i} − (n ln d − \frac{1}{2}nd^{−1} + \frac{1}{3}nd^{−2} − \frac{3}{4}nd^{−2}))

+ \frac{1}{2}n^{−1/2}d^{−1} (S_{2} − ES_{2}) →^{p} 0, (40)

whence (36) yields

dn^{−1/2} (ln ∏_{i} d_{i} − n ln d + \frac{1}{2}nd^{−1} + \frac{5}{12}nd^{−2}) →^{d} N(0, \frac{1}{2}).  (41)

Finally, (25) follows by (41) together with (26), which easily yields

ln b_{n} + n ln d − \frac{1}{2}nd^{−1} − \frac{5}{12}nd^{−2} = α_{n} + o(1).  (42)

It remains to verify (29)–(34). We will be somewhat sketchy. First, ES_{k} = nE(d_{1} − d)^{k}, with d_{1} ∼ Bi(nd, n^{−1}). We introduce the centered indicator variables

I′_{ji} = \{ \begin{matrix}1 − \frac{1}{n}, & if x_{j} = i, \\ −\frac{1}{n}, & if x_{j} ≠ i, \end{matrix} 1 ≤ j ≤ nd, 1 ≤ i ≤ n.

Then d_{i} − d = ∑_{j} I′_{ji}, and standard arguments yield (expanding the power and using the independence of the x_{i})

E(d_{i} − d)^{k} = E(∑_{j} I′_{ji})^{k} = O(d^{⌊k/2⌋}).

This proves (29) and more careful estimates yield (31)–(33). (Alternatively, we may verify (31)–(33), and (29) for the values of k that we need (k ≤ 6), using formulae for the first moments of a binomial distribution.)

It may be similarly shown that

Cov ((d_{1} − d)^{k}, (d_{2} − d)^{k}) = O(n^{−1}d^{k})

and thus

VarS_{k} ≤ nE(d_{1} − d)^{2k} + n(n − 1)Cov ((d_{1} − d)^{k}, (d_{2} − d)^{k}) = O(nd^{k}), which is (30).

Finally, the central limit theorem (34) may be proved by the method of moments. For example, if we introduce the indicator variables J_{jk} = I(x_{j} = x_{k}), j, k = 1, …, nd, then

S_{2} = ∑_{i=1}^{n} d_{i}^{2} − nd^{2} = ∑_{j,k=1}^{nd} J_{jk} − nd^{2}

and thus

S_{2} − ES_{2} = ∑_{j,k=1}^{nd}(J_{jk} − EJ_{jk}) = 2 ∑_{j<k}(J_{jk} − EJ_{jk}).

It is now fairly straightforward to estimate the moments (or, simpler, cumulants) of S_{2} − ES_{2} and obtain (34). We omit the details. □

4.2 Further remarks

As stated above, Schmidt and Shamir [10] used the second moment method directly on G(n, m, s), thus proving the result when Y can be approximated (in L^{2}) by some non-random number c_{n} (depending on n and m), i.e. when Y/c_{n} → 1 in L^{2} for some c_{n} (say c_{n} = EY). The conditioning used above means that in this paper we treat the more general case when Y can be approximated by a function of the vertex degrees. The conditional expectation of Y given the vertex degees is given by (6), which shows that the appropriate approximating function is a constant times the product of the vertex degrees; the proof of Theorem 3 shows that we can write this as

c_{n} exp (∑ log d_{i}) ≈ c′_{n} exp (− ∑(d_{i} − d)^{2}/2d)

and thus we can as well approximate by a function of n and the sums of vertex degrees and squares of vertex degrees. In the case s = 2 (graphs) this is the same as taking a function of the numbers of vertices and edges and the number of paths of length two in the random graph, or equivalently, the numbers of trees of orders 1, 2 and 3 in the graph. This was suggested as a probable good approximation (for the number of perfect matchings as well as for some other related variables) in Janson [7]. The argument there was not rigorous, but was based on an orthogonal expansion which suggested that only these terms are important when d ≫ n^{1/3}, just as only the total number of edges is important when d ≫ n^{1/2}. The same argument suggests that a suitable approximation for d ≫ n^{1/4} can be found as an (exponential) function of the numbers of trees of orders up to 4 in the random graph. For hypergraphs the corresponding thing would be to take the numbers of pairs and triples of hyperedges that are connected in the edge graph. The same ought to apply for d ≫ n^{1/ℓ} for any fixed ℓ, (counting trees up to order ℓ), but we see no way of performing a variance calculation to justify this rigorously.

References

[1] E.A.Bender and E.R.Canfield, The asymptotic number of labelled graphs with given degree sequences, Journal of Combinatorial Theory, Series A, 24 (1978) 296-307.

[2] B.Bollobás, A probabilistic proof of an asymptotic formula for the number of labelled regular graphs, European Journal on Combinatorics, 1 (1980) 311-316.

[3] B.Bollobás and A.M.Frieze, On matchings and hamiltonian cycles in random graphs, Annals of Discrete Mathematics 28, (1985) 23-46.

[4] B.Bollobás, T.I.Fenner and A.M.Frieze, Hamilton cycles in random graphs with minimal degree at least k, in A tribute to Paul Erdős, edited by A.Baker, B.Bollobás and A.Hajnal,1990) 59 - 96.

[5] C.Cooper, A.M.Frieze, M.Molloy and B.Reed, Perfect matchings in random r-regular, s-uniform hypergraphs, Combinatorics, Probability and Computing, to appear.

[6] P.Erdös and A.Rényi, On the existence of a factor of degree one of a connected random graph, Acta Math. Acad. Sci. Hungar. 17 (1966) 359-368.

[7] S.Janson, The numbers of spanning trees, Hamilton cycles and perfect matchings in a random graph, Combinatorics, Probability and Computing, to appear.

[8] R.W.Robinson and N.C.Wormald, Almost all cubic graphs are Hamiltonian, Random Structures and Algorithms 3 (1992) 117-126.

[9] R.W.Robinson and N.C.Wormald, Almost all regular graphs are Hamiltonian, Random Structures and Algorithms to appear.

[10] J.Schmidt and E.Shamir, A threshold for perfect matchings in random d-pure hypergraphs, Discrete mathematics 45 (1983) 287-295.