uu.seUppsala University Publications
Change search
ReferencesLink to record
Permanent link

Direct link
On the Number of Perfect Matchings in Random Lifts
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Applied Mathematics.
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
Abstract [en]

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.
National Category
URN: urn:nbn:se:uu:diva-139413DOI: 10.1017/S0963548309990654ISI: 000283914600008OAI: oai:DiVA.org:uu-139413DiVA: diva2:381083
Available from: 2010-12-23 Created: 2010-12-23 Last updated: 2011-03-01Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text
By organisation
Analysis and Applied Mathematics
In the same journal
Combinatorics, probability & computing

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 116 hits
ReferencesLink to record
Permanent link

Direct link