The number of sets of k disjoint perfect matchings in K_{2n}.
Jeanette McLeod (DCS, ANU)
MSI Computational Mathematics (formerly AdvCom) Seminar SeriesDATE: 2007-04-30
TIME: 11:00:00 - 12:00:00
LOCATION: John Dedman Seminar Room G35
CONTACT: JavaScript must be enabled to display this email address.
ABSTRACT:
A perfect matching in a graph G is a set of pairwise vertex-disjoint edges in which every vertex of G is an endpoint of exactly one edge. We denote the collection of all sets of k edge-disjoint perfect matchings in K_{2n} by P(k,n).
In this talk, two methods of calculating an asymptotic number of sets of k edge-disjoint perfect matchings in K_{2n} will be presented. The first method employs a switching technique to prove that if k=o(n^{1/3}), then
|P(k,n)|\sim\frac{1}{k!}\biggl(\frac{(2n)!}{(2^n\,n!)}\biggr)^k\exp\bigl(\tfrac{1}{4}k(1{-}k)\bigr).
The second method produces a more accurate result than the first. It relies on a theorem of Godsil's which proves that the number of perfect matchings in the complement of $G$ is
\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{\infty}e^{-x^2/2}\alpha(G,x)\,dx,
where \alpha(G,x) is the matchings polynomial of G. By considering the case where G is a k-regular graph with 2n vertices and using the Laplace method to approximate the above integral, it will be shown that
|P(k,n)|\sim \frac{1}{k!}\biggl(\frac{(2n)!}{2^{n}n!}\biggr)^{\negmedspace k} \biggl(\frac{(2n)!}{(2n)^k(2n{-}k)!}\biggr)^{\negthickspace n} \biggl(1{-}\frac{k}{2n}\biggr)^{n/2}e^{k/4},
for k=o(n^{5/6}). Both estimates of |P(k,n)| improve upon an
existing result of Bollobas who solved this problem for
constant k.
