Mathematics – Combinatorics
Scientific paper
2009-07-06
Mathematics
Combinatorics
29 pages; some minor rewording; change of notation for bilinear forms
Scientific paper
Let G be a fixed connected multigraph with no loops. A random n-lift of G is obtained by replacing each vertex of G by a set of n vertices (where these sets are pairwise disjoint) and replacing each edge by a randomly chosen perfect matching between the n-sets corresponding to the endpoints of the edge. Let X_G be the number of perfect matchings in a random lift of G. We study the distribution of X_G in the limit as n tends to infinity, using the small subgraph conditioning method. We present several results including an asymptotic formula for the expectation of X_G when G is d-regular, d\geq 3. The interaction of perfect matchings with short cycles in random lifts of regular multigraphs is also analysed. Partial calculations are performed for the second moment of X_G, with full details given for two example multigraphs, including the complete graph K_4. To assist in our calculations we provide a theorem for estimating a summation over multiple dimensions using Laplace's method. This result is phrased as a summation over lattice points, and may prove useful in future applications.
Greenhill Catherine
Janson Svante
Rucinski Andrzej
No associations
LandOfFree
On the number of perfect matchings in random lifts does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On the number of perfect matchings in random lifts, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the number of perfect matchings in random lifts will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-27483