HAMILTON CYCLES IN A RANDOM TOURNAMENT

Svante Janson

Abstract. The number of Hamilton cycles in a random tournament is asymptotically normally distributed.

1. Introduction

A tournament on n vertices is a directed graph obtained by orienting each edge of the complete undirected graph K_{n} in one of the two possible directions. We will here consider the random tournament T_{n} obtained by choosing uniformly among all tournaments, or equivalently, by orienting the edges independently with probability 1/2 for each direction. For a background see [7], where also further references are given. (Other models of random tournaments, where the directions are assigned with unequal probabilities, have been considered by several authors, see e.g. [2], [9], [3], [6], but we will here only consider the simplest and most symmetric case.)

We will study the number of Hamilton cycles in T_{n} and our main result is the following. (We assume throughout n ≥ 3.)

Theorem 1. Let H_{n} be the number of directed Hamilton cycles in the random tournament T_{n}. Then

E H_{n} = (n − 1)! 2^{−n},  (1.1)
Var H_{n} = (\frac{2}{n} + O(\frac{1}{n^{2}} ))(E H_{n})^{2}  (1.2)

and H_{n} is asymptotically normally distributed:

\frac{H_{n} − E H_{n}}{(Var H_{n})^{1/2}} ⟶^{d} N(0, 1)  as n → ∞.  (1.3)

Using (1.1) and (1.2), we can rewrite (1.3) as

\sqrt{\frac{n}{2}}(H_{n}/((n − 1)! 2^{−n}) − 1) ⟶^{d} N(0, 1).  (1.4)

Remark. This result differs markedly from the corresponding results in [4] for the random undirected graph G_{n,p} and the random directed graph D_{n,p}, with p = 1/2 (or any other fixed value); in those cases the number of Hamilton cycles is asymptotically log-normal. In contrast, the result for G_{n,m}, with for example m = \frac{1}{2} \binom{n}{2}, is very similar; furthermore, the projection method used below is very similar to the one used for G_{n,m} in [4].

Acknowledgment. This research was mainly done during the conference Random Graphs ’93 in Poznań, where this problem was put to me by Noga Alon. I thank him and Andrzej Ruciński for stimulating discussions.

Typeset by AMS-TEX

Supported by the Göran Gustafsson Foundation for Research in Natural Sciences and Medicine

2. A projection method.

We will prove Theorem 1 by a method similar to the well-known ‘method of first projection’ for G_{n,p}, where one approximates the random variable of interest with a linear function on the number of edges in the random graph. For random tournaments (as for G_{n,m}), however, the number of edges is constant and we instead resort to the ‘second projection’, using the numbers of different types of subgraphs on three vertices. We begin by studying the numbers of such subgraphs; for completeness we do it in somewhat more detail than necessary for just the proof of Theorem 1.

There are \frac{1}{2}(n)_{3} paths of length 2 in K_{n}. Each of them becomes in a tournament either a vertex with a pair of outgoing edges, a directed path, or a vertex with a pair of incoming edges. Let N_{0}, N_{1} and N_{2} be the numbers of times these possibilities happen in a given tournament on n vertices; thus N_{0}+N_{1}+N_{2} = \frac{1}{2}(n)_{3}. Letting d_{ik} and d_{0k} be the in-degree and out-degree of vertex k, we have N_{0} = ∑_{k} \binom{d_{0k}}{2}, N_{1} = ∑_{k} d_{0k}d_{ik} and N_{2} = ∑_{k} \binom{d_{ik}}{2}. Hence

2N_{0} + N_{1} = ∑_{k} d_{0k}(d_{0k} − 1 + d_{ik}) = ∑_{k} d_{0k}(n − 2) = \binom{n}{2}(n − 2) = \frac{1}{2}(n)_{3}

since d_{ik} + d_{0k} = n − 1 for each k and ∑ d_{0k} is just the total number of edges. Similarly, also 2N_{2} + N_{1} = \frac{1}{2}(n)_{3}, and thus N_{0} = N_{2}.

Another way to see this is to let N_{3} be the number of directed cycles of length 3 in the tournament. Since any subset of three vertices in the tournament induces a subgraph of order three which is either a directed cycle or a triangle where the vertices have outdegrees 0,1 and 2, it follows that

N_{0} = N_{2} = \binom{n}{3} − N_{3}  and  N_{1} = 3N_{3} + \binom{n}{3} − N_{3} = \binom{n}{3} + 2N_{3}.

Hence any of the variables N_{0}, N_{1}, N_{2}, N_{3} is a linear function of any of the others, and it suffices to consider one of them. We will actually find it convenient to use a fifth variable, viz. the linear combination S = N_{1} − N_{0} − N_{2} = 4N_{3} − \binom{n}{3} . (The formulae above yield N_{0} = N_{2} = \frac{1}{8}(n)_{3} − \frac{1}{4}S, N_{1} = \frac{1}{4}(n)_{3} + \frac{1}{2}S and N_{3} = \frac{1}{24}(n)_{3} + \frac{1}{4}S.)

Considering a random tournament again, these functionals become random variables. We may write S = ∑ J(P), summing over all paths P of length 2 in K_{n}, where

J(P) = \{ \begin{matrix}+1 & if P becomes a directed path in the tournament \\ −1 & otherwise. \end{matrix}

The random variables J(P) have mean 0 and are pairwise independent; hence E S = 0 and E S^{2} = ∑_{P} E J(P)^{2} = \frac{1}{2}(n)_{3}. Furthermore, as n → ∞, S is asymptotically normal. This was proved already by Moran [8] (for the cycle count N_{3}, which is equivalent by the formulae above); it also follows directly from e.g. Janson and Nowicki [5, Theorem 4] or, after a simple fourth moment calculation, De Jong [1, Theorem 1], see also [3] and [10].

We collect these results as a lemma.

Lemma 1. E S = 0, Var S = \frac{1}{2}(n)_{3} and

\frac{S − E S}{(Var S)^{1/2}} ⟶^{d} N(0, 1)  as n → ∞.  □

We state the projection method result in the following form.

Theorem 2. Suppose that X is any functional of the random tournament T_{n} such that

\frac{(E XS)^{2}}{Var X Var S} → 1 as n → ∞

(or, equivalently, (E XS)^{2} ∼ \frac{1}{2}n^{3} Var X). Then

\frac{X − E X}{(Var X)^{1/2}} ⟶^{d} N(0, 1) as n → ∞.

Proof. Let σ_{X}^{2} = Var X, σ_{S}^{2} = Var S and τ = sign(E XS). Then

E(\frac{X − E X}{σ_{X}} − τ \frac{S}{σ_{S}} )^{2} = \frac{Var X}{σ_{X}^{2}} − 2τ \frac{E XS}{σ_{X}σ_{S}} + \frac{Var S}{σ_{S}^{2}} = 2 − 2\frac{| E XS|}{σ_{X}σ_{S}} → 0

and thus (X − E X)/σ_{X} − τS/σ_{S} ⟶^{p} 0 as n → ∞. Since S/σ_{S} ⟶^{d} N(0, 1) by Lemma 1, τ is non-random with τ = ±1 and the normal distribution is symmetric, we have τS/σ_{S} ⟶^{d} N(0, 1) and the result follows by Cramr’s theorem. □

Remark. The careful reader may observe that although we called this a projection method, we did not use the actual orthogonal projection \frac{E XS}{σ_{S}^{2}} S of X; this is only a matter of convenience in the proof.

Remark. Most other small subgraph counts for random tournaments are easily shown to be asymptotically normal using this projection result, but there are some exceptions. This is entirely similar to the situation for G_{n,p} and G_{n,m}, but the exceptional graphs differ in the three cases. We hope to return to this in another paper.

3. Proof of Theorem 1.

We will use Theorem 2, and must therefore compute (at least approximately) E H_{n}S and Var H_{n}. It will be convenient to regard directed graphs as sets of directed edges, in our case subsets of the edge set of the complete directed graph D_{n} (we will not consider any graphs with isolated vertices, so this is unambiguous). Hence, for example, |A ∩ B| denotes the number of common edges in A and B. If A is any directed graph, we let \overline{A} denote the graph obtained by reversing the orientation of each edge, and let A^{0} be the corresponding undirected graph.

Let C be the set of the (n − 1)! directed Hamilton cycles in D_{n}. Then

E H_{n} = E ∑_{C∈C} I(C ⊂ T_{n}) = ∑_{C∈C} P(C ⊂ T_{n}) = (n − 1)! 2^{−n},  (3.1)

which verifies (1.1).

Lemma 2. E H_{n}S = n E H_{n}.

Proof. Let P be the set of all paths of length 2 in K_{n}. Then

E(H_{n}S) = E ∑_{C∈C} ∑_{P ∈P} I(C ⊂ T_{n})J(P)
= E ∑_{C∈C} P(C ⊂ T_{n}) ∑_{P ∈P} E(J(P) | C ⊂ T_{n}).  (3.2)

For any fixed C ∈ C, E(J(P) | C ⊂ T_{n}) = 0 for every P that contains at least one edge not in C^{0}; there remain n choices of P with P ⊂ C^{0}, and for them C ⊂ T_{n} implies J(P) = 1. Hence the final inner sum above equals n, and

E(H_{n}S) = n ∑_{C∈C} P(C ⊂ T_{n}) = n E H_{n}.  □

We next give an exact expression for Var(H_{n}).

Lemma 3.

\frac{Var H_{n}}{(E H_{n})^{2}} = \frac{E H_{n}^{2}}{(E H_{n})^{2}} − 1

= \frac{1 + (−1)^{n}}{(n − 1)!} + ∑_{k=1}^{⌊(n−1)/2⌋} ∑_{j=1}^{k∧(n−2k)} \frac{n(n − 2k − 1)!^{2}(k − 1)! 2^{j}}{(n − 1)! (n − 2k − j)! (k − j)! j! (j − 1)!}.

Proof.

E H_{n}^{2} = ∑_{C,D∈C} P(C, D ⊂ T_{n}) = ∑_{C∈C} P(C ⊂ T_{n}) ∑_{D∈C} P(D ⊂ T_{n} | C ⊂ T_{n}).  (3.3)

By symmetry, the inner sum is the same for every C ∈ C. Moreover, P(D ⊂ T_{n} | C ⊂ T_{n}) = 0 if C ∩ \overline{D} ≠ ∅, and otherwise P(D ⊂ T_{n} | C ⊂ T_{n}) = 2^{−|D\C|} = 2^{|C∩D|} P(D ⊂ T_{n}). Hence, for any fixed C ∈ C, using a type of inclusion–exclusion argument,

(n − 1)! \frac{E H_{n}^{2}}{(E H_{n})^{2}} = 2^{n} ∑_{D∈C} P(D ⊂ T_{n} | C ⊂ T_{n})

= ∑_{D∈C} \frac{P(D ⊂ T_{n} | C ⊂ T_{n})}{P(D ⊂ T_{n})} = ∑_{D∈C} 2^{|C∩D|} 0^{|C∩\overline{D}|}

= ∑_{D∈C}(1 + 1)^{|C∩D|}(1 − 1)^{|C∩\overline{D}|} = ∑_{D∈C} ∑_{A⊂C∩D} ∑_{B⊂C∩\overline{D}}(−1)^{|B|}

= ∑_{A,B⊂C} ∑_{D∈C:D⊃A,\overline{D}⊃B}(−1)^{|B|}

= ∑_{A,B⊂C}(−1)^{|B|}|\{D ∈ C : D ⊃ A ∪ \overline{B}\}|.  (3.4)

If A and B are subgraphs of C with a common edge or just a common vertex, then there are no directed Hamilton cycles D ⊃ A ∪ \overline{B}. Hence, if we collect all terms in the last sum with a given A ∪ B, then we only have to consider A (and B) which are unions of some weak components of A ∪ B. If A ∪ B = C, this gives the two cases A = C, B = ∅ and A = ∅, B = C, with a single Hamilton cycle D ⊃ A ∪ \overline{B} in each case; hence the contribution to (3.4) is 1 + (−1)^{n}. If A ∪ B = ∅ we have A = B = ∅ and a contribution to (3.4) of |C| = (n − 1)!. In the remaining cases, A ∪ B is a union of j ≥ 1 vertex-disjoint paths. If these have the lengths l_{1}, …, l_{j}, and l = ∑_{i} l_{i} = |A ∪ B|, there are n − l − j remaining vertices. Thus there are j + n − l − j = n − l paths and isolated vertices, and there are (n−l −1)! Hamilton cycles D ⊃ A∪\overline{B}, which are obtained by taking these paths and vertices in any order (starting with a fixed one), travelling along each of the paths in the right direction. The contribution to (3.4) for such an A ∪ B is therefore

∑_{B}(−1)^{|B|}(n − l − 1)! = (n − l − 1)! ∏_{i=1}^{j}(1 + (−1)^{l_{i}})

= \{ \begin{matrix}2^{j}(n − l − 1)! & if all l_{i} are even, \\ 0 & if some l_{i} is odd. \end{matrix}  (3.5)

It remains to calculate the number of such A ∪ B ⊂ C with all l_{i} even for given j and l. Since l has to be even, we write l = 2k, and let M(j, k) be the sought number. We have to consider subsets of C that consist of j ≥ 1 paths of l_{i} = 2k_{i} ≥ 2 edges, i = 1, …, j, separated by gaps of lengths, say, m_{1}, …, m_{j} ≥ 1, with ∑_{i} k_{i} = k. Fix a vertex v ∈ C. By symmetry, exactly \frac{j}{n}M(j, k) of these subset have one of their j paths starting at v, we call these special subsets. Each special subset is uniquely determined by the sequences k_{1}, …, k_{j} and m_{1}, …, m_{j}, read in order along C starting at v. These sequences of integers ≥ 1 are subject to the conditions ∑_{i} k_{i} = k and ∑_{i} m_{i} = n − l = n − 2k only; hence they may be chosen in \binom{k−1}{j−1} and \binom{n−2k−1}{j−1} ways respectively, which gives a total of \binom{k−1}{j−1}\binom{n−2k−1}{j−1} special subsets. Since this equals \frac{j}{n}M(j, k), we have

M(j, k) = \frac{n}{j}\binom{k − 1}{j − 1}\binom{n − 2k − 1}{j − 1} = \frac{n(n − 2k − 1)! (k − 1)!}{(n − 2k − j)! (k − j)! j! (j − 1)!}.  (3.6)

(In particular, M(j, k) = 0 unless 1 ≤ j ≤ k and j ≤ n − 2k.) This and (3.5) enable us to complete the evaluation of (3.4) as

(n − 1)! \frac{E H_{n}^{2}}{(E H_{n})^{2}}

= 1 + (−1)^{n} + (n − 1)! + ∑_{k=1}^{⌊(n−1)/2⌋} ∑_{j=1}^{k∧(n−2k)} \frac{n(n − 2k − 1)!^{2}(k − 1)!}{(n − 2k − j)! (k − j)! j! (j − 1)!}2^{j}.

The result follows by dividing through by (n − 1)! and subtracting 1. □

It remains to estimate the terms in the sum in Lemma 3. This can be done rather crudely as follows. First, for k = 1 we have the single term with j = k = 1, which equals

\frac{n(n − 3)!}{(n − 1)!} · 2 = \frac{2n}{(n − 1)(n − 2)} = \frac{2}{n} + O(\frac{1}{n^{2}} );

this is the term we want. Secondly, for all terms we have

\frac{(n − 2k − 1)!}{(n − 2k − j)!} ≤ \frac{(n − 2k + j − 2)!}{(n − 2k − 1)!}

and thus, using j ≤ k and k ≤ (n − 1)/2,

\frac{n(n − 2k − 1)!^{2}}{(n − 1)! (n − 2k − j)!} ≤ n\frac{(n − 2k + j − 2)!}{(n − 1)!} ≤ n\frac{(n − k − 2)!}{(n − 1)!}

≤ n\frac{1}{(n − k − 1)^{k+1}} ≤ n(\frac{2}{n − 1})^{k+1} ≤ n(\frac{3}{n})^{k+1}.

Hence the sum of the terms with k ≥ 2 is at most

∑_{k=2}^{n} ∑_{j=1}^{k} n(\frac{3}{n})^{k+1} \frac{(k − 1)! 2^{j}}{(k − j)! j! (j − 1)!} ≤ ∑_{k=2}^{n} ∑_{j=0}^{k} 3(\frac{3}{n})^{k}\binom{k}{j}2^{j} = ∑_{k=2}^{n} 3(\frac{3}{n})^{k}3^{k} = O(n^{−2}).

Consequently, Lemma 3 yields

\frac{Var H_{n}}{(E H_{n})^{2}} = \frac{2}{n} + O(\frac{1}{n^{2}} ),

which verifies (1.2). We also obtain from this, using Lemma 2,

(E H_{n}S)^{2} = n^{2}(E H_{n})^{2} ∼ \frac{n^{3}}{2} Var H_{n},

and the asymptotic normality follows from Theorem 2. □

References

1. P. De Jong, A central limit theorem for generalized multilinear forms, J. Multivariate Anal. 34 (1990), 275–289.

2. O. Frank, Stochastic competition graphs, Rev. Internat. Stat. Inst. 36 (1971), 319–326.

3. J. Gruszka, Cycles in tournaments and random tournaments, Ph.D. dissertation, Adam Mickiewicz University, Poznań, 1990. (Polish)

4. S. Janson, The numbers of spanning trees, Hamilton cycles and perfect matchings in a random graph, Combinatorics, Probability & Computing (to appear).

5. S. Janson and K. Nowicki, The asymptotic distributions of generalized U-statistics with applications to random graphs, Probab. Th. Rel. Fields 90 (1991), 341–375.

6. T. Łuczak, A. Ruciński and J. Gruszka, On the evolution of a random tournament (to appear).

7. J.W. Moon, Topics on tournaments, Holt, Rinehart and Winston, New York, 1968.

8. P.A. Moran, On the method of paired comparisons, Biometrica 34 (1947), 363–365.

9. K. Nowicki, Asymptotic normality of triad counts in random digraphs, Stochastic Models 5 (1989), 163–180.

10. A. Ruciński, Proving normality in combinatorics, Random graphs, vol. 2, Wiley, New York, 1992, pp. 215–232.

Svante Janson, Department of Mathematics, Uppsala University, PO Box 480, S-751 06 Uppsala, Sweden

  E-mail address: svante.janson@math.uu.se