Triangulations of Cayley and Tutte polytopes |
| |
Authors: | Matjaž Konvalinka Igor Pak |
| |
Institution: | 1. Department of Mathematics, University of Ljubljana, 1000 Ljubljana, Slovenia;2. Department of Mathematics, UCLA, Los Angeles, CA 90095, USA |
| |
Abstract: | 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. |
| |
Keywords: | Cayley polytope Tutte polytope Volume Tutte polynomial Bijective proof Neighbors-first search |
本文献已被 ScienceDirect 等数据库收录! |
|