On the Number of Perfect Matchings in Random Lifts
2010 (English)In: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 19, no 5-6, 791-817 p.Article in journal (Refereed) Published
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 >= 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.
Place, publisher, year, edition, pages
2010. Vol. 19, no 5-6, 791-817 p.
IdentifiersURN: urn:nbn:se:uu:diva-139413DOI: 10.1017/S0963548309990654ISI: 000283914600008OAI: oai:DiVA.org:uu-139413DiVA: diva2:381083