<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 4 Issue 1" %>
Four Questions on Birkhoff Polytope
Igor Pak
Department of Mathematics, Yale University, New Haven, CT 06520, USA
Annals of Combinatorics 4 (1) p.83-90 March, 2000
AMS Subject Classification: 52B05
We ask several questions on the structure of the polytope Pn of doubly stochastic n×n matrices, known as a Birkhoff polytope. We discuss the volume of Pn, the work of the simplex method, and the mixing of random walks on Pn.
Keywords: Birkhoff polytope, simplex method, random walk, symmetric group, mixing time


1. D. Aldous, Random walks on finite groups and rapidly mixing Markov chains , Lecture Notes in Mathematics, Vol. 986, Springer-Verlag, 1983.

2. D. Aldous and J. Fill, Reversible Markov Chains and Random Walks on Graphs , in preparation.

3. L. Babai, Automorphism groups , isomorphism , reconstruction , In: Handbook of Combinatorics, R.L. Graham, M. Groetschel, and L. Lovasz, Eds., Elsevier, 1996.

4. A. Berenstein and A.N. Kirillov, Groups generated by involutions , Gelfand¨DTsetlin patterns , and combinatorics of Young tableaux , Algera i Analiz 7 (1995) 92-152, in Russian.

5. C.S. Chan and D.P. Robbins, On the volume of the polytope of doubly stochastic matrices , Experiment. Math. 8 (1999) 291-300.

6. F.R.K. Chung, Spectral Graph Theory , Regional Conference Series in Mathematics, No. 92, American Mathematical Society, Providence, RI, 1997.

7. P. Diaconis, Group Representations in Probability and Statistics , IMS, Hayward, California, 1988.

8. P. Diaconis and A. Gangolli, Rectangular arrays with fixed margins , IMA, Vol. 72, Springer- Verlag, 1995, pp. 15-41.

9. P. Diaconis and M. Shahshahani, Generating a random permutation with random transpositions, Z. Wahr. verw. Gebiete 57 (1981) 159-179.

10. V.A. Emelichev, M.M. Kovalev, and M.K. Kravtsov, Polytopes , Graphs, Optimization, Nauka, Moscow, 1981.

11. S. Fomin and N. Lulov, On the number of rim hook tableaux , J. Zap. Nauch. Sem. POMI 223 (1995) 219-226.

12. E. Gansner, Matrix correspondences of plane partition , Pacific J. Math. 92 (1981) 295-315.

13. E. Gansner, The Hillman¨DGrassl correspondence and the enumeration of reverse plane partitions , J. Combin. Theory, Ser. A 30 (1981) 71-89.

14. D. Knuth, Permutations , matrices and generalized Young tableaux , Pacific J. Math. 34 (1970) 709-727.

15. N. Lulov, Random walks on groups , Ph.D. Thesis, Harvard University, 1996.

16. I.G. Macdonald, Symmetric Functions and Hall Polynomials , Oxford University Press, 2nd Edition, 1995.

17. M. Mihail, On the expansion of combinatorial polytopes , In: Proc. Mathematical Foundations of Computer Science, Prague, 1992, Lecture Notes in Comp. Sci., Vol. 629, Springer- Verlag, Berlin, 1992, pp. 37-49.

18. J. Mount, Application of Convex Sampling to Optimization and Contingency Table Generation/ Counting , Ph.D. Thesis, CMU, 1995.

19. A. Odlyzko, Asymptotic enumeration methods , In: Handbook of Combinatorics, Vol. 2, R.L. Graham, M. Groetschel, and L. Lovasz, Eds., Elsevier, 1996.

20. I. Pak, Random walks on groups : Strong uniform time approach , Ph.D. Thesis, Harvard University, 1997.

21. I. Pak, When and how n choose k , In: Randomization Methods in Algorithmic Design, P. Pardalos et al., Eds., A.M.S. DIMACS Series, Vol. 43, Providence, RI, 1998.

22. I. Pak and A. Postnikov, Oscillating tableaux and generalized RSK correspondence , In: Proc. of Eighth FPSAC Conference, UMN, Minneapolis, 1996.

23. B. Sagan, The Symmetric Group , Wadsworth, Pacific Grove, CA, 1991.

24. A. Schrijer, Theory of Integer and Linear Programming , John Wiley, New York, 1988.

25. R. Stanley, Combinatorics and Commutative Algebra , Birkhäouser, Boston, 1996.

26. R. Stanley, Decompositions of rational convex polytopes , Ann. Discrete Math. 6 (1980) 333-342.

27. B. Sturmfels, Equations defining toric varieties , AMS Proceedings of Symposia in Pure Mathematics, Vol. 62, American Mathematical Society, Providence, RI, 1998, pp. 447-449.

28. G. Ziegler, Lectures on Polytopes , Graduate Texts in Mathematics, Vol. 152, Springer- Verlag, New York, 1995.