Hostname: page-component-f554764f5-sl7kg Total loading time: 0 Render date: 2025-04-12T23:08:06.398Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Number of Perfect Matchings in Random Lifts

Published online by Cambridge University Press: 09 June 2010

CATHERINE GREENHILL
Affiliation:
School of Mathematics and Statistics, University of New South Wales, Sydney, Australia2052 (e-mail: csg@unsw.edu.au)
SVANTE JANSON
Affiliation:
Department of Mathematics, Uppsala University, PO Box 480, S-751 06 Uppsala, Sweden (e-mail: svante.janson@math.uu.se)
ANDRZEJ RUCIŃSKI
Affiliation:
Department of Discrete Mathematics, Adam Mickiewicz University, Poznań, Poland61-614 (e-mail: rucinski@amu.edu.pl)

Abstract

LetG be a fixed connected multigraph with no loops. A randomn-lift ofG is obtained by replacing each vertex ofG by a set ofn vertices (where these sets are pairwise disjoint) and replacing each edge by a randomly chosen perfect matching between then-sets corresponding to the endpoints of the edge. LetXG be the number of perfect matchings in a random lift ofG. We study the distribution ofXG in the limit asn tends to infinity, using the small subgraph conditioning method.

We present several results including an asymptotic formula for the expectation ofXG whenG isd-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 ofXG, with full details given for two example multigraphs, including the complete graphK4.

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.

Type
Paper
Copyright
Copyright © Cambridge University Press 2010

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable

References

[1]Alon,N.,Benjamini,I.,Lubetzky,E. andSodin,S. (2007)Non-backtracking random walks mix faster.Commun. Contemp. Math.9585–603.CrossRefGoogle Scholar
[2]Amit,A. andLinial,N. (2002)Random graph coverings I: General theory and graph connectivity.Combinatorica221–18.CrossRefGoogle Scholar
[3]Amit,A. andLinial,N. (2006)Random lifts of graphs: Edge expansion.Combin. Probab. Comput.15317–332.CrossRefGoogle Scholar
[4]Amit,A.,Linial,N. andMatoušek,J. (2002)Random lifts of graphs: Independence and chromatic number.Random Struct. Alg.201–22.CrossRefGoogle Scholar
[5]Angel,O.,Friedman,J. andHoory,S. The non-backtracking spectrum of the universal cover of a graph. Preprint; available as arXiv:0712.0192v1 [math.CO].Google Scholar
[6]Burgin,K.,Chebolu,P.,Cooper,C. andFrieze,A. M. (2006)Hamilton cycles in random lifts of graphs.Europ. J. Combin.271282–1293.CrossRefGoogle Scholar
[7]Chebolu,P. andFrieze,A. M. (2008)Hamilton cycles in random lifts of complete directed graphs.SIAM J. Discrete Math.22520–540.CrossRefGoogle Scholar
[8]Greenhill,C.,Janson,S.,Kim,J. H. andWormald,N. C. (2002)Permutation pseudographs and contiguity.Combin. Probab. Comput.11273–298.CrossRefGoogle Scholar
[9]Friedman,J. (2008)A proof of Alon's second eigenvalue conjecture.Memoirs Amer. Math. Soc.195 no. 910.CrossRefGoogle Scholar
[10]Horton,M. D.,Stark,H. M. andTerras,A. A. (2008) Zeta functions of weighted graphs and covering graphs. InAnalysis on Graphs and its Applications, Vol. 77 ofProc. Sympos. Pure Math.,AMS,Providence, RI, pp.29–50.CrossRefGoogle Scholar
[11]Janson,S.,Łuczak,T. andRuciński,A. (2000)Random Graphs,Wiley,New York.CrossRefGoogle Scholar
[12]Linial,N. andRozenman,E. (2005)Random lifts of graphs: Perfect matchings.Combinatorica25407–424.CrossRefGoogle Scholar
[13]Oren,I.,Godel,A. andSmilansky,U. (2009)Trace formulae and spectral statistics for discrete Laplacians on regular graphs I.J. Phys. A: Math. Theor.42415101.CrossRefGoogle Scholar
[14]McMullen,P. (1984)Determinants of lattices induced by rational subspaces.Bull. London Math. Soc.16275–277.CrossRefGoogle Scholar
[15]Molloy,M. S. O.,Robalewska,H.,Robinson,R. W. andWormald,N. C. (1997)1-factorizations of random regular graphs.Random Struct. Alg.10305–321.3.0.CO;2-#>CrossRefGoogle Scholar
[16]Robinson,R. W. andWormald,N. C. (1984) Existence of long cycles in random cubic graphs. InEnumeration and Design (Jackson,D. M. andVanstone,S. A., eds),Academic Press,Toronto, pp.251–270.Google Scholar
[17]Robinson,R. W. andWormald,N. C. (1992)Almost all cubic graphs are Hamiltonian.Random Struct. Alg.3117–125.CrossRefGoogle Scholar
[18]Robinson,R. W. andWormald,N. C. (1994)Almost all regular graphs are Hamiltonian.Random Struct. Alg.5363–374.CrossRefGoogle Scholar
[19]Schnell,U. (1992)Minimal determinants and lattice inequalities.Bull. London Math. Soc.24606–612.CrossRefGoogle Scholar