\documentclass[12pt]{article}

\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{amsfonts}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}{Corollary}[section]
\def\Z{\mathbb Z}
\def\CC{\mathbb C}
\def\rank{\hbox{\rm \ rank}}
\begin{document}
%Costa
%Liliana","lilianacosta@ua.pt","
\section{Acyclic Birkhoff Polytope} By {\sl Liliana Costa, C.M. da Fonseca and Enide Andrade Martins}.  

\medskip  \noindent 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\times n$ nonnegative doubly stochastic matrices, $\Omega _{n}$ , is a vertex if and only if it is a permutation matrix . In fact, $\Omega _{n}$ is the convex hull of all permutation matrices of order $n$.  The \emph{Birkhoff polytope} $\Omega _{n}$ is also known as \emph{ transportation polytope} or \emph{doubly stochastic matrices polytope}.  Recently Dahl discussed the subclass of $\Omega _{n}$ consisting of the tridiagonal doubly stochastic matrices and the corresponding subpolytope \[ \Omega _{n}^{t}=\{A\in \Omega _{n}:A\mbox{ is tridiagonal}\}, \] the so-called \textit{tridiagonal Birkhoff polytope}, and studied the facial structure of $\Omega _{n}^{t}.$  In this talk we present an interpretation of vertices and edges of the acyclic Birkhoff polytope, $\mathfrak{T}_{n}=\Omega _{n}(T)$, where $T$ is a given tree, in terms of graph theory.
%Doubly stochastic matrix; Birkhoff polytope; Number of vertices;Tree","05A15","15A51","","10:14:49","Sat Mar 29 2008","89.214.211.4"
\end{document}
 zzzz
