On the expected number of perfect matchings in cubic planar graphs
Noy, Marc (Universitat Politècnica de Catalunya. Departament de Matemàtiques)
Requilé, Clément (Technische Universität Wien. Institute of Discrete Mathematics and Geometry)
Rué, Juanjo (Universitat Politècnica de Catalunya. Departament de Matemàtiques)

Fecha:	2022
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.
Ayudas:	Ministerio de Economía y Competitividad MTM2017-82166-P
Nota:	Marc Noy and Juanjo Rué were supported by Ministerio de Economía y Competitividad grant MTM2017-82166-P. Clément Requilé was supported by the Special Research Program F50 Algorithmic and Enumerative Combinatorics of the Austrian Science Fund.
Derechos:	Tots els drets reservats.
Lengua:	Anglès
Documento:	Article ; recerca ; Versió publicada
Materia:	Asymptotic enumeration ; Planar graphs ; Regular graphs
Publicado en:	Publicacions matemàtiques, Vol. 66 Núm. 1 (2022) , p. 325-353 (Articles) , ISSN 2014-4350

Adreça original: https://raco.cat/index.php/PublicacionsMatematiques/article/view/396530
DOI: 10.5565/PUBLMAT6612213

29 p, 454.1 KB

El registro aparece en las colecciones:
Artículos > Artículos publicados > Publicacions matemàtiques
Artículos > Artículos de investigación