Tutte polytope

The Cayley polytope was defined recently as the convex hull of Cayley compositions, introduced by Cayley in 1857. In this talk, I will describe how we resolved Braun's conjecture, which expresses the volume of the Cayley polytope in terms of the number of connected graphs. We extend this result to a two-variable deformation, which we call the Tutte polytope. 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 Tuttepolytopes. We prove that simplices in the triangulations correspond to labeled trees. The heart of the proof is a direct bijection based onthe neighbors-first search graph traversal algorithm.

The slides from the talk are available here: DOWNLOAD SLIDES!