The expected number of perfect matchings in cubic planar graphs
Visualitza/Obre
Eurocomb PM.pdf (244,0Kb) (Accés restringit)
Sol·licita una còpia a l'autor
Què és aquest botó?
Aquest botó permet demanar una còpia d'un document restringit a l'autor. Es mostra quan:
- Disposem del correu electrònic de l'autor
- El document té una mida inferior a 20 Mb
- Es tracta d'un document d'accés restringit per decisió de l'autor o d'un document d'accés restringit per política de l'editorial
10.1007/978-3-030-83823-2_27
Inclou dades d'ús des de 2022
Cita com:
hdl:2117/365009
Tipus de documentCapítol de llibre
Data publicació2021-09-01
EditorBirkhäuser
Condicions d'accésAccés restringit per política de l'editorial
Tots els drets reservats. Aquesta obra està protegida pels drets de propietat intel·lectual i
industrial corresponents. Sense perjudici de les exempcions legals existents, queda prohibida la seva
reproducció, distribució, comunicació pública o transformació sense l'autorització del titular dels drets
Abstract
A well-known conjecture by Lovász and Plummer from the 1970s asserting that a bridgeless cubic graph has exponentially many perfect matchings was solved in the affirmative by Esperet et al. (Adv. Math. 2011). On the other hand, Chudnovsky and Seymour (Combinatorica 2012) proved the conjecture for 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 (non 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. (Supported by the Ministerio de Economía y Competitividad grant MTM2017-82166-P, and by the Special Research Program F50 Algorithmic and Enumerative Combinatorics of the Austrian Science Fund.).
CitacióRue, J.; Requilé, C.; Noy, M. The expected number of perfect matchings in cubic planar graphs. A: "Extended Abstracts EuroComb 2021 : European Conference on Combinatorics, Graph Theory and Applications". Birkhäuser, 2021, p. 167-174.
ISBN978-3-030-83822-5
Versió de l'editorhttps://link.springer.com/chapter/10.1007/978-3-030-83823-2_27
Fitxers | Descripció | Mida | Format | Visualitza |
---|---|---|---|---|
Eurocomb PM.pdf | 244,0Kb | Accés restringit |