The skeleton of acyclic Birkhoff polytopes

Abstract

For a fixed tree T with n vertices the corresponding acyclic Birkhoff polytope Ωn(T)consists of doubly stochastic matrices having support in positions specified by T. This is a face of the Birkhoff polytope Ωn(which consists of all n ×n doubly stochastic matrices). The skeleton of Ωn(T) is the graph where vertices and edges correspond to those of Ωn(T), and we investigate some properties of this graph. In particular, we characterize adjacency of pairs of vertices, compute the minimum degree of a vertex and show some properties of the maximum degree of a vertex in the skeleton. We also determine the maximum degree for certain classes of trees, including paths, stars and caterpillars.