Matjaž Konvalinka ; Igor Pak - Cayley and Tutte polytopes

dmtcs:3055 - Discrete Mathematics & Theoretical Computer Science, January 1, 2012, DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012) - https://doi.org/10.46298/dmtcs.3055
Cayley and Tutte polytopes

Authors: Matjaž Konvalinka ; Igor Pak

    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 a 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 and forests. The heart of the proof is a direct bijection based on the neighbors-first search graph traversal algorithm.


    Volume: DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012)
    Section: Proceedings
    Published on: January 1, 2012
    Imported on: January 31, 2017
    Keywords: polytopes, volume, Cayley compositions, Tutte polynomial,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

    Share

    Consultation statistics

    This page has been seen 119 times.
    This article's PDF has been downloaded 325 times.