1 Acyclic Birkhoff Polytope

By Liliana Costa, C.M. da Fonseca and Enide Andrade Martins.

A real square matrix with nonnegative entries and all rows and columns sums equal to one is said to be doubly stochastic. This denomination is associated to probability distributions and it is amazing the diversity of branches of mathematics in which doubly stochastic matrices arise (geometry, combinatorics, optimization theory, graph theory and statistics). Doubly stochastic matrices have been studied quite extensively, especially in their relation with the van der Waerden conjecture for the permanent. In 1946, Birkhoff published a remarkable result asserting that a matrix in the polytope of n × n nonnegative doubly stochastic matrices, Ω_{n} , is a vertex if and only if it is a permutation matrix . In fact, Ω_{n} is the convex hull of all permutation matrices of order n. The Birkhoff polytope Ω_{n} is also known as transportation polytope or doubly stochastic matrices polytope. Recently Dahl discussed the subclass of Ω_{n} consisting of the tridiagonal doubly stochastic matrices and the corresponding subpolytope

Ω_{n}^{t} = {A ∈ Ω_{n} : A is tridiagonal},

the so-called tridiagonal Birkhoff polytope, and studied the facial structure of Ω_{n}^{t}. In this talk we present an interpretation of vertices and edges of the acyclic Birkhoff polytope, 𝔗_{n} = Ω_{n}(T), where T is a given tree, in terms of graph theory.