uu.seUppsala University Publications
Change search

Cite
Citation style
• apa
• ieee
• modern-language-association
• vancouver
• Other style
More styles
Language
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Other locale
More languages
Output format
• html
• text
• asciidoc
• rtf
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, p. 791-817Article 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, p. 791-817
Mathematics
##### Identifiers
ISI: 000283914600008OAI: oai:DiVA.org:uu-139413DiVA, id: diva2:381083
Available from: 2010-12-23 Created: 2010-12-23 Last updated: 2017-12-11Bibliographically approved

#### Open Access in DiVA

No full text in DiVA

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

doi
urn-nbn

#### Altmetric score

doi
urn-nbn
Total: 342 hits

Cite
Citation style
• apa
• ieee
• modern-language-association
• vancouver
• Other style
More styles
Language
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Other locale
More languages
Output format
• html
• text
• asciidoc
• rtf