Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-16T02:08:58.045Z Has data issue: false hasContentIssue false

On the Number of Perfect Matchings in Random Lifts

Published online by Cambridge University Press:  09 June 2010

CATHERINE GREENHILL
Affiliation:
School of Mathematics and Statistics, University of New South Wales, Sydney, Australia2052 (e-mail: csg@unsw.edu.au)
SVANTE JANSON
Affiliation:
Department of Mathematics, Uppsala University, PO Box 480, S-751 06 Uppsala, Sweden (e-mail: svante.janson@math.uu.se)
ANDRZEJ RUCIŃSKI
Affiliation:
Department of Discrete Mathematics, Adam Mickiewicz University, Poznań, Poland61-614 (e-mail: rucinski@amu.edu.pl)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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 XG be the number of perfect matchings in a random lift of G. We study the distribution of XG 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 XG when G is d-regular, d ≥ 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 XG, with full details given for two example multigraphs, including the complete graph K4.

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.