Intersections of Randomly Embedded Sparse Graphs are Poisson

Edward A. Bender Department of Mathematics University of California, San Diego La Jolla, CA 92093-0112

                        ebender@math.ucsd.edu

E. Rodney Canfield Department of Computer Science The University of Georgia Athens, GA 30602, USA

                           erc@cs.uga.edu

Submitted: August 3, 1999; Accepted: September 26, 1999

Abstract

Suppose that t ≥ 2 is an integer, and randomly label t graphs with the integers 1 … n. We give sufficient conditions for the number of edges common to all t of the labelings to be asymptotically Poisson as n → ∞. We show by example that our theorem is, in a sense, best possible. For G_{n} a sequence of graphs of bounded degree, each having at most n vertices, Tomescu [7] has shown that the number of spanning trees of K_{n} having k edges in common with G_{n} is asymptotically e^{−2s/n}(2s/n)^{k}/k! × n^{n−2}, where s = s(n) is the number of edges in G_{n}. As an application of our Poisson-intersection theorem, we extend this result to the case in which maximum degree is only restricted to be O(n log log n/ log n). We give an inversion theorem for falling moments, which we use to prove our Poisson-intersection theorem.

AMS-MOS Subject Classification (1990): 05C30; Secondary: 05A16, 05C05, 60C05

1. Introduction and Statement of Graphical Results

This paper considers random embeddings of an m-vertex graph G into the complete graph K_{n} where m ≤ n. With no loss, assume the vertices of G are {1, 2, … m}. The number of injections of an m-set into an n-set is (n)_{m}, the falling factorial

(n)_{m} = n(n − 1) ⋯ (n − m + 1).

By a random embedding of G into K_{n}, we mean that one of the above injections is chosen from the uniform distribution.

Tomescu [7] showed that the number of edges a randomly embedded graph G_{n} has in common with a random spanning tree of K_{n} is asymptotically Poisson when the degree of the graph is bounded. (The result had been conjectured in [6], and proven there for a special case.) This can be interpreted in terms of random embeddings of pairs of graphs in K_{n}. Theorem 1, discusses random embeddings of t-tuples of graphs. In Theorem 2, we use this to extend Tomescu’s result from graphs of bounded degree to those whose degrees may grow as fast as O(n log log n/ log n).

Theorem 1. Let t ≥ 2 be an integer. Suppose that for each i, 1 ≤ i ≤ t, we have a sequence G_{n}(i), of graphs, each having at most n vertices and at least one edge. Let s_{n}(i) and Δ_{n}(i) be the number of edges and the maximum degree, respectively, for G_{n}(i). Let Y_{n} equal the number of edges common to t randomly chosen embeddings of the G_{n}(i) into K_{n}. Let

λ_{n} = \frac{∏_{i=1}^{t} s_{n}(i)}{\binom{n}{2}t−1}  (1)

and

ρ_{n} = ∏_{i=1}^{t} \frac{(Δ_{n}(i))^{2}}{s_{n}(i)} .  (2)

If min(λ_{n}, ρ_{n}) → 0, then

(Prob(Y_{n} = k) − e^{−λ_{n}} λ_{n}^{k} / k!) → 0  for each fixed k.  (3)

Theorem 2. Let G_{n} be a sequence of graphs, each having at most n vertices. Let s_{n} and Δ_{n} be the number of edges and the maximum degree, respectively, for G_{n}. Let T (G_{n}; n, k) be the number of spanning trees of K_{n} having k edges in common with G_{n}. If

Δ_{n} = O(n log log n/ log n),  (4)

then

(T (G_{n}; n, k)/n^{n−2} − e^{−2s_{n}/n} (2s_{n}/n)^{k} / k!) → 0  for each fixed k. (5)

To what extent are the constraints on the sequences Δ_{n} needed in Theorems 1 and 2? Some condition is needed in Theorem 2 since T (G_{n}; n, 0) = 0 for the nvertex star; however, we do not know if (4) is best possible. For Theorem 1 we have the following result.

Theorem 3. We cannot replace the condition min(λ_{n}, ρ_{n}) → 0 in Theorem 1 with min(λ_{n}, ρ_{n}) = O(1):

(a) If G_{n}(1) is an n-cycle and G_{n}(2) is an n-vertex star, then Prob(Y_{n} = 2) = 1.

(b) If G_{n}(1) and G_{n}(2) are both caterpillars with b = ⌊n^{1/2}⌋ nonleaf vertices, each of degree b, then

∑_{k=0}^{∞} lim_{n→∞} Prob(Y_{n} = k)z^{k} = e^{z−1} exp{(e^{z−1} − 1)}.

The two examples are extreme: in (a) the ratios Δ_{n}(i)^{2}/s_{n}(i) differ greatly; in (b) they are equal.

2. A Theorem on Convergence to Poisson

The proof of Theorem 1, in the next section, requires an inversion theorem for falling moments. Inverting estimates for moments into estimates for the underlying probability distribution is a classical technique. In [2] this is done when the moment generating function has positive radius of convergence. An inversion theorem more useful in some circumstances is stated in [3, p. 75]: If there is a λ such that for every k we have E((Y_{n})_{k}) → λ^{k}, then also we have Prob(Y_{n} = k) → e^{−λ}λ^{k}/k!. (Strictly, the theorem is stated in terms of factorial cumulants (see page 50), but is equivalent to what is stated here.) No proof or reference is given, but this assertion is a corollary of Theorem 4 below. Similar inversion theorems are found in [1, p. 491] and [5, p. 22], phrased in inclusion-exclusion terms. Of the above, only [1] does not require that E(Y_{n}) → λ. The following theorem is similar to that in [1], but differs sufficiently that it is inappropriate to refer to that paper for a proof.

Theorem 4. Let Y_{1}, Y_{2}, … be a sequence of nonnegative integer valued random variables, each of which has falling moments of all orders. Let λ_{n} be the expected value E(Y_{n}) of the random variable Y_{n}. For each ϵ > 0 define the sets A_{ϵ}, B_{ϵ} ⊆ {1, 2, …} by

\begin{aligned}A_{ϵ} & = \{n : λ_{n} > 1/ϵ\} \\ B_{ϵ} & = \{n : 1/ϵ > λ_{n} > ϵ\}. \end{aligned}

Suppose that for each real ϵ > 0 we have

E((Y_{n})_{2}) ∼ λ_{n}^{2} as n → ∞ through A_{ϵ},  (6)

and that for each real ϵ > 0 and integer k > 0 we have

E((Y_{n})_{k}) ∼ λ_{n}^{k} as n → ∞ through B_{ϵ}.  (7)

Then it follows that

(Prob(Y_{n} = k) − e^{−λ_{n}} λ_{n}^{k} / k!) → 0 for each k.

To prove this, we require Bonferroni’s inequalities:

Theorem 5. Let Y be a random variable taking on nonnegative integer values. Suppose E((Y)_{k}) exists for k ≤ K. Then, for 0 ≤ J ≤ K − k

∑_{j=0}^{J} \frac{(−1)^{j} E((Y)_{k+j})}{k! j!}  (8)

is an over-estimate of Prob(Y = k) when J is even and an under-estimate when J is odd. Furthermore, in absolute value the last term in the sum is a bound on the difference between the sum over 0 ≤ j < J and Prob(Y = k).

Proof of Theorem 5. The last sentence in the theorem follows immediately from the over- and under-estimate claim concerning (8). We now prove the overand under-estimate claim. Let y_{k}(N) = ∑_{n=k}^{N} Prob(Y = n) (n)_{k}. Note that E((Y)_{k}) = lim_{N→∞} y_{k}(N). We have

∑_{j=0}^{J} \frac{(−1)^{j}y_{k+j} (N)}{k! j!} = ∑_{j≤J} ∑_{n=k}^{N} \frac{(−1)^{j} Prob(Y = n) (n)_{k+j}}{k! j!}

= ∑_{n=k}^{N} \frac{Prob(Y = n) (n)_{k}}{k!} (∑_{j≤J} \frac{(−1)^{j}(n − k)_{j}}{j!} ).

The parenthesized sum is ∑_{j≤J} \binom{n−k}{j} = (−1)^{J} \binom{n−k−1}{J} when n > k, and it equals 1 when n = k. Letting N → ∞ proves the theorem.

Proof of Theorem 4. Let an integer k and an ϵ > 0 be given. We must exhibit N such that

n ≥ N ⇒ ( | Prob(Y_{n} = k) − e^{−λ_{n}}λ_{n}^{k}/k! | < ϵ ).  (9)

We separate the proof into three cases, and exhibit four constants N_{1}, N_{2}, N_{3}, and L such that each of the conditions

n ≥ N_{1} and λ_{n} < ϵ
n ≥ N_{2} and λ_{n} > L
n ≥ N_{3} and ϵ ≤ λ_{n} ≤ L

implies the desired conclusion appearing on the right side of (9).

When k ≥ 1 and λ > 0, we easily have

1 − λ ≤ e^{−λ} ≤ 1 and 0 ≤ e^{−λ}λ^{k}/k! ≤ λe^{−λ}(λ^{k−1}/(k − 1)!) < λ.

For any random variable Y taking non negative integer values, we have, for k ≥ 1,

0 ≤ Prob(Y = k) ≤ Prob(Y ≥ 1) ≤ E(Y),

whence also

1 − E(Y) ≤ Prob(Y = 0) ≤ 1.

Combining these with the previous estimates, we obtain the first part of our proof simply by taking N_{1} = 1.

For the second part of the proof, we employ Chebyshev’s inequality. Recall that k is fixed. Choose L so large that

L ≥ 2k, 1/L < ϵ/2,  and  λ > L ⇒ e^{−λ}λ^{k}/k! < ϵ.

Let σ_{n}^{2} be the variance of Y_{n}. Chebyshev’s inequality gives

Prob(Y_{n} = k) ≤ (\frac{σ_{n}}{λ_{n} − k} )^{2},

and the latter is no greater than 4(σ_{n}/λ_{n})^{2} since L ≥ 2k. However, by hypothesis, if n becomes infinite through values such that λ_{n} ≥ L, we have

σ_{n}^{2} = E((Y_{n})_{2}) + λ_{n} − λ_{n}^{2}
= (1 + O(1))λ_{n}^{2} + λ_{n} − λ_{n}^{2}
= λ_{n} + O(λ_{n}^{2}),

whence

(σ_{n}/λ_{n})^{2} = (λ_{n})^{−1} + O(1).

The first term on the right is less than ϵ/2 by our choice of L; hence, choosing N_{2} so large that the O(1) term is less than ϵ/2 for n ≥ N_{2} completes the second part of the proof.

For the third and final part of the proof, we use Theorem 5. Choose J sufficiently large that

\frac{(ϵ^{−1})^{k+J}}{k! J!} < ϵ/3 and J > L.

Note that

| ∑_{0≤j<J}(−1)^{j}λ^{j}/j! − e^{−λ} | ≤ λ^{J}/J!  (10)

since, for J > λ, the absolute values of the terms with j ≥ J are decreasing and so the error is at most the first neglected term. There are three errors, E_{1}, E_{2}, E_{3}, to bound:

\begin{aligned}Prob(Y_{n} = k) & = ∑_{0≤j<J} \frac{(−1)^{j}E((Y_{n})_{k+j})}{k! j!} + E_{1} \\ ∑_{0≤j<J} \frac{(−1)^{j}E((Y_{n})_{k+j})}{k! j!} & = ∑_{0≤j<J} \frac{(−1)^{j}λ_{n}^{j+k}}{k! j!} + E_{2} \\ ∑_{0≤j<J} \frac{(−1)^{j}λ_{n}^{j+k}}{k! j!} & = \frac{λ_{n}^{k}}{k!} e^{−λ_{n}} + E_{3}. \end{aligned}

• By Theorem 5, E_{1} is smaller than E((Y_{n})_{k+J})/k! J!, which by assumption is (1+ O(1))λ_{n}^{J+k}/k! J!. By choice of J the latter is less than ϵ/3 for n sufficiently large.

• E_{2} is bounded in absolute value by O(1) ∑_{0≤j<J} 1/k! j! < O(1)e/k!, the O(1) term being the maximum of the finitely many differences |((Y_{n})_{k+j}) − λ_{n}^{k+j}|. For n sufficiently large, O(1)e/k! is smaller than ϵ/3.

• Finally, by (10), E_{3} is smaller in absolute value than λ_{n}^{k+J}/k! J!, which as noted

already is less than ϵ/3 for n sufficiently large. This concludes the proof.

3. Proof of Theorem 1

Using Theorem 4, we now prove Theorem 1. At times we drop subscripts and superscripts and refer to a graph G ⊆ K_{n} with s edges and maximum degree Δ. Throughout the proof, we speak of the probability of various events, and evaluate the expected value of some random variables. The underlying probability space for all this is the set of all t-tuples of embeddings of the graphs G(i) into K_{n} with the uniform distribution.

If ω = ω_{1}, …, ω_{t} is such an embedding, then (Y_{n}(ω))_{k} is the number of ways to choose a sequence e of k distinct edges all of which lie in every embedding. Let χ(S) be 1 if the statement S is true and 0 otherwise. With a sum on ω running over all embeddings and a sum on e running over all k-tuples of distinct edges,

E((Y_{n})_{k}) = ∑_{ω} Prob(ω) ∑_{e} χ(e is in every ω)

= ∑_{e} ∑_{ω} ∏_{i=1}^{t}(Prob(ω_{i}) χ(e is in every ω))

= ∑_{e} f_{n}(e), where f_{n}(e) = ∏_{i=1}^{t} p_{n}(G_{n}(i) ⊃ e),  (11)

and p_{n}(G ⊃ e) is the probability that a random embedding of G in K_{n} contains e.

Partition the k-tuples of distinct edges in K_{n} into two classes, I and D, where I contains all k-tuples of independent edges and D contains all other k-tuples (the dependent sets). Thus ∑_{e} in (11) can be partitioned into sums over I and D.

Here is a way to compute p_{n}(G ⊃ e). Imagine G as a subgraph of K_{n}. Now choose edges of K_{n} to be relabeled as e, preserving whatever incidences are required among the ends of the e_{i} by the names of their vertices. The probability that these k chosen edges lie in G is p_{n}(G ⊃ e).

We now consider ∑_{e∈I} f_{n}(e), using the method in the previous paragraph to estimate p_{n}(G ⊃ e). The edges chosen to be e can be any independent set in K_{n}, of which there are (n)_{2k} if the edges are directed and so (n)_{2k}/2^{k} if the edges are not directed. Hence |I| = (n)_{2k}/2^{k} and

p_{n}(G ⊃ e) = \frac{2^{k}I(G, k)}{(n)_{2k}},  (12)

where I(G, k) is the number of k-long sequences of independent edges in G. Thus

∑_{e∈I} f_{n}(e) = (\frac{2^{k}}{(n)_{2k}} )^{t−1} ∑_{e∈I} ∏_{i=1}^{t} I(G_{n}(i), k).  (13)

When k = 1, we have D = ∅ and I(G_{n}(i), 1) = s_{n}(i). Thus, from (11) and (13),

E(Y_{n}) = \frac{1}{\binom{n}{2}} ∏_{i=1}^{t} \frac{s_{n}(i)}{\binom{n}{2}}.  (14)

This shows that the λ_{n} of Theorem 1 is E(Y_{n}). By the hypotheses of Theorem 4, we may restrict our attention to n with λ_{n} > ϵ, which we do from now on. By hypothesis min(ρ_{n}, λ_{n}) → 0, and so

ρ_{n} → 0 as n → ∞ through A_{ϵ} ∪ B_{ϵ}.  (15)

We detour briefly to prove a bound on the growth of the Δ’s that is needed later: For each i,

Δ_{n}(i)/s_{n}(i) → 0 as n → ∞ through A_{ϵ} ∪ B_{ϵ}.  (16)

For all i, nΔ_{n}(i) ≥ 2s_{n}(i) by a simple counting argument. Hence

\begin{aligned}\frac{ρ_{n}}{λ_{n}} & = \frac{∏_{i=1}^{t}(Δ_{n}(i)^{2}/s_{n}(i))}{\binom{n}{2} ∏_{i=1}^{t} (s_{n}(i)/\binom{n}{2})} \\ & ∼ (\frac{Δ_{n}(j)}{s_{n}(j)})^{2} ∏_{i≠j} \frac{(nΔ_{n}(i)/s_{n}(i))^{2}}{2} ≥ 2^{1−t} (\frac{Δ_{n}(j)}{s_{n}(j)})^{2} . \end{aligned}

By (15) and λ_{n} > ϵ, (16) follows.

We have

s^{k} ≥ I(G, k) ≥ s(s − Δ) ⋯ (s − (k − 1)Δ).

Since

\frac{s^{k}}{s(s − Δ) ⋯ (s − (k − 1)Δ)} < (\frac{s}{s − kΔ})^{k}

= (1 + \frac{kΔ}{s − kΔ})^{k} < exp (\frac{k^{2}Δ}{s − kΔ}) ,

it follows from (16) that I(G_{n}(i), k) ∼ s_{n}(i)^{k} for each fixed k. Hence f_{n}(e) ∼ (2λ/n^{2})^{k} when e ∈ I. Since |I| = (n)_{2k}/2^{k} ∼ n^{2k}/2^{k}, it follows from (11) and (12) that

∑_{e∈I} f_{n}(e) ∼ (n^{2k}/2^{k}) ∏_{i=1}^{t}(s_{n}(i)^{k}2^{k}/n^{2k}) ∼ λ_{n}^{k}.  (17)

We will show that

∑_{e∈D} f_{n}(e) = O(λ_{n}^{k}).  (18)

When (17) and (18) are combined with λ_{n} = E(Y_{n}), we obtain (7) with B_{ϵ} replaced by A_{ϵ} ∪B_{ϵ} and hence (6) follows as well. Thus, proving (18) will complete the proof of Theorem 1.

Suppose that the k edges in e form a graph H with v vertices and c components. Since e ∈ D,

c < v/2 < k.  (19)

Fix a spanning forest F of H. The edges of e are relabeled in the following order:

1. One edge in each tree in the spanning forest. The probability that each such edge lies in G, conditioned on edges already relabeled is bounded above by 2s/(n − 2k)^{2}.

2. Additional edges that grow each tree in the spanning forest in a connected fashion. The probability that each such edge lies in G, conditioned on edges already relabeled is bounded above by Δ/(n − 2k). To see this, note that one vertex on each such edge has already been embedded.

3. The remaining edges of e. Here we use the trivial bound of 1 for the conditional probability.

Since the number of edges in a spanning forest on v vertices and c components is v − c, there are v − 2c edges in Step 2 and so

p_{n}(G ⊃ e) ≤ (\frac{2s}{(n − 2k)^{2}} )^{c} (\frac{Δ}{n − 2k} )^{v−2c} .

Constructing possible e’s with the given values of k, v, and c in a similar manner, we see that there are at most

k! (n^{2}/2)^{c} n^{v−2c} = (2^{c} k!) n^{v}.

Hence the contribution of such e to the sum over D is at most

(2^{c} k!) n^{v} ∏_{i=1}^{t} (\frac{2s_{n}(i)}{(n − 2k)^{2}} )^{c} (\frac{Δ_{n}(i)}{n − 2k} )^{v−2c}

= O(1) n^{v} ∏_{i=1}^{t} (\frac{2s_{n}(i)}{n^{2}})^{c} (\frac{Δ_{n}(i)}{n})^{v−2c}

= O(1) \{n^{2} ∏_{i=1}^{t} \frac{s_{n}(i)}{n^{2}}\}^{v/2}(∏_{i=1}^{t} \frac{Δ_{n}(i)^{2}}{s_{n}(i)} )^{v/2−c}.

It follows from (15) and (19) that all e ∈ D with a given set of values for v and c contribute O(λ_{n}^{v/2}) to E((Y_{n})_{k}). Since the number of choices for v and c is bounded, λ_{n} > ϵ and v/2 < k by (19), we are done.

4. Proof of Theorem 2

Apply Theorem 1 with t = 2, G_{n}(1) = G_{n}, and G_{n}(2) = T_{n}, a spanning tree of K_{n}. In the next paragraph we show that, if k log log n/ log n → ∞, then almost all spanning trees of K_{n} have Δ < k. Thus ρ_{n} → 0 for almost all spanning trees T_{n} provided

\frac{Δ_{n}^{2}(log n/ log log n)^{2}}{ns_{n}} = o(1).

Averaging Theorem 1 over almost all T_{n}, eliminating those of high degree, proves Theorem 2.

The maximum degree bound follows from [4], but we include a simple proof here for completeness. Consider the Prüfer sequence for a tree. If the maximum degree is k, no number appears more than k times. An upper bound on sequences with at least t = k + 1 appearances of some number is obtained by choosing (i) a number from {1, …, n} to appear at least t times, (ii) t locations for it in the Prüfer sequence, and (iii) the remaining n − t − 2 sequence elements. Hence we have the upper bound

n\binom{n − 2}{t}n^{n−t−2} < n^{n−2}(n/t!) < n^{n−2}(n/k!).

Since there are n^{n−2} trees, the maximum degree is almost surely less than k if n/k! = O(1). The claim in the previous paragraph follows from Stirling’s formula.

5. Proof of Theorem 3.

For part (a), suppose that the star has been embedded in K_{n} and let v be the vertex that is connected to the other n − 1 vertices. When the n-cycle is embedded, one vertex will map to v. The two edges of the cycle that contain v as an end point also lie in the star and no other edges do.

Part (b) involves somewhat more calculation. Suppose the first caterpillar, G_{n}(1), has been embedded and let V = {v_{1}, …, v_{b}} be the vertices of degree b. There are two sources of common edges: First, when the second caterpillar has vertices of degree b in V. Second, when vertices of degree 1 in G_{n}(2) lie in V. In our computations, we will ignore some dependencies that become insignificant as n → ∞.

We consider the first case. The number of vertices in G_{n}(2) of degree b that lie in V is asymptotically Poisson and its expected value is

b × Prob(v_{1} has degree b in G_{n}(2)) = b × (b/n) ∼ 1.

If v_{k} has degree b in G_{n}(2), the number of common edges between G_{n}(1) and G_{n}(2) that share v_{k} is Poisson and its expected value is

∑_{v≠v_{k}} ∏_{i=1}^{2} p_{n}(G_{n}(i) ⊃ {v_{k}, v} | deg(v_{k}) = b) = (n − 1) × (b/(n − 1))^{2} ∼ 1.

Hence the generating function for the number of such vertices in common is the composition of two Poisson distributions of mean 1.

We now consider the second case. Since nearly all vertices have degree 1, the number of degree 1 vertices of G_{n}(2) that lie in V is asymptotic to |V| = b. For each such vertex v, the probability that its edge in G_{n}(2) is also in G_{n}(1) is asymptotic to b/n since v has degree b in G_{n}(1). Hence the number of such common edges is asymptotically Poisson with mean b × (b/n) ∼ 1.

Combining the results of the two previous paragraphs, we obtain Theorem 3(b).

References

1. E. A. Bender, Asymptotic methods in enumeration, Siam Review 16 (1974) 485–515.

2. J. H. Curtiss, A note on the theory of moment generating functions, Annals of Mathematical Statistics 13 (1942) 430–433.

3. F. N. David and D. E. Barton Combinatorial Chance, Griffin, London, 1962.

4. A. Meir and J. W. Moon, A note on trees with concentrated maximum degrees, Utilitas Mathematica 42 (1992) 61–64.

5. Joel Spencer, Ten Lectures on the Probabilistic Method, 2nd ed., SIAM, Philadelphia, 1994.

6. I. Tomescu, On the number of trees having k edges in common with a caterpillar of moderate degree, Ann. Discrete Math. 28 (1985) 305–310.

7. I. Tomescu, On the number of trees having k edges in common with a graph of bounded degrees, Discrete Math. 169 (1997) 283–286.