On the expected number of perfect matchings in cubic planar graphs

• Autores: Marc Noy Serrano , Clément Requilé, Juanjo Rué Perna
• Localización: Publicacions matematiques, ISSN 0214-1493, Vol. 66, Nº 1, 2022, págs. 325-353
• Idioma: inglés
• Enlaces
  • Texto completo
• Resumen

  • A well-known conjecture by Lov´asz and Plummer from the 1970s asserted that a bridgeless cubic graph has exponentially many perfect matchings. It was solved in the affirmative by Esperet et al. ([13]). On the other hand, Chudnovsky and Seymour ([8]) proved the conjecture in the special case of cubic planar graphs. In our work we consider random bridgeless cubic planar graphs with the uniform distribution on graphs with n vertices. Under this model we show that the expected number of perfect matchings in labeled bridgeless cubic planar graphs is asymptotically cγn, where c > 0 and γ ∼ 1.14196 is an explicit algebraic number. We also compute the expected number of perfect matchings in (not necessarily bridgeless) cubic planar graphs and provide lower bounds for unlabeled graphs. Our starting point is a correspondence between counting perfect matchings in rooted cubic planar maps and the partition function of the Ising model in rooted triangulations.

• Referencias bibliográficas
  • N. Alon and S. Friedland, The maximum number of perfect matchings in graphs with a given degree sequence, Electron. J. Combin. 15(1) (2008),...
  • O. Bernardi and M. Bousquet-Mélou, Counting colored planar maps: algebraicity results, J. Combin. Theory Ser. B 101(5) (2011), 315–377. DOI:...
  • M. Bodirsky, M. Kang, M. Löffler, and C. McDiarmid, Random cubic planar graphs, Random Structures Algorithms 30(1–2) (2007), 78–94. DOI: 10....
  • B. Bollobás, “Random Graphs”, Cambridge Studies in Advanced Mathematics, 2nd edition, Cambridge University Press, 2011. DOI: 10.1017/CBO97805118140...
  • B. Bollobás, and B. D. McKay, The number of matchings in random regular graphs and bipartite graphs, J. Combin. Theory Ser. B 41(1) (1986),...
  • M. Bousquet-Mélou and A. Elvey Price, The generating function of planar Eulerian orientations, J. Combin. Theory Ser. A 172 (2020), 105183,...
  • E. Brézin, C. Itzykson, G. Parisi, and J. B. Zuber, Planar diagrams, Comm. Math. Phys. 59(1) (1978), 35–51. DOI: 10.1007/BF01614153.
  • M. Chudnovsky and P. Seymour, Perfect matchings in planar cubic graphs, Combinatorica 32(4) (2012), 403–424. DOI: 10.1007/s00493-012-2660-9.
  • A. Denise, M. Vasconcellos, and D. J. A. Welsh, The random planar graph, Festschrift for C. St. J. A. Nash-Williams, Congr. Numer. 113 (1996),...
  • R. Diestel, “Graph Theory”, Fifth edition, Graduate Texts in Mathematics 173, Springer, Berlin, 2017. DOI: 10.1007/978-3-662-53622-3.
  • M. Drmota, “Random Trees”, An interplay between combinatorics and probability, SpringerWienNewYork, Vienna, 2009. DOI: 10.1007/978-3-211-75357-6.
  • M. Drmota, M. Noy, and G.-R. Yu, Universal singular exponents in catalytic variable equations, J. Combin. Theory Ser. A 185 (2022), Paper...
  • L. Esperet, F. Kardoˇs, A. D. King, D. Král, and S. Norine, Exponentially many perfect matchings in cubic graphs, Adv. Math. 227(4) (2011),...
  • L. Esperet, F. Kardoˇs, and D. Král, A superlinear bound on the number of perfect matchings in cubic bridgeless graphs, European J. Combin....
  • B. Eynard, “Counting Surfaces”, CRM Aisenstadt Chair lectures, Progress in Mathematical Physics 70, Birkh¨auser/Springer, [Cham], 2016. DOI:...
  • S. Felsner, E. Fusy, and M. Noy, Asymptotic enumeration of orientations, Discrete Math. Theor. Comput. Sci. 12(2) (2010), 249–262. DOI: 10.46298/...
  • P. Flajolet and R. Sedgewick, “Analytic Combinatorics”, Cambridge University Press, Cambridge, 2009. DOI: 10.1017/CBO9780511801655.
  • Z. Gao and N. C. Wormald, Enumeration of rooted cubic planar maps, Ann.Comb. 6(3–4) (2002), 313–325. DOI: 10.1007/s000260200006.
  • O. Giménez and M. Noy, Asymptotic enumeration and limit laws of planar graphs, J. Amer. Math. Soc. 22(2) (2009), 309–329. DOI: 10.1090/S0894...
  • S. Janson, The numbers of spanning trees, Hamilton cycles and perfect matchings in a random graph, Combin. Probab. Comput. 3(1) (1994), 97–126....
  • S. K. Lando and A. K. Zvonkin, “Graphs on Surfaces and Their Applications”, With an appendix by Don B. Zagier, Encyclopaedia of Mathematical...
  • L. Lovász and M. D. Plummer, “Matching Theory”, North-Holland Mathematics Studies 121, Annals of Discrete Mathematics 29, North-Holland Publishing...
  • R. C. Mullin, On the enumeration of tree-rooted maps, Canadian J. Math. 19 (1967), 174–183. DOI: 10.4153/CJM-1967-010-x.
  • R. C. Mullin, E. Nemeth, and P. J. Schellenberg, The enumeration of almost cubic maps, in: “1970 Proc. Louisiana Conf. on Combinatorics, Graph...
  • M. Noy, Random planar graphs and beyond, in: “Proceedings of the International Congress of Mathematicians—Seoul 2014”, Vol. IV, Kyung Moon...
  • M. Noy, C. Requile, and J. Ru ´ e´, Enumeration of labelled 4-regular planar graphs, Proc. Lond. Math. Soc. (3) 119(2) (2019), 358–378. DOI:...
  • M. Noy, C. Requilé, and J. Rué, Asymptotic enumeration of labelled 4-regular planar graphs, Preprint (2020). arXiv:2001.05943.
  • M. Noy, C. Requilé, and J. Rué, Further results on random cubic planar graphs, Random Structures Algorithms 56(3) (2020), 892–924. DOI: 10.1002/...
  • J. Petersen, Die Theorie der regulären graphs, Acta Math. 15(1) (1891), 193–220. DOI: 10.1007/BF02392606.
  • B. Salvy and P. Zimmermann, GFUN: a Maple package for the manipulation of generating and holonomic functions in one variable, ACM Trans. Math....
  • P. G. Tait, Remarks on the colouring of maps, Proc. Roy. Soc. Edinburgh, 10(4) (1880), 501–503.
  • W. T. Tutte, On Hamiltonian circuits, J. London Math. Soc. 21(2) (1946), 98–101. DOI: 10.1112/jlms/s1-21.2.98.
  • W. T. Tutte, A census of planar triangulations, Canadian J. Math. 14 (1962), 21–38. DOI: 10.4153/CJM-1962-002-9.
  • W. T. Tutte, A census of Hamiltonian polygons, Canadian J. Math. 14 (1962), 402–417. DOI: 10.4153/CJM-1962-032-x.
  • W. T. Tutte, A census of planar maps, Canadian J. Math. 15 (1963), 249–271. DOI: 10.4153/CJM-1963-029-x.
  • W. T. Tutte, “Graph Theory as I Have Known It”, With a foreword by U. S. R. Murty, Reprint of the 1998 original, Oxford Lecture Series in...
  • L. G. Valiant, The complexity of computing the permanent, Theoret. Comput. Sci. 8(2) (1979), 189–201. DOI: 10.1016/0304-3975(79)90044-6.
  • T. R. S. Walsh and A. B. Lehman, Counting rooted maps by genus III: Nonseparable maps, J. Combinatorial Theory Ser. B 18(3) (1975), 222–259....