论文标题
关于立方平面图中预期的完美匹配数量
On the expected number of perfect matchings in cubic planar graphs
论文作者
论文摘要
Lovász和Plummer的一个众所周知的猜想是，1970年代的Plummer声称，无用的立方图呈指数呈成倍的完美匹配。 Esperet等人在肯定的肯定中解决了它。 （Adv。Math。2011）。另一方面，Chudnovsky和Seymour（Combinatorica 2012）证明了Cubic Planar图的特殊情况。在我们的工作中，我们考虑了随机无桥的立方平面图，其图形上的均匀分布和$ n $顶点。在此模型下，我们表明，标记为无用的立方平面图中预期的完美匹配数是$Cγ^n $，其中$ c> 0 $和$γ\ sim 1.14196 $是明确的代数数。我们还计算了（非必然是无用的）立方平面图中预期的完美匹配数，并为未标记的图提供了下限。我们的起点是在扎根的立方平面图中计数完美匹配与根系三角形中Ising模型的分区函数之间的对应关系。
A well-known conjecture by Lovász 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. (Adv. Math. 2011). On the other hand, Chudnovsky and Seymour (Combinatorica 2012) 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 $γ\sim 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.
