Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

Request Permissions   Purchase Content 


A positive Grassmannian analogue of the permutohedron

Author: Lauren K. Williams
Journal: Proc. Amer. Math. Soc. 144 (2016), 2419-2436
MSC (2010): Primary 05E99
Published electronically: October 22, 2015
MathSciNet review: 3477058
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The classical permutohedron $ \operatorname {Perm}_n$ is the convex hull of the points $ (w(1),\dots ,w(n))\in \mathbb{R}^n$ where $ w$ ranges over all permutations in the symmetric group $ S_n$. This polytope has many beautiful properties - for example it provides a way to visualize the weak Bruhat order: if we orient the permutohedron so that the longest permutation $ w_0$ is at the ``top'' and the identity $ e$ is at the ``bottom'', then the one-skeleton of $ \operatorname {Perm}_n$ is the Hasse diagram of the weak Bruhat order. Equivalently, the paths from $ e$ to $ w_0$ along the edges of $ \operatorname {Perm}_n$ are in bijection with the reduced decompositions of $ w_0$. Moreover, the two-dimensional faces of the permutohedron correspond to braid and commuting moves, which by the Tits Lemma, connect any two reduced expressions of $ w_0$.

In this note we introduce some polytopes $ \operatorname {Br}_{k,n}$ (which we call bridge polytopes) which provide a positive Grassmannian analogue of the permutohedron. In this setting, BCFW-bridge decompositions of reduced plabic graphs play the role of reduced decompositions. We define $ \operatorname {Br}_{k,n}$ and explain how paths along its edges encode BCFW-bridge decompositions of the longest element $ \pi _{k,n}$ in the circular Bruhat order. We also show that two-dimensional faces of $ \operatorname {Br}_{k,n}$ correspond to certain local moves for plabic graphs, which by a result of Postnikov, connect any two reduced plabic graphs associated to $ \pi _{k,n}$. All of these results can be generalized to the positive parts of Schubert cells. A useful tool in our proofs is the fact that our polytopes are isomorphic to certain Bruhat interval polytopes. Conversely, our results on bridge polytopes allow us to deduce some corollaries about the structure of Bruhat interval polytopes.

References [Enhancements On Off] (What's this?)

  • [AHBC$^12$] Nima Arkani-Hamed, Jacob L. Bourjaily, Freddy Cachazo, Alexander B. Goncharov, Alexander Postnikov, and Jaroslav Trnka,
    Scattering amplitudes and the positive Grassmannian, 2012.
    Preprint, arXiv:1212.5605.
  • [Bjö84] A. Björner, Posets, regular CW complexes and Bruhat order, European J. Combin. 5 (1984), no. 1, 7-16. MR 746039 (86e:06002),
  • [BLVS$^99$] Anders Björner, Michel Las Vergnas, Bernd Sturmfels, Neil White, and Günter M. Ziegler, Oriented matroids, 2nd ed., Encyclopedia of Mathematics and its Applications, vol. 46, Cambridge University Press, Cambridge, 1999. MR 1744046 (2000j:52016)
  • [BW82] Anders Björner and Michelle Wachs, Bruhat order of Coxeter groups and shellability, Adv. in Math. 43 (1982), no. 1, 87-100. MR 644668 (83i:20043),
  • [Ede81] Paul H. Edelman, The Bruhat order of the symmetric group is lexicographically shellable, Proc. Amer. Math. Soc. 82 (1981), no. 3, 355-358. MR 612718 (82j:06004),
  • [FS00] Sergey Fomin and Michael Shapiro, Stratified spaces formed by totally positive varieties, Michigan Math. J. 48 (2000), 253-270. Dedicated to William Fulton on the occasion of his 60th birthday. MR 1786489 (2001i:20095),
  • [Her14] Patricia Hersh, Regular cell complexes in total positivity, Invent. Math. 197 (2014), no. 1, 57-114. MR 3219515,
  • [KLS13] Allen Knutson, Thomas Lam, and David E. Speyer, Positroid varieties: juggling and geometry, Compos. Math. 149 (2013), no. 10, 1710-1752. MR 3123307,
  • [KW11] Yuji Kodama and Lauren K. Williams, KP solitons, total positivity, and cluster algebras, Proc. Natl. Acad. Sci. USA 108 (2011), no. 22, 8984-8989. MR 2813307 (2012f:37142),
  • [KW13] Y. Kodama and L. Williams,
    The full Kostant-Toda hierarchy on the positive flag variety, 2013.
    Preprint, arXiv:1308.5011, to appear in Comm. Math. Phys.
  • [Lus94] G. Lusztig, Total positivity in reductive groups, Lie theory and geometry, Progr. Math., vol. 123, Birkhäuser Boston, Boston, MA, 1994, pp. 531-568. MR 1327548 (96m:20071)
  • [Pos06] Alexander Postnikov,
    Total positivity, Grassmannians, and networks, 2006.
    Preprint, arXiv:math/0609764.
  • [Pro82] Robert A. Proctor, Classical Bruhat orders and lexicographic shellability, J. Algebra 77 (1982), no. 1, 104-126. MR 665167 (84j:20044),
  • [Rie99] Konstanze Rietsch, An algebraic cell decomposition of the nonnegative part of a flag variety, J. Algebra 213 (1999), no. 1, 144-154. MR 1674668 (2000e:14086),
  • [Sco06] Joshua S. Scott, Grassmannians and cluster algebras, Proc. London Math. Soc. (3) 92 (2006), no. 2, 345-380. MR 2205721 (2007e:14078),
  • [TW14] Emmanuel Tsukerman and Lauren Williams,
    Bruhat interval polytopes, 2014.
    Preprint, arXiv:1406.5202.
  • [Wil07] Lauren K. Williams, Shelling totally nonnegative flag varieties, J. Reine Angew. Math. 609 (2007), 1-21. MR 2350779 (2008m:14100),

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 05E99

Retrieve articles in all journals with MSC (2010): 05E99

Additional Information

Lauren K. Williams
Affiliation: Department of Mathematics, University of California, Berkeley, California 94720-3840

Received by editor(s): January 27, 2015
Received by editor(s) in revised form: July 13, 2015, July 25, 2015, and August 3, 2015
Published electronically: October 22, 2015
Additional Notes: The author was partially supported by an NSF CAREER award DMS-1049513, a grant from the Simons Foundation (#300841), and by the Fondation Sciences Mathématiques de Paris.
Communicated by: Patricia L. Hersh
Article copyright: © Copyright 2015 American Mathematical Society

American Mathematical Society