$c$-Birkhoff polytopes

Banaian, Esther; Chepuri, Sunita; Gunawan, Emily; Pan, Jianping

doi:10.5802/alco.472

Banaian, Esther ¹; Chepuri, Sunita ²; Gunawan, Emily ³; Pan, Jianping ⁴

¹Dept. of Mathematics, University of California, Riverside, Riverside, CA (USA)
²Dept. of Mathematics and Computer Science, University of Puget Sound, Tacoma, WA (USA)
³Dept. of Mathematics and Statistics, University of Massachusetts Lowell, Lowell, MA (USA)
⁴School of Mathematical and Statistical Sciences, Arizona State University, Tempe, AZ (USA)

Algebraic Combinatorics, Volume 9 (2026) no. 1, pp. 183-230

Abstract

In a 2018 paper, Davis and Sagan studied several pattern-avoiding polytopes. They found that a particular pattern-avoiding Birkhoff polytope had the same normalized volume as the order polytope of a certain poset, leading them to ask if the two polytopes were unimodularly equivalent. Motivated by Davis and Sagan’s question, in this paper we define a pattern-avoiding Birkhoff polytope called a $c$-Birkhoff polytope for each Coxeter element $c$ of the symmetric group. We then show that the $c$-Birkhoff polytope is unimodularly equivalent to the order polytope of the heap poset of the $c$-sorting word of the longest permutation. When $c=s_1s_2\dots s_{n}$, this result recovers an affirmative answer to Davis and Sagan’s question. Another consequence of this result is that the normalized volume of the $c$-Birkhoff polytope is the number of the longest chains in the (type A) $c$-Cambrian lattice.

Received: 2025-05-29
Revised: 2025-11-07
Accepted: 2025-12-02
Published online: 2026-03-03

DOI: 10.5802/alco.472

Classification: 52B20, 05A05, 06A07
Keywords: Birkhoff polytope, order polytope, heap, Cambrian lattice, c-singleton

Author's affiliations:

Banaian, Esther ¹ ; Chepuri, Sunita ² ; Gunawan, Emily ³ ; Pan, Jianping ⁴

¹ Dept. of Mathematics, University of California, Riverside, Riverside, CA (USA)
² Dept. of Mathematics and Computer Science, University of Puget Sound, Tacoma, WA (USA)
³ Dept. of Mathematics and Statistics, University of Massachusetts Lowell, Lowell, MA (USA)
⁴ School of Mathematical and Statistical Sciences, Arizona State University, Tempe, AZ (USA)

License:

CC-BY 4.0

Copyrights: The authors retain unrestricted copyrights and publishing rights

@article{ALCO_2026__9_1_183_0,
     author = {Banaian, Esther and Chepuri, Sunita and Gunawan, Emily and Pan, Jianping},
     title = {$c${-Birkhoff} polytopes},
     journal = {Algebraic Combinatorics},
     pages = {183--230},
     year = {2026},
     publisher = {The Combinatorics Consortium},
     volume = {9},
     number = {1},
     doi = {10.5802/alco.472},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.472/}
}

TY  - JOUR
AU  - Banaian, Esther
AU  - Chepuri, Sunita
AU  - Gunawan, Emily
AU  - Pan, Jianping
TI  - $c$-Birkhoff polytopes
JO  - Algebraic Combinatorics
PY  - 2026
SP  - 183
EP  - 230
VL  - 9
IS  - 1
PB  - The Combinatorics Consortium
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.472/
DO  - 10.5802/alco.472
LA  - en
ID  - ALCO_2026__9_1_183_0
ER  -

%0 Journal Article
%A Banaian, Esther
%A Chepuri, Sunita
%A Gunawan, Emily
%A Pan, Jianping
%T $c$-Birkhoff polytopes
%J Algebraic Combinatorics
%D 2026
%P 183-230
%V 9
%N 1
%I The Combinatorics Consortium
%U https://alco.centre-mersenne.org/articles/10.5802/alco.472/
%R 10.5802/alco.472
%G en
%F ALCO_2026__9_1_183_0

Banaian, Esther; Chepuri, Sunita; Gunawan, Emily; Pan, Jianping. $c$-Birkhoff polytopes. Algebraic Combinatorics, Volume 9 (2026) no. 1, pp. 183-230. doi: 10.5802/alco.472

References
Cited by

[1] Amiot, Claire; Iyama, Osamu; Reiten, Idun; Todorov, Gordana Preprojective algebras and $c$ -sortable words, Proc. Lond. Math. Soc. (3), Volume 104 (2012) no. 3, pp. 513-539 | DOI | MR | Zbl

[2] Assem, Ibrahim; Simson, Daniel; Skowroński, Andrzej Elements of the representation theory of associative algebras. Vol. 1, London Mathematical Society Student Texts, 65, Cambridge University Press, Cambridge, 2006, x+458 pages | DOI | MR | Zbl

[3] Athanasiadis, Christos A. Ehrhart polynomials, simplicial polytopes, magic squares and a conjecture of Stanley, J. Reine Angew. Math., Volume 583 (2005), pp. 163-174 | DOI | MR | Zbl

[4] Banaian, Esther; Chepuri, Sunita; Gunawan, Emily; Pan, Jianping Pattern-avoiding polytopes and Cambrian lattices, Sém. Lothar. Combin., Volume 91B (2024), Paper no. 77, 12 pages | MR

[5] Bapat, Ravindra B.; Raghavan, T. E. S. Nonnegative matrices and applications, Encyclopedia of Mathematics and its Applications, 64, Cambridge University Press, Cambridge, 1997, xiv+336 pages | DOI | MR | Zbl

[6] Barnard, Emily; Gunawan, Emily; Meehan, Emily; Schiffler, Ralf Cambrian combinatorics on quiver representations (type $𝔸$ ), Adv. in Appl. Math., Volume 143 (2023), Paper no. 102428, 37 pages | DOI | MR | Zbl

[7] Barvinok, Alexander; Stephen, Tamon The distribution of values in the quadratic assignment problem, Math. Oper. Res., Volume 28 (2003) no. 1, pp. 64-91 | DOI | MR | Zbl

[8] Baumeister, Barbara; Haase, Christian; Nill, Benjamin; Paffenholz, Andreas On permutation polytopes, Adv. Math., Volume 222 (2009) no. 2, pp. 431-452 | DOI | MR | Zbl

[9] Beck, Matthias; Pixton, Dennis The Ehrhart polynomial of the Birkhoff polytope, Discrete Comput. Geom., Volume 30 (2003) no. 4, pp. 623-637 | DOI | MR | Zbl

[10] Bédard, Robert On commutation classes of reduced words in Weyl groups, European J. Combin., Volume 20 (1999) no. 6, pp. 483-505 | DOI | MR | Zbl

[11] Billera, Louis J.; Sarangarajan, A. All $0$ - $1$ polytopes are traveling salesman polytopes, Combinatorica, Volume 16 (1996) no. 2, pp. 175-188 | DOI | MR | Zbl

[12] Birkhoff, Garrett Three observations on linear algebra, Univ. Nac. Tacuman, Rev. Ser. A, Volume 5 (1946), pp. 147-151 | Zbl | MR

[13] Björner, Anders; Brenti, Francesco Combinatorics of Coxeter groups, Graduate Texts in Mathematics, 231, Springer, New York, 2005, xiv+363 pages | MR | Zbl

[14] Brualdi, Richard A.; Cao, Lei 123-avoiding doubly stochastic matrices, Linear Algebra Appl., Volume 697 (2024), pp. 49-81 | DOI | MR | Zbl

[15] Brüstle, Thomas; Dupont, Grégoire; Pérotin, Matthieu On maximal green sequences, Int. Math. Res. Not. IMRN, Volume 2014 (2014) no. 16, pp. 4547-4586 | DOI | MR | Zbl

[16] Burggraf, Katherine; De Loera, Jesús; Omar, Mohamed On volumes of permutation polytopes, Discrete geometry and optimization (Fields Inst. Commun.), Volume 69, Springer, New York, 2013, pp. 55-77 | DOI | MR | Zbl

[17] Chan, Clara S.; Robbins, David P. On the volume of the polytope of doubly stochastic matrices, Experiment. Math., Volume 8 (1999) no. 3, pp. 291-300 | MR | Zbl | DOI

[18] Chapoton, Frédéric; Fomin, Sergey; Zelevinsky, Andrei Polytopal realizations of generalized associahedra, Canad. Math. Bull., Volume 45 (2002) no. 4, pp. 537-566 | DOI | MR | Zbl

[19] Davis, Robert; Sagan, Bruce Pattern-avoiding polytopes, European J. Combin., Volume 74 (2018), pp. 48-84 | DOI | MR | Zbl

[20] De Loera, Jesús A.; Liu, Fu; Yoshida, Ruriko A generating function for all semi-magic squares and the volume of the Birkhoff polytope, J. Algebraic Combin., Volume 30 (2009) no. 1, pp. 113-139 | DOI | MR | Zbl

[21] Defant, Colin; Li, Rupert Ungarian Markov chains, Electron. J. Probab., Volume 28 (2023), Paper no. 1, 39 pages | DOI | MR | Zbl

[22] Demonet, Laurent; Iyama, Osamu; Reading, Nathan; Reiten, Idun; Thomas, Hugh Lattice theory of torsion classes: beyond $τ$ -tilting theory, Trans. Amer. Math. Soc. Ser. B, Volume 10 (2023), pp. 542-612 | DOI | MR | Zbl

[23] Dequêne, Benjamin; Frieden, Gabriel; Iraci, Alessandro; Schreier-Aigner, Florian; Thomas, Hugh; Williams, Nathan Charmed roots and the Kroweras complement, J. Lond. Math. Soc. (2), Volume 110 (2024) no. 5, Paper no. e70025, 32 pages | DOI | MR | Zbl

[24] Developers, The Sage SageMath, the Sage Mathematics Software System (Version 10.6) (2025) (https://www.sagemath.org)

[25] Diaconis, Persi; Eriksson, Nicholas Markov bases for noncommutative Fourier analysis of ranked data, J. Symbolic Comput., Volume 41 (2006) no. 2, pp. 182-195 | DOI | MR | Zbl

[26] Fiedler, Miroslav Doubly stochastic matrices and optimization, Advances in mathematical optimization (Math. Res.), Volume 45, Akademie-Verlag, Berlin, 1988, pp. 44-51 | MR | Zbl | DOI

[27] Fishburn, Peter Acyclic sets of linear orders, Soc. Choice Welf., Volume 14 (1997) no. 1, pp. 113-124 | DOI | MR | Zbl

[28] Fishel, Susanna; Nelson, Luke Chains of maximum length in the Tamari lattice, Proc. Amer. Math. Soc., Volume 142 (2014) no. 10, pp. 3343-3353 | DOI | MR | Zbl

[29] Fomin, Sergey; Zelevinsky, Andrei Cluster algebras. I. Foundations, J. Amer. Math. Soc., Volume 15 (2002) no. 2, pp. 497-529 | DOI | MR | Zbl

[30] Galambos, Ádám; Reiner, Victor Acyclic sets of linear orders via the Bruhat orders, Soc. Choice Welf., Volume 30 (2008) no. 2, pp. 245-264 | DOI | MR | Zbl

[31] Garver, Alexander; Musiker, Gregg On maximal green sequences for type $𝔸$ quivers, J. Algebraic Combin., Volume 45 (2017) no. 2, pp. 553-599 | DOI | MR | Zbl

[32] Gyoda, Yasuaki Lattice structure in cluster algebra of finite type and non-simply-laced Ingalls–Thomas bijection (2024) | arXiv

[33] Hohlweg, Christophe; Lange, Carsten E. M. C.; Thomas, Hugh Permutahedra and generalized associahedra, Adv. Math., Volume 226 (2011) no. 1, pp. 608-640 | DOI | MR | Zbl

[34] Ingalls, Colin; Thomas, Hugh Noncrossing partitions and representations of quivers, Compos. Math., Volume 145 (2009) no. 6, pp. 1533-1562 | DOI | MR | Zbl

[35] Labbé, Jean-Philippe; Lange, Carsten E. M. C. Cambrian acyclic domains: counting $c$ -singletons, Order, Volume 37 (2020) no. 3, pp. 571-603 | DOI | MR | Zbl

[36] Liu, Ricky I.; Mészáros, Karola; St. Dizier, Avery Gelfand-Tsetlin polytopes: a story of flow and order polytopes, SIAM J. Discrete Math., Volume 33 (2019) no. 4, pp. 2394-2415 | DOI | MR | Zbl

[37] Mészáros, Karola; Morales, Alejandro H.; Striker, Jessica On flow polytopes, order polytopes, and certain faces of the alternating sign matrix polytope, Discrete Comput. Geom., Volume 62 (2019) no. 1, pp. 128-163 | DOI | MR | Zbl

[38] Muller, Greg The existence of a maximal green sequence is not invariant under quiver mutation, Electron. J. Combin., Volume 23 (2016) no. 2, Paper no. 2.47, 23 pages | DOI | MR | Zbl

[39] OEIS Foundation Inc. (2025) The On-Line Encyclopedia of Integer Sequences (Published electronically at http://oeis.org)

[40] Onn, Shmuel Geometry, complexity, and combinatorics of permutation polytopes, J. Combin. Theory Ser. A, Volume 64 (1993) no. 1, pp. 31-49 | DOI | MR | Zbl

[41] Paffenholz, Andreas Faces of Birkhoff polytopes, Electron. J. Combin., Volume 22 (2015) no. 1, Paper no. 1.67, 36 pages | DOI | MR | Zbl

[42] Pak, Igor Four questions on Birkhoff polytope, Ann. Comb., Volume 4 (2000) no. 1, pp. 83-90 | DOI | MR | Zbl

[43] Perrone, Elisa; Solus, Liam; Uhler, Caroline Geometry of discrete copulas, J. Multivariate Anal., Volume 172 (2019), pp. 162-179 | DOI | MR | Zbl

[44] Reading, Nathan Cambrian lattices, Adv. Math., Volume 205 (2006) no. 2, pp. 313-353 | DOI | MR | Zbl

[45] Reading, Nathan Clusters, Coxeter-sortable elements and noncrossing partitions, Trans. Amer. Math. Soc., Volume 359 (2007) no. 12, pp. 5931-5958 | DOI | MR | Zbl

[46] Reading, Nathan Sortable elements and Cambrian lattices, Algebra Universalis, Volume 56 (2007) no. 3-4, pp. 411-437 | DOI | MR | Zbl

[47] Reading, Nathan From the Tamari lattice to Cambrian lattices and beyond, Associahedra, Tamari lattices and related structures (Prog. Math. Phys.), Volume 299, Birkhäuser/Springer, Basel, 2012, pp. 293-322 | DOI | MR | Zbl

[48] Reading, Nathan; Speyer, David E. Cambrian fans, J. Eur. Math. Soc. (JEMS), Volume 11 (2009) no. 2, pp. 407-447 | DOI | MR | Zbl

[49] Schiffler, Ralf Quiver representations, CMS Books in Mathematics/ Ouvrages de Mathématiques de la SMC, Springer, Cham, 2014, xii+230 pages | DOI | MR | Zbl

[50] Simion, Rodica; Schmidt, Frank W. Restricted permutations, European J. Combin., Volume 6 (1985) no. 4, pp. 383-406 | DOI | MR | Zbl

[51] Stanley, Richard P. Two poset polytopes, Discrete Comput. Geom., Volume 1 (1986) no. 1, pp. 9-23 | DOI | MR | Zbl

[52] Stanley, Richard P. Enumerative combinatorics. Volume 1, Cambridge Studies in Advanced Mathematics, 49, Cambridge University Press, Cambridge, 2012, xiv+626 pages | MR | Zbl

[53] Stembridge, John R. On the fully commutative elements of Coxeter groups, J. Algebraic Combin., Volume 5 (1996) no. 4, pp. 353-385 | DOI | MR | Zbl

[54] Stump, Christian; Thomas, Hugh; Williams, Nathan Cataland: why the Fuß?, Mem. Amer. Math. Soc., Volume 305 (2025) no. 1535, p. vii+143 | DOI | MR | Zbl

[55] Thomas, Hugh An analogue of distributivity for ungraded lattices, Order, Volume 23 (2006) no. 2-3, pp. 249-269 | DOI | MR | Zbl

[56] Viennot, Gérard Xavier Heaps of pieces. I. Basic definitions and combinatorial lemmas, Combinatoire énumérative (Montreal, Que., 1985/Quebec, Que., 1985) (Lecture Notes in Math.), Volume 1234, Springer, Berlin, 1986, pp. 321-350 | DOI | MR

[57] Ziegler, Günter M. Lectures on polytopes, Graduate Texts in Mathematics, 152, Springer-Verlag, New York, 1995, x+370 pages | DOI | MR

Cited by Sources: