论文标题
角polyhedra和三连接的Schnyder标签的枚举
Enumeration of corner polyhedra and 3-connected Schnyder labelings
论文作者
论文摘要
我们表明，Corner Polyhedra和3个连接的Schnyder标签加入了越来越多的平面结构列表，这些平面结构可以与（加权）象限步行模型确切地对应，这是由于Kenyon，Miller，Sheffield和Wilson所引起的。 我们的方法导致了第一个多项式时间算法来计算这些结构，并确定其确切的渐近生长常数：corter polyhedra的数量$ p_n $和3份连接的schnyder标签的$ n $ $ n $ shign $ size shign $ n $ n $ n $ n}^$（p_n） 16/3 $ as $ n $进入无限。 尽管增长率是合理的，就像在先前已知的对应关系的情况下一样，由于现在的标准Denisov-Wachtel方法，渐近多项式校正对指数增长似乎并未遵循，这是由于基础串联步行的台阶集的双峰行为。但是，启发式论点表明，这些指数为$ -1-π/\ arccos（9/16）\ $ -4.23 $，对于$ p_n $和$ -1-π/\ arccos（22/27）\ arccos（22/27）\ -6.08 $，大约是$ s_n $的，这意味着相关的系列不是d-f-f-f-f-finite。
We show that corner polyhedra and 3-connected Schnyder labelings join the growing list of planar structures that can be set in exact correspondence with (weighted) models of quadrant walks via a bijection due to Kenyon, Miller, Sheffield and Wilson. Our approach leads to a first polynomial time algorithm to count these structures, and to the determination of their exact asymptotic growth constants: the number $p_n$ of corner polyhedra and $s_n$ of 3-connected Schnyder labelings of size $n$ respectively satisfy $(p_n)^{1/n}\to 9/2$ and $(s_n)^{1/n}\to 16/3$ as $n$ goes to infinity. While the growth rates are rational, like in the case of previously known instances of such correspondences, the exponent of the asymptotic polynomial correction to the exponential growth does not appear to follow from the now standard Denisov-Wachtel approach, due to a bimodal behavior of the step set of the underlying tandem walk. However a heuristic argument suggests that these exponents are $-1-π/\arccos(9/16)\approx -4.23$ for $p_n$ and $-1-π/\arccos(22/27)\approx -6.08$ for $s_n$, which would imply that the associated series are not D-finite.
