Random Perfect Matchings, in Tandem, of the Complete Graph K_2n
by
Anant Godbole
East Tennessee State University
Coauthors: Daniel B. Tenny, Cohen & Milstein Law Firm, New York

Let K_2n be the complete graph on 2n vertices. Form two perfect matchings of K_2n at random, and let X denote the number of edges common to the two matchings. Let P_n be the probability that these matchings are disjoint; in other words, let P_n=Pr(X=0). American Mathematical Monthly Problem No. 10587 asked for the value of lim_n→∞P_n, and it was shown there using a combinatorial argument that lim_n→∞P_n=e^-1/2. Here we generalize this result by showing that the distribution of X tends to a Poisson distribution as n→∞. We then further generalize the problem to dividing K_kn into n disjoint k-cliques, and show that the number of edges common to two such divisions tends to a Poisson distribution with mean (k-1)²/2. Finally, we explore, for k=2, the generalized cycle structure of the second random perfect matching, showing that the joint distribution of the cycle counts (of size up to b) can be approximated by a Poisson process with independent components provided that b²=o(n). Comparisons are made with parallel results for random permutations, where the best error bounds are superexponentially small; they are not in our case.

Date received: March 28, 2008

Copyright © 2008 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cawn-20.