Geodesic
Cayley and Tutte polytopes
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012), DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012) (2012).

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2012_special_263_a41,
     author = {Konvalinka, Matja\v{z} and Pak, Igor},
     title = {Cayley and {Tutte} polytopes},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012)},
     year = {2012},
     doi = {10.46298/dmtcs.3055},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3055/}
}
TY  - JOUR
AU  - Konvalinka, Matjaž
AU  - Pak, Igor
TI  - Cayley and Tutte polytopes
JO  - Discrete mathematics & theoretical computer science
PY  - 2012
VL  - DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3055/
DO  - 10.46298/dmtcs.3055
LA  - en
ID  - DMTCS_2012_special_263_a41
ER  - 
%0 Journal Article
%A Konvalinka, Matjaž
%A Pak, Igor
%T Cayley and Tutte polytopes
%J Discrete mathematics & theoretical computer science
%D 2012
%V DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3055/
%R 10.46298/dmtcs.3055
%G en
%F DMTCS_2012_special_263_a41
Konvalinka, Matjaž; Pak, Igor. Cayley and Tutte polytopes. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012), DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012) (2012). doi : 10.46298/dmtcs.3055. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3055/

Cité par Sources :