A determinant-based algorithm for counting perfect matchings in a general graph
Steve Chien

Abstract
We present a simple estimator for the numb er of p erfect matchings in a general (non-bipartite) graph. Our estimator requires O( -2 3n/2 ) trials to obtain a (1 ± )-approximation of the correct value with high probability on a graph with 2n vertices in the worst case, and only a p olynomial numb er (O( -2 n (n)) of trials on random graphs, where  (n) is any function tending to infinity. Our algorithm is based on the following idea: For any graph G, construct its associated Tutte matrix T , and derive a random matrix B from it by replacing each variable in T with ±1 uniformly at random; then output det B . This estimator is a natural generalization of the Godsil­ Gutman estimator for matchings in a bipartite graph, and our analysis of its p erformance on random graphs b orrows generously from Frieze and Jerrum's analysis of a similar estimator for bipartite graphs.

1

Intro duction

We investigate the problem of determining for any graph G = (V = [2n], E ) the number of perfect matchings M (G) in G. Computing M (G) exactly for bipartite graphs is equivalent to computing the permanent of a (0, 1) matrix and was shown by Valiant to be #Pcomplete [11]. A wide variety of approaches have been designed to approximate M (G) for bipartite graphs. The most successful of these has been the Markov chain Monte Carlo approach, which recently led to a ful ly polynomial randomized approximation scheme for the bipartite case [8, 9]. Such an algorithm is capable of pro ducing, for any graph G, and any value  (0, 1], a value that approximates M (G) within a factor 1 ± with high probability, using time only polynomial in n and 1/ . So far, however, there is no such algorithm for general graphs; for example, if N (G) is the number of nearperfect matchings in G, the Markov chain metho d requires time polynomial in the ratio N (G)/M (G), which may be exponential in n. In this paper, we present a simple and elegant algorithm for approximating M (G) for general graphs

that reduces the problem to computing determinants of random matrices. As such, it is reminiscent of the similar algorithms for bipartite graphs pioneered by Go dsil and Gutman [4], and later extended by Karmarkar et al. [10], Barvinok [1, 2], and Chien, Rasmussen and Sinclair [3]. In fact, our algorithm can be seen as a natural generalization of the Go dsil­ Gutman estimator. For an input graph G with 2n vertices, our algorithm constructs its asso ciated Tutte matrix T , a 2n×2n skew-symmetric symbolic matrix whose nonzero entries are formal variables xij . We derive from this a random matrix B by replacing each variable xij in T with a uniform random element ±1. We define our estimator XG to be the random variable det B and show that it is unbiased; i.e., E[XG ] = M (G). We are also able to bound the variance of our estimator. In general, given any unbiased estimator X of M (G), the number of samples required to obtain a 1 ± -factor approximation of M (G) with high probability 2 2 is const E[X ]2] . The ratio E[X ]2] is called the critical ratio 2 E [X E [X of the estimator. Our first main result is the following: Theorem. Given any graph G with 2n vertices, the E [X 2 ] estimator XG is unbiased, and the critical ratio E[X G]2
G

is bounded above by 3n/2 . In our second main result, we show that the critical ratio is much lower for random graphs. Emulating the analysis of Frieze and Jerrum [5] for bipartite graphs, we show the following result: Theorem. Let  (n) be any function tending to infinity. Then almost every graph G  G2n,p=1/2 satisfies
2 E[XG ] E[XG ]2

 n (n) for a fixed constant .

This paper is organized as follows: We define the estimator and bound its worst case performance in  Microsoft Research, 1065 La Avenida, Mountain View Section 2. The analysis of the estimator's behavior CA 94043. Work performed while at Computer Science Divi- on random graphs is in Section 3, and we discuss its sion, University of California, Berkeley CA 94720-1776, U.S.A. similarity to the Go dsil­Gutman family of bipartite and supported by NSF grants CCR-9820951 and CCR-0121555. estimators and possible extensions in Section 4. Email:schien@microsoft.com.
Copyright © 2004 by the Association for Computing Machinery, Inc. and the Society for industrial and Applied Mathematics. All Rights reserved. Printed in The United States of America. No part of this book may be reproduced, stored, or transmitted in any manner without the written permission of the publisher. For information, write to the Association for Computing Machinery, 1515 Broadway, New York, NY 10036 and the Society for Industrial and Applied Mathematics, 3600 University City Science Center, Philadelphia, PA 19104-2688

728


where C (G ) is the set of cycle covers in G and sgn() = -12n-c(), where c() is the number of cycles in . 2.1 The Tutte Matrix. Our estimator is based on Taking the expected value yields  ( the Tutte matrix of a graph. Given a graph G = (V = E[XG ] = sgn()E[ bij ]. [2n], E ) with 2n vertices, the Tutte matrix T is a 2n × 2n  C (G ) i,j ) skew-symmetric symbolic matrix with entries defined as follows: We will now show that cycle covers that correspond to perfect matchings contribute exactly 1 to the sum  E[XG ], while the expected contribution of all other cycle if {i, j }  E and i < j  xij covers is zero. tij = -xij if {i, j }  E and i > j  To see the first part, we observe that there is a 0 otherwise bijection between perfect matchings in G and cycle It is well known that the Tutte matrix is related covers in G in which each cycle has length 2. This to perfect matchings in a graph; for example the bijection maps a perfect matching  given by the edges determinant of the Tutte matrix is nonzero if and only {u1 , v1 }, . . . , {un , vn } to the cycle cover  consisting if the graph contains a perfect matching. of the n length-2 cycles (ui , vi ). The contribution of n this cycle cover to E[XG ] is sgn()E[ i=1 bui ,vi bvi ,ui ]. 2.2 The Estimator. We are now prepared to define From the structure of the Tutte matrix, we have that our estimator as described in the Introduction: bui ,vi = -bvi ,ui , and from our algorithm we have that b2 i ,vi = 1, so this becomes sgn()(-1)n = (-1)n (-1)n u · Given a graph G = (V = [2n], E ), construct its = 1. Hence each perfect matching contributes exactly 2n × 2n Tutte matrix T . 1 to our estimator. Now consider a cycle cover  in which at least · Obtain a random matrix B by replacing each one cycle has length k > 2; let this cycle consist of variable xij by an element chosen uniformly at the (o( dered) vertices (u1 , . . . , uk ). Then the prodr random from the set {±1} and leaving the zeros uct i,j ) bij corresp onding to this cycle cover will unchanged. contain the term bu1 ,u2 but not bu2 ,u1 . Since bu1 ,u2 is independent of all other terms in the product and · Output XG = det B . ( E[bu1 ,u2 ] = 0, we have that E[ i,j ) bij ] = 0, as reWe first prove that the estimator is unbiased: quired. 2 The Algorithm Performance and Its Worst-Case Theorem 2.1. E[XG ] = M (G). Proof. By definition, we have XG = det B =  sgn( )
S2n

i2n

bi,i .

2.3 Worst-Case Performance. We now turn our attention to bounding the variance of the estimator. Specifically, we prove the following theorem, which combined with Theorem 2.1 establishes our first main result from the Introduction: Theorem 2.2. The critical ratio of the estimator XG is bounded by 2 E[XG ] n/2 2 3 E[XG ] Proof. We first consider the denominator of the critical ratio, E[XG ]2 . Since E[XG ] = M (G), E[XG ]2 is the number of ordered pairs of perfect matchings. Observe that for any two perfect matchings,  and  , their union H =    is a subgraph of G consisting of isolated edges and even-length cycles in G. Further, if c(H ) is the number of cycles in H , then there are exactly 2c(H ) ordered pairs of perfect matchings whose union is H , as each cycle in H can be formed in two ways. Thus, if we define P (G) to be the set of subgraphs of G consisting only of isolated edges and even length cycles, then we

=1

First note that for any   S2n its contribution 2n sgn( ) i=1 bi,i to det B is nonzero if and only if {i,  i}  E for all i; in this case we call  a nonzero permutation. Now consider the modified graph G = (V , E ) in which we replace each edge {i, j }  E with a pair of directed edges (i, j ) and (j, i) in E having respective weights bij and bj i . There is a natural bijection between nonzero permutations   S2n and (directed) cycle covers of V using the 2n edges (i,  i) in E . The product 2n i=1 bi,i can then b e interpreted as the pro duct of the weights bi,i of the edges in the cycle cover, allowing us to write  ( XG = sgn() bij ,
 C (G
)

i,j )

729


can rewrite E[XG ] as

 (or  ) if at least one of the directed edges (i, j ) or (j, i) is in  (or  ). Since E[bij ] = 0 and bij is independent H 2 c (H ) (2.1) 2 . E[XG ] = of all other entries in B except for bj i , we can see that  P (G ) E[B B ] = 0 unless every edge in G is covered an even number of times by  and  . From this we can conclude Now consider the numerator of the critical rathat the set of edges in G covered by  and  must 2 tio, the second moment E[XG ]. Recall from the consist only of isolated edges and even-length cycles; proof of Theorem 2.1 that we can write XG =  ( i.e., these edges form a subgraph H  P (G). a nd C (G ) defined C (G ) sgn() i,j ) bij , with G We must now determine for each H  P (G) the as before. It will also be helpful to introduce the nota( number of pairs of (,  )  E (G ) × E (G ) whose union tion B = sgn() i,j ) bij for the contribution of the    covers exactly H , with each edge in H covered cycle cover  to XG . an even number of times. The answer turns out to be We now make the important known observation c(H ) 6 , where c(H ) is again the number of cycles in H . that in XG we can ignore any cycle cover  in C (G ) To see this, note that any (undirected) even-length cycle that contains a cycle of odd length: i C = (u1 , u2 , . . . , u2k ) in H can be covered by  and  n six different ways: Lemma 2.1. (  ·  and  can each correspond to a perfect bij , sgn() XG = matching when restricted to C , with  covi,j )  E (G ) ering the edges {u1 , u2 }, {u3 , u4 } . . . , {u2k-1 , u2k } twice each while  covers the remaining edges where E (G )  C (G ) consists of only those cycle covers {u2 , u3 }, {u4, u5 } . . . , {u2k , u1 }, or vice versa, for a in which every cycle is of even length. total of two different ways. Proof. We will show that each cycle cover  containing ·  and  can both be directed cycles when restricted an odd cycle can be matched with another such cycle to C . Here,  and  can each run in either direction cover  so that B = -B . As a result, the total (u1 , u2 , . . . , u2k ) or (u1 , u2k , . . . , u2 ), for a total of contribution of these cycle covers to XG will be zero. four different ways. Suppose  contains an odd length cycle; let  consist of cycles C1 , . . . , Ct , written in some canonical order, We can check that in each of these 6c(H ) pairs, we have and let Ci = (u1 , u2 , . . . , uk ) with k odd be its first odd that B B = 1. Therefore, we can rewrite the second cycle. Then  will be the cycle cover that is identical moment of XG as H c to  except that the direction of Ci is reversed; i.e.  2 E[XG ] = 6 c (H ) . ontains the cycle (u1 , uk , uk-1 , . . . , u2 ) instead of Ci .  P (G ) We now claim that B = -B . To see this, note that the only difference between B and B is that Combining this with equation (2.1), we can bound the c B contains the product bu1 ,u2 bu2 ,u3 · · · buk ,u1 while B critical ratio as H c (H ) ontains the product bu1 ,uk buk-1 ,uk-2 · · · bu2 ,u1 . From 2 E[XG ] 6 c (G )  P (G ) 6 =H  max c(G)  3n/2 the structure of the Tutte matrix, we can rewrite the 2 c (H ) H  P (G ) 2 E[XG ]  P (G ) 2 latter product as (-buk ,u1 )(-buk-2 ,uk-1 ) · · · (-bu1 ,u2 ) = (-1)k bu1 ,u2 bu2 ,u3 · · · buk ,u1 . Since k is odd, we have that This completes the proof of Theorem 2.2. B = -B as required. 2.4 Lower Bounds. The upper bound of 3n/2 on This lemma allows us to write the critical ratio of XG matches the best known upper ( ( ( bound for the Godsil­Gutman estimator for perfect 2 ) E[XG ] = sgn(,  E[ bij ij ] matchings in a bipartite graph, which can be seen as a ,  ) i,j ) i,j ) b special case of our estimator (see Section 4 for details). ( = sgn(,  )E[B B ], However, we can show a larger worst-case lower bound ,  ) on the critical ratio of XG in the non-bipartite case. In particular, if we let G be the graph consisting n where the sum is over all ordered pairs (,  )  E (G ) × of 2 copies of the complete graph K4 , then the critical 7 E (G ) of cycle covers in which every cycle is of even ratio of XG is ( 3 )n/2 . In contrast, the best known lower bound for the bipartite case occurs when G consists of length. n Consider now a particular pair (,  )  E (G ) × 2 copies of the complete bipartite graph K2,2 , in which ) E (G . We will say that an edge {i, j } in G is covered by case the critical ratio is 2n/2 .

2

730


3 Random Graphs We now show that this estimator performs well on random graphs. In doing so, we closely follow Frieze and Jerrum's analysis for similar estimators on bipartite graphs [5]. First, it will be convenient later to restate Theorem 2.2 as follows:

 c( ,0 ) ~ 3. fn , the value defined as , where Fn 3 c( , 0 ) is the number of components in   0 , ~ i.e. the total number of cycles and isolated edges.  c( ,0 ) ~ 4. hn , the value defined as , where Hn 3 c( , 0 ) is the number of components in   0 . ~ (In this case, c( , 0 ) is the total number of cycles, ~ as there are no isolated edges.)

Corollary 3.1. Given a graph G, define  (G) = Note that |Hn |,fn , and hn are independent of the ) E[3c(, ], where  and  are perfect matchings chosen choice of  . Further, it is well known that |F | = 0 n uniformly at random from G and c( ,  ) is the number (2n - 1)!! and we can show f = (2n + 1)!!, where n of cycles (not including isolated edges) in    . Then the notation t!! is taken to mean t(t - 2)(t - 4) · · · 1. From there we can bound |Hn | and hn using inclusion2 E[XG ] exclusion to obtain =  (G). 2 E[XG ] n!2n |Hn | = (  ) Let G2n,m denote the set of graphs on 2n vertices n with m edges, and let G  G2n,m denote choosing a graph uniformly at random from G2n,m . The following and  hn = O(n!2n n). result from Janson [6] on the concentration of the number of perfect matchings M (G) will prove useful: (See Appendix for details on bounding fn , |Hn | and hn .) Thus for any fixed perfect matching 0 on K2n , the 2 ~ Theorem 3.1. (Janson) Let G  G2n,m where m3  expectation of 3c(,0 ) over all derangements  from 0 n . Then is hn E[M (G)2 ] n3 ~ (3.2) = O(n). E [3c(,0 ) ] = = 1 + O( 2 ). 2 |Hn | m E[M (G)] Frieze and Jerrum now use the following procedure We now prove the following result: to choose a triple (G,  ,  )   uniformly at random: Theorem 3.2. Let m = m(n) and  =  (n) be functions satisfying 0 <  < 1 and m2  n-3   as n  . Assume n is sufficiently large, and select G  G2n,m . Then for some fixed constant , we have Pr( (G)  n -1 )  1 -  . The proof of this theorem rests largely on the following lemma: Lemma 3.1. Let  be the set of triples (G,  ,  ) where G is a graph on the vertex set V = [2n] with m edges and  and  are perfect matchings in G. Then 1( || 1. Choose k from the range 0, . . . , n from an "appropriate" (defined below) distribution. 2. Choose  and  uniformly at random from the pairs of perfect matchings on K2n such that  and  share exactly k edges. 3. Choose G uniformly at random from the set of all graphs with m edges that contain  and  .

If in step 1 we choose k with the probability that  and  share exactly k edges in a random choice ) 3c(, = O(n). of (G,  ,  ), then this procedure results in a uniform )  G, , choice from , as the number of ways of extending  and  to a graph with m edges depends only on k . ) Proof. Before tackling the main part of the proof, we ~ Note also in step 2 that the expected value E, [3c(, ] first perform some preliminary computations on the ) ~ of 3c(, over all choices of  and  is the same as following ob jects, where 0 is an arbitrary fixed perfect in equation (3.2) with parameter n - k , and therefore matching in the complete graph K2n : bounded above by O(n - k ) = O(n). Hence we get 1. Fn , the set of all perfect matchings on K2n . ) 1( 3c(, = O(n), || 2. Hn , the set of perfect matchings on K2n that share G ,  ,  )  no edges with 0 ; we will call these derangements from 0 . concluding the proof of Lemma 3.1.

731


for counting perfect matchings in a bipartite graph, and the implications for extending our estimator for general Proof. (Theorem 3.2) Let G  G2n,m . Combining Jangraphs. son's bound from Theorem 3.1 and applying Chebyshev's inequality, we obtain Pr(M (G)   E[M (G)]) = 4.1 The Go dsil­Gutman Estimators. The origin3 O( m2 ) for any constant  < 1. For concreteness we nal Godsil­Gutman estimator [4] is based on the folwill use Frieze and Jerrum's choice of  = 3 , though lowing simple idea: Given a bipartite graph G = (U = 4 in our case any value would work. This implies that [n], V = [n], E ), construct its n × n adjacency matrix A, n3 Pr(M (G)2  19 E[M (G)]2 ) = O( m2 ). in which aij = 1 if (i, j )  E . Derive from A a random 6 For sufficiently large n, E[M (G)2 ]  (1 + matrix D by replacing each 1-entry in A independently 2 )E[M (G)] for any > 0, so we can write Pr(M (G)2  with an element of {±1} chosen uniformly at random; n3 1 2 then output YG = (det D)2 . It can be easily shown that 2 E[M (G) ]) = O( m2 ). Now notice that Lemma 3.1 can be restated as E[YG ] = M (G). Karmarkar et al. [10] later showed that the worst G 1 (3.3) M (G)2  (G)  cn case critical ratio for YG is bounded above by 3n/2 , || and improved Godsil and Gutman's algorithm by usfor some constant c and sufficiently large n. Let N ing complex numbers. Specifically, they form the rann be the number of graphs on V = [2n] with m edges. dom matrix D by replacing each 1-entry i1 dependently with an element from the set {±1, ±i} chosen uniAssume for the purpose of contradiction that there exist more than  N graphs G with  (G) >  n , for formly 2at random and define their estimator to be  | det D| = (det D)(det D). They then proved that this n3 some fixed  > 2c. Since at most O( m2 )N graphs new complex estimator has a worst case critical ratio of 1 G have M (G)2  2 E[M (G)2 ], then at least ( - 2n/2 . 3 n O( m2 ))N "misbehaved" graphs have both  (G) >  n This idea was then carried to higher-dimensional al 1 and M (G)2 > 2 E[M (G)2 ]. gebras by Barvinok [1] as well as by Chien, Rasmussen The contribution of just the misbehaved graphs to and Sinclair [3]. The latter authors proved that, by rethe left hand side of inequality (3.3) is at least placing each 1-entry of A with a randomly chosen signed basis element from an appropriate higher-dimensional 3 3 n 1 n 1 n 1 ( - O( 2 ))N E[M (G)2 ] = ( - O( 2 ))n. Clifford algebra to form D, the worst case critical ratio || m 2  2 m can be driven down to a constant. This would lead to a n3 Since m2  tends to zero and  > 2c, this yields a fully polynomial randomized approximation scheme for the bipartite case if det D can be computed in polynocontradiction, finishing the proof. mial time, though no algorithm for doing so is known. We can now convert the result from the G2n,m model The main obstacle is that Clifford algebras are not in to the G2n,p model using known results for asymptotic general commutative, and hence standard determinant equivalence between the two models; see for example, algorithms (e.g. Gaussian elimination) fail. Proposition 1.12 of [7]. This yields In this final section we relate the results of this paper to the previous work for bipartite graphs. Corollary 3.2. Let p = p(n) and  =  (n) be functions satisfying 0 < p,  < 1 and p2  n   as 4.2 The General and Bipartite Estimators. It n  . Assume n is sufficiently large, and select turns out that our estimator for general graphs XG G  G2n,p . Then for some fixed constant , we have is a generalization of the Godsil­Gutman bipartite n Pr( (G)    )  1 -  . estimator YG : 1 Fixing p = 2 results in the second main result of Proposition 4.1. Let G be a bipartite graph on (U = this paper: [n], V = [n], E). Then the two estimators XG and YG Corollary 3.3. Let  (n) be any function tending to are identical. infinity. Then for some fixed constant , almost every E [X 2 ] Proof. First, let us consider YG . This estimator builds graph G  G2n,1/2 satisfies E[X G]2 =  (G)  n (n). G the adjacency matrix A for G, derives D from this We are now prepared to prove Theorem 3.2: 4 Comparison with Bipartite Estimators In this section we discuss the relationship between our estimator and the Godsil­Gutman family of estimators
Karmarkar et al used complex cube roots of unity, rather than fourth roots as stated here, which leads to the same asymptotic behavior.
1 Actually,

732


by replacing each 1-entry with ±1, and then computes (det D)2 . We now show that XG carries out the same procedure. Let us order the vertices of G so that those in U precede those in V . Then the Tutte matrix T of G has th w e form 0 T0 T= -T0 0

lead to a possible fully polynomial randomized approximation scheme for matchings in a general graph, conditioned on the ability to efficiently compute a higherdimensional determinant. Acknowledgements The author would like to thank Alistair Sinclair for many helpful conversations.

here T0 is the transpose of T0 , and so the estimator References will construct the random matrix 0 , B0 [1] A. Barvinok, Polynomial time algorithms to approxB= -B0 0 imate p ermanents and mixed discriminants within a where B0 is formed by replacing each variable xij in T0 with ±1. Since the variable xij is present if and only if (i, j )  E , B0 is formed in exactly the same manner as D. Noticing that XG = det B = (det B0 )2 finishes the proof. 4.3 Extending the Estimator. It is natural to ask whether the sequence of improvements to the Godsil­ Gutman estimator discussed above can be applied to the estimator for general graphs. Unfortunately, a straightforward generalization fails at the very next step. The complex estimator for the bipartite case constructs a random matrix D and then computes (det D)(det D), suggesting that the complex estimator for the general case should construct a modified Tutte matrix T of the form 0 , T0 T= -T0 0 leading to a random matrix B of the form 0 . B0 B= -B0 0 In this case, det B = (det B0 )(det B0 ), as desired, and we do obtain an unbiased estimator. However, a key step in the analysis of the second moment fails: Lemma 2.1, which allows us to ignore cycle covers containing odd cycles, is no longer true. As a result, this new estimator may have larger variance than the original estimator on graphs with many odd cycles. This is not a problem with bipartite graphs, of course, as there are no odd cycles there. Nonetheless, it is plausible that a modified estimator using complex numbers may still work for general graphs. If so, it would be interesting to see if further improvements along the lines of Barvinok [1] and Chien, Rasmussen and Sinclair [3] are also possible. This would
[2] [3]

[4]

[5]

[6]

[7] [8]

[9]

[10]

[11]

simply exp onential factor, Random Structures and Algorithms 14 (1999), 29­61. A. Barvinok, "New p ermanent estimators via noncommutative determinants," Preprint, July 2000. S. Chien, L. Rasmussen and A. Sinclair,"Clifford algebras and approximating the p ermanent," Proceedings of the 34th ACM Symposium on Theory of Computing, 2002, pp. 222­231. C. Godsil and I. Gutman, "On the matching p olynomial of a graph," Algebraic Methods in Graph Theory, 1981, pp. 241­249. A. Frieze and M. Jerrum, "An analysis of a Monte Carlo algorithm for approximating the p ermanent," Combinatorica 15 (1995), pp. 67­83. S. Janson, "The numb er of spanning trees, Hamilton cycles, and p erfect matchings in a random graph," Combinatorics, Probability and Computing 3 (1994), pp. 97­126. ´ S. Janson, T. Luczak, and A. Rucinski, Random Graphs, Wiley Interscience, 2000. M. Jerrum and A. Sinclair, "Approximating the p ermanent," SIAM Journal on Computing 18 (1989), pp. 1149­1178. M. Jerrum, A. Sinclair, and E. Vigoda, "A p olynomial-time approximation algorithm for the p ermanent of a matrix with non-negative entries," Proceedings of the 33rd ACM Symposium on Theory of Computing, 2001, pp. 712­721. ´ N. Karmarkar, R. Karp, R. Lipton, L. Lovasz, and M. Luby, "A Monte-Carlo algorithm for estimating the p ermanent," SIAM Journal on Computing 22 (1993), pp. 284­293. L.G. Valiant, "The complexity of computing the p ermanent," Theoretical Computer Science 8 (1979), 189­201.

App endix: Computing fn , |Hn | and hn in Lemma 3.1 First, we prove the following formula for fn :  c ( ,  0 ) ~ Lemma A.1. Recal l that fn = . Then Fn 3 fn = (2n + 1)!!

733


Proof. We show this by induction. The base case of Lemma A.2. f1 is easily verified to be 3. For the case of fn+1 ,  (2t + 1)!! consider the complete graph K2(n+1) and some fixed = (2t t) t! perfect matching 0 in it. Fix one particular edge {i, j } in 0 ; we now partition the set of all perfect matchings Proof.  in K2(n+1) into classes based on how vertices i and 2t + 1 2t - 1 3 (2t + 1)!! j are matched by  , and consider the contribution of = ··· t! t t-1 1 each of these classes to fn+1 . Specifically, we have the 3 t 2t + 1 2t - 1 following three classes: = 2( )( )···( ) 2t 2t - 2 2  1. Vertices i and j can be matched to each other in = (2t t)  . Thus i and j form their own component in   0 independent of the other 2n vertices. The contribution to fn+1 from this class is then 3 × fn . From this, we can bound |Hn | and hn using inclusion-exclusion as follows: 2. Vertices i and j can be matched to vertices k and , respectively, in  , where {k , } is an edge Lemma A.3. |Hn | and hn satisfy the fol lowing bounds: in 0 . Then (i, k , , j ) is a component in   0 n!2n independent of the remaining 2(n - 1) vertices. |Hn | = (  ) n There are 2n ways i and j can be matched in this  manner, and so the total contribution to fn+1 is hn = O(n!2n n) 2n × 3 × fn-1 . Proof. We first show a lower bound for |Hn |: 3. Finally, i and j can be matched to vertices k and n| n| in  , where k and are not matched to each n |Hn | = |Fn | - Fn-1 | + · · · + (-1) F0 | other in 0 . Let k be matched to k and be 1 n n| matched to in 0 . Then the sequence of vertices kn = (-1)k Fn-k | (k , k , i, j, , ) is part of a component in  0 . The k =0 contribution to fn+1 from this situation is equal to fn-1 , as we can imagine consolidating the sequence kn n! , , [2(n - k ) - 1]!! = (-1)k (k k , i, j, , ) into a single edge {k } in 0 in the k !(n - k )! =0 smaller complete graph K2(n-1) , having removed k n (-1)k  vertices i, j, k , . 1 = n! (2n-k n - k) k ! (2(n - k ) + 1) There are 2n(2n-2) ways of choosing k and in this =0 case, for a total contribution of 2n(2n - 2) × fn-1 . From this case analysis, we can write fn+1 = = = = = = 3fn + 6nfn-1 + (4n2 - 4n)fn-1 3fn + 2n(2n + 1)fn-1 3fn + 2n(2n + 1)!! 3(2n + 1)!! + 2n(2n + 1)!! (2n + 3)!! 3fn + 2n(2n + 1)(2n - 1)!!

Now note that the sum  the first two terms (k = 0 of  1 and k = 1) is 2n1 1 (2n n) - 2(2n-1) (2n n - 1) = +  (2n / n), and in every subsequent pair of terms the positive term has larger magnitude that the negative n  term. Hence |Hn | = ( n!2 ). n We then show an upper bound for hn : n3 n3 n 1 n f0 hn = f n - fn-1 + · · · + (-1) n 1 nf kn = (-3)k n-k k
=0

where in the third and fifth lines we have used the inductive hypothesis. This completes the proof. We now provide details on the bounds for |Hn | and hn used in the proof of Lemma 3.1. We first show the following lemma:

=

kn

=0

(-3)k

= n!

k n (-3)k  (2n-k n - k ) k!
=0

n! [2(n - k ) + 1]!! k !(n - k )!

734


Again, note that the sum  the first three terms of  3 in the summation is (2n n) - 2 (2n n - 1) +   9 n n - 2) = (2n n). In every subsequent pair 8 (2 of terms, the negative term has larger magnitude than the positive term. Therefore we can conclude hn =  O(n!2n n).

735