ALGEBRAIC COMBINATORICS

A property of the Birkhoff polytope
Algebraic Combinatorics, Volume 1 (2018) no. 2, p. 275-281
The Birkhoff polytope B n is the convex hull of all n×n permutation matrices in ℝ n×n . We compute the combinatorial symmetry group of the Birkhoff polytope.A representation polytope is the convex hull of some finite matrix group G≤GL(d,ℝ). We show that the group of permutation matrices is essentially the only finite matrix group which yields a representation polytope with the same face lattice as the Birkhoff polytope.
Received : 2017-09-20
Revised : 2017-10-12
Accepted : 2017-10-12
Published online : 2018-03-02
DOI : https://doi.org/10.5802/alco.6
Classification:  52B15,  05E18,  20B25,  20C15,  52B05,  52B12
Keywords: Birkhoff polytope, representation polytope, permutation polytope, combinatorial symmetry 
@article{ALCO_2018__1_2_275_0,
     author = {Baumeister, Barbara and Ladisch, Frieder},
     title = {A property of the Birkhoff polytope},
     journal = {Algebraic Combinatorics},
     publisher = {MathOA foundation},
     volume = {1},
     number = {2},
     year = {2018},
     pages = {275-281},
     doi = {10.5802/alco.6},
     zbl = {06882342},
     mrnumber = {3856525},
     language = {en},
     url = {https://alco.centre-mersenne.org/item/ALCO_2018__1_2_275_0}
}

Baumeister, Barbara; Ladisch, Frieder. A property of the Birkhoff polytope. Algebraic Combinatorics, Volume 1 (2018) no. 2, pp. 275-281. doi : 10.5802/alco.6. https://alco.centre-mersenne.org/item/ALCO_2018__1_2_275_0/

[1] Baumeister, Barbara; Grüninger, Matthias On Permutation Polytopes: Notions of Equivalence, J. Algebraic Combin., Volume 41 (2015) no. 4, pp. 1103-1114 | Article | MR 3342715 | Zbl 1322.52010

[2] Baumeister, Barbara; Haase, Christian; Nill, Benjamin; Paffenholz, Andreas On Permutation Polytopes, Adv. Math., Volume 222 (2009) no. 2, pp. 431-452 | Article | MR 2538016 | Zbl 1185.52006

[3] Baumeister, Barbara; Haase, Christian; Nill, Benjamin; Paffenholz, Andreas Permutation Polytopes of Cyclic Groups (2011), 15 pages (preprint, https://arxiv.org/abs/1109.0191v1) | MR 2538016 | Zbl 1185.52006

[4] Chermak, Andrew; Delgado, Alberto A Measuring Argument for Finite Groups, Proc. Amer. Math. Soc., Volume 107 (1989) no. 4, pp. 907-914 | Article | MR 994774 | Zbl 0687.20022

[5] Friese, Erik; Ladisch, Frieder Affine Symmetries of Orbit Polytopes, Adv. Math., Volume 288 (2016), pp. 386-425 | Article | MR 3436389 | Zbl 1330.52017

[6] Guralnick, Robert M.; Perkinson, David Permutation Polytopes and Indecomposable Elements in Permutation Groups, J. Combin. Theory Ser. A, Volume 113 (2006) no. 7, pp. 1243-1256 | Article | MR 2259059 | Zbl 1108.52014

[7] Isaacs, I. Martin Finite Group Theory, American Mathematical Society, Providence, RI, Graduate Studies in Mathematics (2008) no. 92, xii+350 pages | Article | MR 2426855 | Zbl 1169.20001

[8] Li, Chi-Kwong; Spitkovsky, Ilya; Zobin, Nahum Finite Reflection Groups and Linear Preserver Problems, Rocky Mountain J. Math., Volume 34 (2004) no. 1, pp. 225-251 | Article | MR 2061128 | Zbl 1060.15007

[9] Li, Chi-Kwong; Tam, Bit-Shun; Tsing, Nam-Kiu Linear Maps Preserving Permutation and Stochastic Matrices, Linear Algebra Appl., Volume 341 (2002), pp. 5-22 | Article | MR 1873605 | Zbl 0998.15004

[10] Lovász, László; Plummer, Michael D. Matching Theory, North-Holland, North-Holland Mathematics Studies (1986) no. 121, xxvii+544 pages (Annals of Discrete Mathematics 29) | MR 859549 | Zbl 0618.05001