Triangulations of Cayley and Tutte polytopes

Details Triangulations of Cayley and Tutte polytopes Triangulations of Cayley and Tutte polytopes

2011-08-09

arxiv.org/abs/1108.1905v1

Mathematics

Combinatorics

32 pages, 11 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Triangulations of Cayley and Tutte polytopes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Triangulations of Cayley and Tutte polytopes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Triangulations of Cayley and Tutte polytopes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-70159