标题： Cayley和Tutte多面体的三角剖分 显示英文标题

标题： Triangulations of Cayley and Tutte polytopes

摘要： Cayley多面体最近被定义为Cayley在1857年引入的Cayley组合的凸包。 在本文中，我们解决了Braun的猜想，该猜想将Cayley多面体的体积用连通图的数量来表示。 我们将这一结果扩展到两种单变量变形的Cayley多面体（我们称之为t-Cayley和t-Gayley多面体），以及最一般的双变量变形，我们称之为Tutte多面体。 后者体积通过完全图的Tutte多项式的评估给出。 我们的方法基于Cayley和Tutte多面体的显式三角剖分。 我们证明了三角剖分中的单形对应于标记树。 证明的核心是一个基于邻居优先搜索图遍历算法的直接双射。 显示英文摘要

摘要： Cayley polytopes were defined recently as convex hulls of Cayley compositions introduced by Cayley in 1857. In this paper we resolve Braun's conjecture, which expresses the volume of Cayley polytopes in terms of the number of connected graphs. We extend this result to two one-variable deformations of Cayley polytopes (which we call t-Cayley and t-Gayley polytopes), and to the most general two-variable deformations, which we call Tutte polytopes. The volume of the latter is given via an evaluation of the Tutte polynomial of the complete graph. Our approach is based on an explicit triangulation of the Cayley and Tutte polytope. We prove that simplices in the triangulations correspond to labeled trees. The heart of the proof is a direct bijection based on the neighbors-first search graph traversal algorithm.