On the number of perfect matchings and Hamilton cycles in ϵ-regular non-bipartite graphs

Alan Frieze^{∗} Department of Mathematical Sciences Carnegie Mellon University Pittsburgh PA15213, USA

                      alan@random.math.cmu.edu

Submitted July 4, 2000, Accepted November 19, 2000

Abstract

A graph G = (V, E) on n vertices is super ϵ-regular if (i) all vertices have degree in the range [(d − ϵ)n, (d + ϵ)n], dn being the average degree, and (ii) for every pair of disjoint sets S, T ⊆ V, |S|, |T | ≥ ϵn, e(S, T) is in the range [(d − ϵ)|S||T |, (d + ϵ)|S||T |]. We show that the number of perfect matchings lies in the range [((d − 2ϵ)^{ν} \frac{n!}{ν!2^{ν}} , (d + 2ϵ)^{ν} \frac{n!}{ν!2^{ν}}], where ν = \frac{n}{2}, and the number of Hamilton cycles lies in the range [(d − 2ϵ)^{n}n!, (d + 2ϵ)^{n}n!].

1 Introduction

Let G = (V, E) be a graph with |V | = n. Let 0 < d < 1 and ϵ > 0 be constants (independent of n) where ϵ is assumed to be small compared with d. We assume that the density of G is d i.e. |E|/\binom{n}{2} = d. Suppose that the following two conditions hold:

• If d_{G} denotes vertex degree in G then

(d − ϵ)n ≤ d_{G}(v) ≤ (d + ϵ)n  for all v ∈ V.  (1)

Mathematics Subject Classification (1991); primary 05C50, 05C70, secondary 05C80

∗Supported in part by NSF Grant CCR9818411

• If for S, T ⊆ V, S ∩ T = ∅ we let e(S, T) denote the number of edges of G with one end in S and the other in T and d(S, T) = \frac{e(S,T)}{|S| |T |} then

|d(S, T) − d| ≤ ϵ for all S, T ⊆ V, S ∩ T = ∅, |S|, |T | ≥ ϵn.  (2)

A graph satisfying (1),(2) said to be super ϵ-regular. We assume that n = 2ν is even. Let m(G) denote the number of perfect matchings in G and let h(G) denote the number of Hamilton cycles in G. In this paper we prove

Theorem 1 If ϵ is sufficiently small and n is sufficiently large then

(a)

(d − 2ϵ)^{ν} \frac{n!}{ν!2^{ν}} ≤ m(G) ≤ (d + 2ϵ)^{ν} \frac{n!}{ν!2^{ν}} .

(b)

(d − 2ϵ)^{n}n! ≤ h(G) ≤ (d + 2ϵ)^{n}n!.

In both cases the bounds are “close” to the expected number of in the random graph G_{n,d}. The results here are strongly related to the result of Alon, Rödl and Ruciński [2]. They considered bipartite graphs H with vertex partition A, B where |A| = |B| = n. Assuming (1) and (2) for S ⊆ A and T ⊆ B they proved

Theorem 2 [2]

(d − 2ϵ)^{n}n! ≤ m(G) ≤ (d + 2ϵ)^{n}n!.

Michael Krivelevich has made some interesting observations on Theorem 1: First of all, part (b) of Theorem 1 improves Corollary 2.9 of Thomason [9] which estimates the number of Hamilton cycles in a pseudo-random graph. Secondly, if G is dn-regular and the second eigenvalue of the adjacency matrix of G is at most ηdn for small η, then G is super ϵ(η)-regular (see for example Chung [4] Theorem 5.1) and so our result holds for such graphs.

We note that a similar result can be proven for the number of spanning trees in such a graph: if t(G) denotes the number of spanning trees of G then

(d − 2ϵ)^{n−1}n^{n−2} ≤ t(G) ≤ (d + 2ϵ)^{n−1}n^{n−2}.  (3)

This follows from results of Alon [1] and Kostochka [7].

We prove Theorem 1(a) in the next section and Theorem 1(b) in Section 3. For completeness, we also give a proof of (3) in Section 4.

2 Perfect Matchings

Let A, B, |A| = |B| = ν be a partition of V. We re-express (2) in terms of ν i.e.

|d(S, T) − d| ≤ ϵ for all S ⊆ A, T ⊆ B, |S|, |T | ≥ 2ϵν.  (4)

Furthermore, if A, B is a random partition and H = H(A, B) is the bipartite sub-graph of G induced by A, B then with high probability d_{H}(v) ∈ [(d − ϵ − o(1))ν, (d + ϵ + o(1))ν] for all v ∈ V. Thus the conditions of Theorem 2 are satisfied with ν replacing n and 2ϵ replacing ϵ. It follows immediately that

m(H) ≥ (1 − o(1))\binom{n}{ν} × ν!(d − 2ϵ)^{ν} × \frac{1}{2^{ν}} = (1 − o(1))\frac{n!}{ν!2^{ν}} (d − 2ϵ)^{ν}.  (5)

The factor \frac{1}{2^{ν}} accounts for the fact that each perfect matching occurs in 2^{ν} different graphs H, assuming we consider the partition A, B distinct from B, A. There is slack in the calculation in [2] and this will absorb the 1 − o(1) term and so (5) proves the lower bound in Theorem 1.

For the upper bound we follow [2] and use the Minc conjecture [8] proved by Bregman [3]. For a partition A, B and v ∈ A let d_{B}(v) denote the number of G-neighbours of v in B. The Minc conjecture then states that

m(H) ≤ ∏_{v∈A}(d_{B}(v))!^{1/d_{B}(v)}.

Thus

m(G) ≤ \frac{1}{2^{ν}} ∑_{A,B} ∏_{v∈A}(d_{B}(v))!^{1/d_{B}(v)}.  (6)

For a fixed A, we let A_{1} = {v ∈ A : d_{B}(v) > (d + ϵ)ν}. Property (1) implies that |A_{1}| ≤ ϵn. Now since (x!)^{1/x} increases with x, we see, after using Stirling’s approximation and (1), that

∏_{v∈A}(d_{B}(v))!^{1/d_{B}(v)} ≤ (\frac{d + ϵ}{e}ν)^{|A\A_{1}|} (\frac{d + ϵ}{e}n)^{|A_{1}|} (1 + O (\frac{ln n}{n}))^{ν}

≤ (\frac{d + ϵ}{e}ν)^{ν} 2^{ϵn}n^{O(1)}.

Hence

m(G) ≤ \frac{1}{2^{ν}} \binom{n}{ν} (\frac{d + ϵ}{e}ν)^{ν} 2^{ϵn}n^{O(1)} ≤ (d + 2ϵ)^{ν} \frac{n!}{ν!2^{ν}}

completing the proof of part (a) of Theorem 1. □

3 Hamilton Cycles

A Hamilton cycle is the union of two perfect matchings and so h(G) ≤ \frac{1}{2}m(G)^{2} and the upper bound in part (b) of Theorem 1 follows from the upper bound in part (a).

The lower bound requires more work. For 1 ≤ k ≤ ⌊n/3⌋, let Φ_{k} be the set of all 2-factors in G containing exactly k cycles, and let Φ = ∪_{k}Φ_{k} be the set of all 2-factors. Let f_{k} = |Φ_{k}| so that f_{1} = h(G). If M is a perfect matching of G, let a_{M} denote the number of perfect matchings of G that are disjoint from M. Since deleting M only disturbs ϵ-regularity marginally, we see by part (a) that a_{M} ≥ (d − 2ϵ)^{ν} \frac{n!}{ν!2^{ν}}. Thus

A_{G} = ∑_{M∈G} a_{M} ≥ ((d − 2ϵ)^{ν} \frac{n!}{ν!2^{ν}} )^{2} ≥ (d − 2ϵ)^{n}n! × \frac{1}{3n^{1/2}} .  (7)

On the other hand, we have

A_{G} ≤ ∑_{k=1}^{⌊n/3⌋} 2^{k}f_{k}.  (8)

We will show by a relatively crude argument that where k_{1} = ⌈\frac{4}{(d−2ϵ)(d−ϵ)}⌉

\frac{f_{k+1}}{f_{k}} ≤ n^{3}  1 ≤ k ≤ k_{1}.  (9)

We then use an idea from Dyer, Frieze and Jerrum [5]. In this paper they show that if an n vertex graph G has minimum degree δ(G) ≥ (\frac{1}{2} + α)n for a positive constant α, then a polynomial fraction of the 2-factors of G are Hamilton cycles. We extend their argument to ϵ-regular graphs.

Let β = \frac{200}{(d−2ϵ)(d−ϵ)^{2}} . Let k_{0} = ⌊β ln n⌋, and for 1 ≤ k ≤ n, define γ(k) = n^{β}k!(β ln n)^{−k}, and

ϕ(k) = \begin{cases}γ(k), & if k ≤ k_{0}; \\ γ(k_{0}), & otherwise. \end{cases}

Lemma 1 Let ϕ be the function defined above. Then

1. ϕ is non-increasing and satisfies

min{ϕ(k − 1), ϕ(k − 2)} = ϕ(k − 1) ≥ (β ln n)k^{−1}ϕ(k);

2. ϕ(k) ≥ 1, for all k.

Proof Observe that γ is unimodal, and that k_{0} is the value of k minimizing γ(k); it follows that ϕ is non-increasing. When k ≤ k_{0}, we have ϕ(k − 1) = γ(k − 1) = (β ln n)k^{−1}γ(k) = (β ln n)k^{−1}ϕ(k); otherwise, ϕ(k−1) = γ(k_{0}) = ϕ(k) ≥ (β ln n)k^{−1}ϕ(k). In either case, the inequality in part 1 of the lemma holds.

Part 2 of the lemma follows from the chain of inequalities

\frac{1}{ϕ(k)} ≤ \frac{1}{γ(k_{0})} ≤ \frac{(β ln n)^{k_{0}}}{n^{β}k_{0}!} ≤ n^{−β} ∑_{k=0}^{∞} \frac{(β ln n)^{k}}{k!} = n^{−β} exp(β ln n) = 1.

□

Define

Ψ = {(F, F′) : F ∈ Φ_{k}, F′ ∈ Φ_{k′}, k′ < k, and F ⊕ F′ is a 6-cycle},

where ⊕ denotes symmetric difference. Observe that Γ = (Φ, Ψ) is an acyclic directed graph; let us agree to call its component parts nodes and arcs to avoid confusion with the vertices and edges of G. Observe also that if (F, F′) ∈ Ψ is an arc, then F′ can be obtained from F by deleting three edges and adding three others, and that this operation can decrease the number of cycles by at most two. Thus every arc (F, F′) ∈ Ψ is directed from a node F in some Φ_{k} to a node F′ in Φ_{k−1} or Φ_{k−2}.

Our proof strategy is to define a positive weight function w on the arc set Ψ such that the total weight of arcs leaving each node (2-factor) F ∈ Φ_{≥k_{1}} is significantly greater than the total weight of arcs entering F. We will show below that

∑_{F^{+}:(F,F^{+})∈Ψ} w(F, F^{+}) ≥ 100ϕ(k)n^{2} ln n  F ∈ Φ_{k}, k ≥ k_{1},  (10)
∑_{F^{−}:(F^{−},F)∈Ψ} w(F^{−}, F) ≤ 9ϕ(k)n^{2}H_{n}  F ∈ Φ_{k}, k ≥ 1,  (11)

where H_{n} = ∑_{i=1}^{n} i^{−1} ≤ ln n + 1 is the nth harmonic number.

Now let

W_{k,l} = ∑_{{F ∈Φ_{k},F′∈Φ_{l} \atop (F,F′)∈Ψ}} w(F, F′).

Then (10) and (11) imply that for k ≥ k_{1},

W_{k+2,k} + W_{k+1,k} ≤ 9f_{k}ϕ(k)n^{2}H_{n}  (12)
W_{k,k−1} + W_{k,k−2} ≥ 100f_{k}ϕ(k)n^{2} ln n.  (13)

Now (13) implies that either (i) W_{k,k−1} ≥ 50f_{k}ϕ(k)n^{2} ln n so that from (12)(k-1) we have

\frac{f_{k−1}}{f_{k}} ≥ 5\frac{ϕ(k)}{ϕ(k − 1)}

or (ii) W_{k,k−2} ≥ 50f_{k}ϕ(k)n^{2} ln n so that from (12)(k-2) we have

\frac{f_{k−2}}{f_{k}} ≥ 5\frac{ϕ(k)}{ϕ(k − 2)}

It follows that if k ≥ k_{0} + 2 then

f_{k} ≤ 5^{−(k−k_{0})/2} max{f_{k_{0}+1}, f_{k_{0}}}.

Then from (8) we see that

A_{G} ≤ \frac{\sqrt{5}}{\sqrt{5} − 2} ∑_{k=1}^{k_{0}+1} 2^{k}f_{k} ≤ \frac{\sqrt{5}}{\sqrt{5} − 2}2^{k_{0}+1} ∑_{k=1}^{k_{0}+1} f_{k}.  (14)

Furthermore, since F ∈ Φ_{k}, k > k_{1} implies that

∑_{F^{+}:(F,F^{+})∈Ψ} w(F, F^{+}) − ∑_{F^{−}:(F^{−},F)∈Ψ} w(F^{−}, F) ≥ 1

the total weight of arcs entering Φ_{k_{1}} is an upper bound on the number of 2-factors in G with more than k_{1} cycles and the maximum total weight of arcs entering a single node in Φ_{k_{1}} is an upper bound on the ratio ρ = \frac{f_{k_{1}+1}+f_{k_{1}+2}+···+f_{⌊n/3⌋}}{f_{k_{1}}} . Thus

ρ ≤ 9ϕ(1)n^{2}H_{n} = O(n^{2+β}).

Combined with (14) and (9) we see that

A_{G} ≤ n^{O(1)}f_{1}  (15)

and the lower bound in Theorem 1(b) follows from (7), modulo taking advantage of slack to absorb the n^{O(1)} term.

3.1 Proofs of (10) and (11)

The weight function w : Ψ → R^{+} we employ is defined as follows. For any arc (F′, F) with F ∈ Φ_{k}: if the 2-factor F is obtained from F′ by coalescing two cycles of lengths l_{1} and l_{2} into a single cycle of length l_{1} + l_{2}, then w(F′, F) = (l_{1}^{−1} + l_{2}^{−1})ϕ(k); if F results from coalescing three cycles of length l_{1}, l_{2} and l_{3} into a single one of length l_{1} + l_{2} + l_{3}, then w(F′, F) = (l_{1}^{−1} + l_{2}^{−1} + l_{3}^{−1})ϕ(k).

Let F ∈ Φ_{k} be a 2-factor with k > 1 cycles C_{1}, C_{2}, …, C_{k}, of lengths n_{1}, n_{2}, …, n_{k}. We proceed to bound from below the total weight of arcs leaving F. For this purpose imagine that the cycles C_{1}, C_{2}, …, C_{k} are oriented in some way, so that we can speak of each oriented edge (u, u′) in some cycle C_{i} as being “forward” or “backward”. For each vertex a we can then let (a, π(a)) be the unique forward edge containing a. Since we are interested in obtaining a lower bound, it is enough to consider only arcs (F, F^{+}) from F of a certain kind: namely, those for which the 6-cycle C = F ⊕ F^{+} is of the form C = (x, x′, y, y′, z, z′), where (x, x′) ∈ F is a forward cycle edge, (y, y′) ∈ F is a forward edge in a cycle distinct from the first, and (z, z′) ∈ F is a backward cycle edge. The edge (z, z′) may be in the same cycle as either (x, x′) or (y, y′), or in a third cycle. Observe that (x′, y), (y′, z) and (z′, x) must necessarily be edges of F^{+}. It is routine to check that any cycle C = (x, x′, y, y′, z, z′) satisfying the above constraints does correspond to a valid arc from F. The fact that (z, z′) is oriented in the opposite sense to (x, x′) and (y, y′) plays a crucial role in ensuring that the number of cycles decreases in the passage to F^{+} when only two cycles are involved.

First, we estimate the number of cycles C for which a fixed (x, x′) is contained in a particular cycle C_{i} of F. We say that C is rooted at C_{i}. Let Z′ be the neighbour set of x in G and Z = π(Z′). Similarly, let Y′ be the set of neighbours of x′ which do not belong to C_{i} and let Y = π(Y′). If |Y′| ≥ ϵn then by ϵ-regularity there are at least (d − 2ϵ)n vertices z ∈ Z which have at least (d − ϵ)|Y′| ≥ (d − ϵ)((d − ϵ)n − n_{i}) neighbours y′ in Y′. Let δ_{i} = 1_{n_{i}≤(d−2ϵ)n}. We see that δ_{i} = 1 implies (x, x′) is contained in at least (d − 2ϵ)(d − ϵ)((d − ϵ)n − n_{i})n cycles. Note also that ∑_{i=1}^{k} δ_{i} ≥ k − \frac{1}{d−2ϵ}.

We can now bound the total weight of arcs leaving F. Each arc (F, F^{+}) defined by a cycle C rooted at C_{i} has weight at least n_{i}^{−1} min{ϕ(k − 1), ϕ(k − 2)}, which, by Lemma 1, is bounded below by (β ln n)(kn_{i})^{−1}ϕ(k). Thus the total weight of arcs leaving F is bounded as follows:

∑_{F^{+}:(F,F^{+})∈Ψ} w(F, F^{+}) ≥ ∑_{i=1}^{k}(d − 2ϵ)(d − ϵ)((d − ϵ)n − n_{i})nδ_{i}n_{i} \frac{(β ln n)ϕ(k)}{kn_{i}} (16)

≥ β(d − 2ϵ)(d − ϵ)ϕ(k) (d − ϵ − \frac{1}{k(d − 2ϵ)} − \frac{1}{k}) n^{2} ln n(17)
≥ β(d − 2ϵ)(d − ϵ)ϕ(k)\frac{d − ϵ}{2}n^{2} ln n,
≥ 100ϕ(k)n^{2} ln n  (18)

where we have used the fact that k ≥ k_{1}. Note that the presence of a unique backward edge, namely (z, z′), ensures that each cycle C has a distinguishable root, and hence that the arcs (F, F^{+}) were not overcounted in summation (16). This completes the proof of (10).

We now turn to the corresponding upper bound on the total weight of arcs (F^{−}, F) ∈ Ψ entering F. It is straightforward to verify that the cycle C = (x, x′, y, y′, z, z′) = F^{−} ⊕ F must contain three edges — (x, x′), (y, y′) and (z, z′) — from a single cycle C_{i} of F, the remaining edges coming from F^{−}. The labeling of vertices in C can be made canonical in the following way: assume an ordering on vertices in V, and assign label x to the smallest vertex. The condition (x, x′) ∈ F uniquely identifies vertex x′, and the labeling of the other vertices in the cycle C follows.

Removing the three edges (x, x′), (y, y′) and (z, z′) from C_{i} leaves a triple of simple paths of lengths (say) a − 1, b − 1 and c − 1: these lengths correspond (respectively) to the segment containing x, the segment containing x′, and the remaining segment. Going round the cycle C_{i}, starting at x′ and ending at x, the vertices x, x′, y, y′, z, z′ may appear in one of eight possible sequences:

x′, y′, y, z′, z, x;

x′, z, z′, y, y′, x;
x′, z, z′, y′, y, x;
x′, z′, z, y, y′, x;
x′, y′, y, z, z′, x;
x′, y, y′, z′, z, x;
x′, z′, z, y′, y, x;
x′, y, y′, z, z′, x.

For a given triple of lengths (a, b, c), each of the above sequences corresponds to at most n_{i} possible choices for the edges (x, x′), (y, y′) and (z, z′), yielding a maximum of 8n_{i} in total. To see this, observe that the edge (x, x′) may be chosen in n_{i} ways (minimality of x fixes the orientation of the edge), and that the choice of (x, x′) combined with the information provided by the sequence completely determines the triple of edges.

The eight sequences divide into five possible cases, as the first four sequences lead to equivalent outcomes (covered by case 1 below). Taken in order, the five cases are:

1. For at most 4n_{i} of the choices for the edges (x, x′), (y, y′) and (z, z′), C_{i} ⊕ C is a single cycle;

2. for at most n_{i} choices, C_{i} ⊕ C is a pair of cycles of lengths b and a + c;

3. for at most n_{i} choices, C_{i} ⊕ C is a pair of cycles of lengths a and b + c;

4. for at most n_{i} choices, C_{i} ⊕ C is a pair of cycles of lengths c and a + b;

5. for at most n_{i} choices, C_{i} ⊕ C is a triple of cycles of lengths a, b and c.

The first case does not yield an arc (F^{−}, F), since the number of cycles does not decrease when passing from F^{−} = F ⊕ C to F, but the other four cases do have to be reckoned with.

The total weight of arcs entering F can be bounded above as follows:

∑_{F^{−}:(F^{−},F)∈Ψ} w(F^{−}, F) ≤ ∑_{i=1}^{k} n_{i}ϕ(k) ∑_{{a,b,c≥1 \atop a+b+c=n_{i}}} [(\frac{1}{a} + \frac{1}{b} + \frac{1}{c}) +

(\frac{1}{a} + \frac{1}{b + c}) + (\frac{1}{b} + \frac{1}{a + c}) + (\frac{1}{c} + \frac{1}{a + b})]

= ∑_{i=1}^{k} n_{i}ϕ(k) ∑_{{a,b,c≥1 \atop a+b+c=n_{i}}} [\frac{6}{a} + \frac{3}{b + c}]

≤ ∑_{i=1}^{k} n_{i}ϕ(k)n ∑_{a=1}^{n_{i}−1} [\frac{6}{a} + \frac{3}{n_{i} − a}]
≤ 9ϕ(k)n^{2}H_{n}.

This completes the proof of (11).

3.2 Proof of (9)

We show that if F ∈ Φ_{k} and 2 ≤ k ≤ k_{1} then there is at least one arc (F, F′) ∈ Ψ. Since each F′ is the terminus of at most n^{3} arcs, (9) follows immediately.

Let C_{1} be the largest cycle of F. Then |C_{1}| ≥ n/k_{1} ≥ \frac{d^{2}}{5} n.

Case 1: |C_{1}| ≤ n − 3ϵn.

ϵ-regularity implies that there are at most ϵn vertices X which have fewer than (d−ϵ)|C_{1}| neighbours in C_{1}. As there are at least 3ϵn vertices not in C_{1}, there are vertices x_{1}, x_{2} ∉ X which are neighbours on a cycle C_{2} ≠ C_{1}. Let A_{i}, i = 1, 2 be the neighbour sets of x_{i} on C_{1} and let B_{i} = π(A_{i}) for i = 1, 2. By assumption, |B_{i}| ≥ \frac{1}{5}d^{2}(d − ϵ)n for i = 1, 2 and so we can choose B′_{i} ⊆ B_{i}, i = 1, 2 such that B′_{1} ∩ B′_{2} = ∅ and |B′_{1}| = |B′_{2}| ≥ \frac{1}{6}d(d − ϵ)n. ϵ-regularity implies that there is at least one edge joining B′_{1}, B′_{2}. Suppose this is the edge (b_{1}, b_{2}). Then x_{1}, π^{−1}(b_{1}), b_{1}, b_{2}, π^{−1}(b_{2}), x_{2}, x_{1} defines the requisite 6-cycle.

Case 2: |C_{1}| > n − 3ϵn.

Just take any two vertices which are neighbours on a cycle other than C_{1}. Each has at least (d − 4ϵ)n neighbours in C_{1} and we can argue the existence of a 6-cycle as in the previous case. □

Remark: The proof shows that the number of Hamilton cycles is within a polynomial factor of the number of two factors of G. Therefore one can generate a (near) random Hamilton cycle of G by generating (near) random 2-factors of G until a Hamilton cycle is produced. By doing this sufficiently many times we expect to obtain a good approximation to the ratio of Hamilton cycles to 2-factors. Since the number of 2-factors of G can be efficiently approximated to within arbitrary accuracy (Jerrum, Sinclair and Vigoda [6]) we see that we can efficiently estimate the number of Hamilton cycles of G to within arbitrary accuracy. Formally, there is a Fully Polynomial Time Randomised Approximation Scheme for estimating the number of Hamilton cycles in an super ϵ-regular graph. It is of course assume that d > 0 is constant and ϵ < d. This same argument is used in [5].

4 Spanning Trees

For the lower bound let Ω = {f : V → V : (v, f(v)) ∈ E, for all v ∈ V } be the set of functions defined by each v ∈ V choosing a neighbour f(v). Clearly

|Ω| = ∏_{v∈V} d_{G}(v) ≥ (d − ϵ)^{n}n^{n}.  (19)

Each f ∈ Ω defines a digraph D_{f} = (V, A_{f}), A_{f} = {(v, f(v) : v ∈ V }. A weak component of D_{f} consists of a cycle C with a rooted forest whose roots are in C. Suppose that D_{f} has k_{f} weak components. We obtain a spanning tree of G by (i) deleting the lexicographically first edge of each cycle of D_{f} and then (ignoring orientation) extending the k_{f} components to a spanning tree. We claim that if α = 4/\sqrt{d − ϵ} and

Ω_{1} = \{f ∈ Ω : k_{f} ≤ α\sqrt{n}\}

then

|Ω_{1}| ≥ |Ω|/2.  (20)

Assume that (20) holds. Each spanning tree is obtained by deleting k_{f} edges of a D_{f} and then adding k_{f} − 1 edges. It follows that each spanning tree can be obtained in at most \binom{N}{α\sqrt{n}}^{2}, N = \binom{n}{2} ways from a member of Ω_{1}. Thus

t(G) ≥ \frac{1}{2}n^{−4α\sqrt{n}}(d − ϵ)^{n}n^{n}

and the lower bound in (3) follows. Proof of (20) Let f be chosen randomly from Ω and write

k_{f} = ∑_{v∈V} \frac{1}{|K_{v}|}

where K_{v} is the weak component containing v. We will argue that

Pr(|K_{v}| ≤ k) ≤ \frac{k^{2}}{(d − ϵ)n}  k ≥ 1.  (21)

Given (21) we have

E(|K_{v}|^{−1}) ≤ ∑_{k=1}^{\sqrt{(d−ϵ)n}} \frac{1}{k}(Pr(|K_{v}| ≤ k) − Pr(|K_{v}| ≤ k − 1)) + \frac{1}{\sqrt{(d − ϵ)n}}

≤ ∑_{k=1}^{\sqrt{(d−ϵ)n}} \frac{Pr(|K_{v}| ≤ k)}{k(k + 1)} + \frac{1}{\sqrt{(d − ϵ)n}}

≤ ∑_{k=1}^{\sqrt{(d−ϵ)n}} \frac{1}{(d − ϵ)n} + \frac{1}{\sqrt{(d − ϵ)n}}
= \frac{2}{\sqrt{(d − ϵ)n}}

Thus

E(k_{f}) ≤ \frac{2\sqrt{n}}{\sqrt{d − ϵ}}

and (20) follows from the Markov inequality. To verify (21), start with v and follow v, f(v), f^{2}(v), …, until there is a repetition in the sequence. The probability of a repetition at the ith step is at most \frac{i}{(d−ϵ)n}, since there are always at least (d − ϵ)n random choices for f^{i}(v). If there are no repetitions by step k then |K_{v}| > k. Thus

Pr(|K_{v}| ≤ k) ≤ ∑_{i=1}^{k} \frac{i}{(d − ϵ)n}

and (21) follows. □ For the upper bound in (3) let Ω^{∗} = {f : V → V : (v, f(v)) ∈ E or f(v) = v for all v ∈ V }. Then

t(G) ≤ |Ω^{∗}| ≤ ((d + ϵ)n + 1)^{n} ≤ (d + 2ϵ)^{n−1}n^{n−2}.

To see this consider the following injective map from the spanning trees of G into Ω^{∗}: orient each edge of tree T towards vertex 1 and then put f(1) = 1. Acknowledgement We thank Michael Krivelevich for his earlier comments and for pointing out the simple proof of the upper bound in (3).

References

[1] N. Alon, The number of spanning trees in regular graphs, Random Structures and Algorithms 1 (1990) 175–182.

[2] N. Alon, V. Rödl and A. Ruciński, Perfect matchings in ϵ-regular graphs, The Electronic Journal of Combinatorics 5 (1998) #R13.

[3] L. M. Bregman, Some properties of non-negative matrices and their permanents, Soviet Mathematics Doklady 14 (1973) 945–949.

[4] F. R. K. Chung, Spectral Graph Theory, CBMS monograph no. 92, American Mathematical Society 1997.

[5] M. E. Dyer, A. M. Frieze and M. R. Jerrum, Approximately counting Hamilton cycles in dense graphs, SIAM Journal on Computing 27 (1998) 1262–1272.

[6] M. R. Jerrum, A. Sinclair and E. Vigoda, A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries, to appear.

[7] A. V. Kostochka, The number of spanning trees in graphs with given degree sequences, Random Structures and Algorithms 6 (1995) 269–274.

[8] H. Minc, Non-negative matrices, Wiley, 1988.

[9] A. Thomason, Pseudo-random graphs, Proceedings of Random Graphs 85, Annals of Discrete Mathematics 33, M. Karonski, Z. Palka, eds., North Holland (1985) 307–331.