pith. sign in

arxiv: 2504.07505 · v3 · submitted 2025-04-10 · 🧮 math.CO

c-Birkhoff polytopes

Esther Banaian , Sunita Chepuri , Emily Gunawan , Jianping Pan This is my paper

Pith reviewed 2026-05-22 20:55 UTC · model grok-4.3

classification 🧮 math.CO
keywords c-Birkhoff polytopepattern-avoiding polytopesheap posetorder polytopeCambrian latticeCoxeter elementunimodular equivalencesorting word
0
0 comments X

The pith

For any Coxeter element c the c-Birkhoff polytope is unimodularly equivalent to the order polytope of the heap poset of the c-sorting word of the longest permutation.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper defines a family of pattern-avoiding Birkhoff polytopes, one for each Coxeter element c of the symmetric group, called c-Birkhoff polytopes. It proves that each such polytope is unimodularly equivalent to the order polytope of the heap poset constructed from the c-sorting word of the longest permutation. The result recovers an affirmative answer to a question of Davis and Sagan for the special case c equal to the product of adjacent transpositions in order. It further shows that the normalized volume of the polytope equals the number of longest chains in the type A c-Cambrian lattice.

Core claim

For every Coxeter element c the c-Birkhoff polytope, obtained by imposing pattern-avoidance conditions derived from c, is unimodularly equivalent to the order polytope of the heap poset of the c-sorting word of the longest permutation in the symmetric group. When c is the standard product s1 s2 … sn the equivalence answers the question raised by Davis and Sagan; in general the normalized volume equals the number of longest chains in the associated c-Cambrian lattice.

What carries the argument

The heap poset of the c-sorting word of the longest permutation, whose order ideals encode the combinatorial type of the c-Birkhoff polytope under the claimed unimodular equivalence.

If this is right

  • The normalized volume of the c-Birkhoff polytope equals the number of longest chains in the type A c-Cambrian lattice.
  • When c equals s1 s2 … sn the result affirms the unimodular equivalence asked by Davis and Sagan.
  • The lattice points and faces of the c-Birkhoff polytope are in bijection with the order ideals of the heap poset.
  • The equivalence transfers enumeration and volume formulas from the Cambrian lattice to the pattern-avoiding polytope.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same heap-poset construction may produce geometric models for other pattern-avoiding polytopes outside the Birkhoff family.
  • Volume computations for these polytopes can now be performed by counting chains in Cambrian lattices rather than by direct polytope methods.
  • Analogous equivalences might exist when the symmetric group is replaced by other finite Coxeter groups.

Load-bearing premise

The pattern avoidance conditions that define the c-Birkhoff polytope produce a polytope whose faces and lattice points match exactly the order ideals of the heap poset built from the c-sorting word.

What would settle it

For a small n and a concrete Coxeter element c, compute the normalized volume or the number of vertices of the c-Birkhoff polytope and compare it with the same quantity for the order polytope of the corresponding heap poset; any mismatch disproves the equivalence.

Figures

Figures reproduced from arXiv: 2504.07505 by Emily Gunawan, Esther Banaian, Jianping Pan, Sunita Chepuri.

Figure 1
Figure 1. Figure 1: Left: Hasse diagram of the underlying poset of Heap([1214321432]). Right: the heap diagram of Heap([1214321432]), with each label j replaced by sj . π(x) < π(y). A labeled linear extension of the heap of a reduced word [a] = [a1 · · · aℓ ] is a word [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Left: The zero relations of Theorem 4.4 in the permutation matrix of a c-singleton for c = [1432657]. Right: The permutation matrix for s1s4s3s2, a c-singleton for this c. Let υc denote the cardinality of the upper-barred numbers in [2, n+1 2 ]. We define νc : [1, n + 1] → [−υc, n − υc] as the bijection given in the table below. i uυc uυc−1 . . . u1 d0 d1 . . . dr dr+1 us us−1 . . . uυc+1 νc(i) −υc 1 − υc … view at source ↗
Figure 3
Figure 3. Figure 3: Left: We depict the projection Πc for c = [1432657]. We also place red X’s in the entries which are guaranteed to be zero by Theorem 4.4. Right: We draw the permutation matrix for s1s4s3s2 and circle the entries which are recorded by Πc. Proposition 5.5. For each upper-barred integer u and each k ≤ µ(u), the entry (n + 2 − k, ck (u)) is strictly below the main diagonal. Proof. Suppose for sake of contradic… view at source ↗
Figure 4
Figure 4. Figure 4: Left: Algorithm for constructing the heap diagram for Hc = Heap(Rc) for c = [4321657] = (1 5 7 8 6 4 3 2) (equivalently, the lower-barred letters are 5, 7, and the upper-barred letters are 6, 4, 3, 2) in A7. Right: The heap diagram for Hc. Notice that by construction Rc is the “diagonal reading word” of Hc, that is, the linear extension of Hc formed by concatenating the diagonals of the diagram from left t… view at source ↗
Figure 5
Figure 5. Figure 5: Left: Heap of s1s2s3s4-sorting word of the longest element w0 in A4. Right: Heap of s1s2s3s4 . . . sn-sorting word of the longest element w0 in An. Remark 6.5. In light of Theorem 6.3, we can consider the poset isomorphism in Theorem 2.20 to be a poset isomorphism from the lattice of c-singletons onto J(Hc). By abuse of notation, from now on we write f(w) to mean an order ideal of Hc. Remark 6.6. We summar… view at source ↗
Figure 6
Figure 6. Figure 6: Accompanying figure for Theorem 6.11. Left: Hasse diagram of the underlying poset of Hc with the elements in f(b4) highlighted. Right: the heap diagram of Hc with the elements in f(b4) highlighted. Remark 6.12. In general, o(bi) is the vector with 1’s in the last i entries and 0’s everywhere else. Proposition 6.13. Let c be a Coxeter element of An. There exists a unique n+1 2  × [PITH_FULL_IMAGE:figures/… view at source ↗
Figure 7
Figure 7. Figure 7: We also compute the changes of the permutation matrix from u (3) to u (2). In this process we multiply u (3) on the right by [765]. This is demonstrated in [PITH_FULL_IMAGE:figures/full_fig_p028_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: On the left we have the permutation matrix associated to the reduced word u (3) and on the right we have the same for u (2), where c = [1432657] as in previous examples. Comparing these illustrates the main point of Lemma 6.20. Lemma 6.19. Let 1 ≤ k ≤ r + 1 and 1 ≤ j ≤ dk − 1. If i = j + Pk−1 a=1(da − 1), that is, if bi = d (k) j , then the n+1 2  − i + 1 th entry of the vector Πc(X(bi)) is 1, and all ea… view at source ↗
Figure 9
Figure 9. Figure 9: Heap of [21365487]-sorting word of the longest element w0 in A8, used in Examples 6.23, 6.26, 6.28, and 6.31 c-singletons w where 1 ̸∈ f(w). We then prove Theorem 6.21 by combining these cases with Theorem 6.13. Recall that Dx denotes the diagonal in Hc containing x, and Ax denotes the antidiagonal in Hc containing x. Notation 6.22. Suppose w is a c-singleton such that f(w) contains the poset element 1 in … view at source ↗
Figure 10
Figure 10. Figure 10: For c = [1234567] mark with red X’s the entries which are guaranteed to be zero by Theorem 4.4, and we show the projection Πc with (black) numbers. Proof. When y ≤ n+2 2 , the first statement follows from Lemma 4.10, so suppose y > n+2 2 . We can use the same argument as in part 1, case i of the proof of Lemma 4.10 to show we cannot have distinct values 1 ≤ a < b ≤ y such that w(a) ≡ w(b) (mod y) even whe… view at source ↗
Figure 11
Figure 11. Figure 11: Left: Heap of the [1357246]-sorting word of the longest element w0 in A7. Right: Heap of the [13572468]-sorting word of the longest element w0 in A8. 28 X 25 X 20 X 13 X 26 X 21 7 14 27 X 22 8 15 3 23 9 16 24 10 17 4 X 11 18 5 1 X X 19 2 X 6 X 12 X 36 X 33 X 28 X 21 13 X 34 X 29 X 22 14 35 X 30 7 23 15 X 31 8 24 16 32 9 25 17 3 10 26 18 4 X X 27 19 5 1 11 X X 20 2 X 6 X 12 X X Now, we calculate some examp… view at source ↗
Figure 12
Figure 12. Figure 12: Heap of [2123243212], a reduced word for the longest element w0 in A4 On the other hand, consider the subpolytope B of the Birkhoff polytope in A4 defined by taking the convex hull of the permutations corresponding to the order ideals of H. In contrast to O(H), the dimension of B is at most 9. To see this, first we list the twelve permutations [PITH_FULL_IMAGE:figures/full_fig_p041_12.png] view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The paper defines the c-Birkhoff polytope for each Coxeter element c of S_n as the convex hull of the permutation matrices avoiding a c-dependent collection of patterns. It proves that this polytope is unimodularly equivalent to the order polytope of the heap poset of the c-sorting word of the longest element w_0. The result recovers an affirmative answer to a 2018 question of Davis and Sagan for the case c = s_1 s_2 … s_n and implies that the normalized volume equals the number of longest chains in the type-A c-Cambrian lattice.

Significance. The equivalence supplies a combinatorial model linking pattern-avoiding permutation matrices to heap posets and Cambrian lattices, thereby giving an explicit count for the volumes of these polytopes. The argument employs standard Coxeter-theoretic constructions (c-sorting words and heaps) without introducing free parameters or post-hoc fitting, and the special case directly resolves the Davis–Sagan query.

major comments (1)
  1. [Section 4 (bijection argument)] The central claim rests on a bijection showing that a permutation matrix satisfies the c-pattern-avoidance condition if and only if its support corresponds to an order ideal in the heap poset H_c. The manuscript must verify that this correspondence holds for every Coxeter element c (not merely for the long cycle); a single mismatch would render the polytopes combinatorially inequivalent. The proof sketch in the relevant section should include an explicit check that the covering relations induced by the pattern-avoidance rule coincide with those of the heap poset.
minor comments (2)
  1. [Introduction and Section 2] The precise definition of the c-dependent pattern-avoidance condition should be stated in a single numbered definition early in the paper rather than distributed across the introduction and later sections.
  2. [Notation section] Notation for the c-sorting word and the associated heap poset should be fixed once and used consistently; minor variations in subscripting appear in the statements of the main theorems.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the positive evaluation and the recommendation of minor revision. The comment on the bijection argument is addressed point-by-point below.

read point-by-point responses

  1. Referee: [Section 4 (bijection argument)] The central claim rests on a bijection showing that a permutation matrix satisfies the c-pattern-avoidance condition if and only if its support corresponds to an order ideal in the heap poset H_c. The manuscript must verify that this correspondence holds for every Coxeter element c (not merely for the long cycle); a single mismatch would render the polytopes combinatorially inequivalent. The proof sketch in the relevant section should include an explicit check that the covering relations induced by the pattern-avoidance rule coincide with those of the heap poset.

    Authors: The argument in Section 4 is formulated for an arbitrary Coxeter element c, relying on the c-dependent definitions of the sorting word and the associated heap poset H_c. The bijection is obtained by matching the forbidden patterns (which are determined by the reduced word for c) with the covering relations in the heap. We acknowledge that the current exposition could benefit from a more explicit verification that the covering relations match for general c rather than relying primarily on the special case. We will revise the section to add a short lemma or paragraph that directly compares the covering relations coming from the pattern-avoidance conditions with those of the heap poset, using only the standard properties of heaps and c-sorting words. revision: yes

Circularity Check

0 steps flagged

No circularity: self-contained combinatorial equivalence proof

full rationale

The paper introduces the c-Birkhoff polytope by a new pattern-avoidance definition depending on a Coxeter element c, then proves unimodular equivalence to the order polytope of the associated heap poset by exhibiting a vertex bijection (permutation matrices satisfying the avoidance condition correspond exactly to order ideals). This is a direct, first-principles combinatorial argument from Coxeter theory and poset theory; it does not rely on fitted parameters, self-citations for load-bearing uniqueness theorems, or renaming of prior empirical results. The Davis-Sagan reference is external motivation only and is answered without circular reduction. The derivation chain is independent of its own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The claim depends on the new definition of the c-Birkhoff polytope together with background facts from Coxeter group theory and poset theory; no free parameters are apparent from the abstract.

axioms (1)
  • standard math Standard properties of Coxeter groups, reduced words, sorting words, and heap posets
    These are invoked to define the c-sorting word and the associated heap poset for the longest permutation.
invented entities (1)
  • c-Birkhoff polytope no independent evidence
    purpose: A pattern-avoiding Birkhoff polytope parameterized by a Coxeter element c
    Newly defined in this paper to study the equivalence with order polytopes.

pith-pipeline@v0.9.0 · 5724 in / 1485 out tokens · 55193 ms · 2026-05-22T20:55:01.340560+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

14 extracted references · 14 canonical work pages

  1. [1]

    Preprojective algebras and c-sortable words

    [Ami+12] Claire Amiot, Osamu Iyama, Idun Reiten, and Gordana Todorov. “Preprojective algebras and c-sortable words”. In:Proc. Lond. Math. Soc. (3)104.3 (2012), pp. 513–539.doi: 10.1112/plms/pdr020. [ASS06] Ibrahim Assem, Daniel Simson, and Andrzej Skowro´ nski.Elements of the representation theory of associative algebras. Vol

    work page doi:10.1112/plms/pdr020 2012

  2. [2]

    Ehrhart polynomials, simplicial polytopes, magic squares and a conjecture of Stanley

    London Mathematical Society Student Texts. Techniques of representation theory. Cambridge University Press, Cambridge, 2006, pp. x+458.doi:10.1017/CBO9780511614309. [Ath05] Christos A. Athanasiadis. “Ehrhart polynomials, simplicial polytopes, magic squares and a conjecture of Stanley”. In:J. Reine Angew. Math.583 (2005), pp. 163–174.doi: 10.1515/crll.2005...

    work page doi:10.1017/cbo9780511614309 2006

  3. [3]

    Cambrian combi- natorics on quiver representations (type A)

    Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 1997, pp. xiv+336.doi:10.1017/CBO9780511529979. [Bar+23] Emily Barnard, Emily Gunawan, Emily Meehan, and Ralf Schiffler. “Cambrian combi- natorics on quiver representations (type A)”. In:Adv. in Appl. Math.143 (2023), Paper No. 102428, 37.doi:10.1016/j.aam.2022.102428...

    work page doi:10.1017/cbo9780511529979 1997

  4. [4]

    123-avoiding doubly stochastic matrices

    Graduate Texts in Mathematics. Springer, New York, 2005, pp. xiv+363. [BC24] Richard A. Brualdi and Lei Cao. “123-avoiding doubly stochastic matrices”. In:Linear Algebra Appl.697 (2024), pp. 49–81.doi:10.1016/j.laa.2023.07.021. [BDP14] Thomas Br¨ ustle, Gr´ egoire Dupont, and Matthieu P´ erotin. “On maximal green sequences”. In:Int. Math. Res. Not. IMRN16...

    work page doi:10.1016/j.laa.2023.07.021 2005

  5. [5]

    On the volume of the polytope of doubly stochastic matrices

    Fields Inst. Commun. Springer, New York, 2013, pp. 55–77.doi:10.1007/978-3-319-00200-2\_5. [CR99] Clara S. Chan and David P. Robbins. “On the volume of the polytope of doubly stochastic matrices”. In:Experiment. Math.8.3 (1999), pp. 291–300. [CFZ02] Fr´ ed´ eric Chapoton, Sergey Fomin, and Andrei Zelevinsky. “Polytopal realizations of generalized associah...

    work page doi:10.1007/978-3-319-00200-2 2013

  6. [6]

    Pattern-avoiding polytopes

    Dedicated to Robert V. Moody. 2002, pp. 537– 566.doi:10.4153/CMB-2002-054-1. [DS18] Robert Davis and Bruce Sagan. “Pattern-avoiding polytopes”. In:European J. Combin. 74 (2018), pp. 48–84.doi:10.1016/j.ejc.2018.07.006. [DLY09] Jes´ us A. De Loera, Fu Liu, and Ruriko Yoshida. “A generating function for all semi- magic squares and the volume of the Birkhoff...

    work page doi:10.4153/cmb-2002-054-1 2002

  7. [7]

    Math. Res. Akademie-Verlag, Berlin, 1988, pp. 44–

    work page 1988

  8. [8]

    Acyclic sets of linear orders

    [Fis97] Peter Fishburn. “Acyclic sets of linear orders”. In:Soc. Choice Welf.14.1 (1997), pp. 113–124.doi:10.1007/s003550050055. [FN14] Susanna Fishel and Luke Nelson. “Chains of maximum length in the Tamari lattice”. In:Proc. Amer. Math. Soc.142.10 (2014), pp. 3343–3353.doi: 10.1090/S0002-9939- 2014-12069-7. [FZ02] Sergey Fomin and Andrei Zelevinsky. “Cl...

    work page doi:10.1007/s003550050055 1997

  9. [9]

    Transportation Research Part B: Methodological 46, 1159–1176

    arXiv:2211.08935v6 [math.RT]. [HLT11] Christophe Hohlweg, Carsten E. M. C. Lange, and Hugh Thomas. “Permutahedra and generalized associahedra”. In:Adv. Math.226.1 (2011), pp. 608–640.doi: 10.1016/j. aim.2010.07.005. [IT09] Colin Ingalls and Hugh Thomas. “Noncrossing partitions and representations of quivers”. In:Compos. Math.145.6 (2009), pp. 1533–1562.do...

    work page doi:10.1016/j 2011

  10. [10]

    Sortable elements and Cambrian lattices

    Prog. Math. Phys. Birkh¨ auser/Springer, Basel, 2012, pp. 293–322.doi: 10.1007/978-3-0348-0405-9_15 . [Rea07b] Nathan Reading. “Sortable elements and Cambrian lattices”. In:Algebra Universalis 56.3-4 (2007), pp. 411–437.doi:10.1007/s00012-007-2009-1. [RS09] Nathan Reading and David E. Speyer. “Cambrian fans”. In:J. Eur. Math. Soc. (JEMS) 11.2 (2009), pp. ...

    work page doi:10.1007/978-3-0348-0405-9_15 2012

  11. [11]

    Abu-Hashem, Mohammad Shehab, Qusai Shambour, and Riham Muqat.Nonvolatile Memory-Based Internet of Things: A Survey, pages 285–304

    [Sch14] Ralf Schiffler.Quiver representations. CMS Books in Mathematics/ Ouvrages de Math´ ematiques de la SMC. Springer, Cham, 2014, pp. xii+230.doi: 10.1007/978-3- 319-09204-1. [SS85] Rodica Simion and Frank W. Schmidt. “Restricted permutations”. In:European J. Combin.6.4 (1985), pp. 383–406.doi:10.1016/S0195-6698(85)80052-4. [Sta12] Richard P. Stanley....

    work page doi:10.1007/978-3- 2014

  12. [12]

    Two poset polytopes

    Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 2012, pp. xiv+626. [Sta86] Richard P. Stanley. “Two poset polytopes”. In:Discrete Comput. Geom.1.1 (1986), pp. 9–23.doi:10.1007/BF02187680. [Ste96] John R. Stembridge. “On the fully commutative elements of Coxeter groups”. In:J. Algebraic Combin.5.4 (1996), pp. 353–385.doi:1...

    work page doi:10.1007/bf02187680 2012

  13. [13]

    Springer, Berlin, 1986, pp

    Lecture Notes in Math. Springer, Berlin, 1986, pp. 321–350.doi: 10.1007/BFb0072524. [Zie95] G¨ unter M. Ziegler.Lectures on polytopes. Vol

    work page doi:10.1007/bfb0072524 1986

  14. [14]

    Springer-Verlag, New York, 1995, pp

    Graduate Texts in Mathematics. Springer-Verlag, New York, 1995, pp. x+370.doi:10.1007/978-1-4613-8431-1. 46 Department of Mathematics, University of California, Riverside, Riverside, CA (USA) Department of Mathematics and Computer Science, University of Puget Sound, Tacoma, W A (USA) Department of Mathematics and Statistics, University of Massachusetts Lo...

    work page doi:10.1007/978-1-4613-8431-1 1995