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

Direct link
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, 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
Mathematics
Identifiers
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
Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 330 hits
CiteExportLink to record
Permanent link

Direct link
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