Portal de Periódicos da CAPES

On the Number of Perfect Matchings in Random Lifts

2010; Cambridge University Press; Volume: 19; Issue: 5-6 Linguagem: Inglês

10.1017/s0963548309990654

1469-2163

Catherine Greenhill, Svante Janson, Andrzej Ruciński,

Markov Chains and Monte Carlo Methods

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.