Four questions on Birkhoff polytopes (Q1977733): Difference between revisions

In this article, the author asks four questions about the Birkhoff polytopes. The Birkhoff polytope \(P_n\) is the \((n-1)^2\) dimensional polytope consisting of all \(n\) by \(n\) matrices whose entries are non-negative and whose rows and columns all sum to \(1\). The author addresses the question of the volume of \(P_n\), proving that it has the same volume as a different polytope. He also shows that the simplex method runs in exponential time in \(n\) in the worst case, but in polynomial time in the average case. He also shows that (certain) random walks mix fast on \(P_n\), and shows that this is not true of the prism whose top and bottom are \(P_n\).