Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

Request Permissions   Purchase Content 
 
 

 

Diameter of graphs of reduced words and galleries


Authors: Victor Reiner and Yuval Roichman
Journal: Trans. Amer. Math. Soc. 365 (2013), 2779-2802
MSC (2010): Primary 20F55, 20F05
DOI: https://doi.org/10.1090/S0002-9947-2012-05719-9
Published electronically: November 26, 2012
MathSciNet review: 3020115
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: For finite reflection groups of types $ A$ and $ B$, we determine the diameter of the graph whose vertices are reduced words for the longest element and whose edges are braid relations. This is deduced from a more general theorem that applies to supersolvable hyperplane arrangements.


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

  • 1. D. Armstrong, The sorting order on a Coxeter group. J. Combin. Theory Ser. A 116 (2009), 1285-1305. MR 2568800 (2010m:20057)
  • 2. C.A. Athanasiadis and F. Santos, Monotone paths on zonotopes and oriented matroids. Canad. J. Math. 53 (2001), 1121-1140. MR 1863845 (2003a:52031)
  • 3. C.A. Athanasiadis, P.H. Edelman and V. Reiner, Monotone paths on polytopes. Math. Zeit. 235 (2000), 315-334. MR 1795510 (2002a:52011)
  • 4. M. Autord and P. Dehornoy, On the distance between the expressions of a permutation. arXiv:0902.3074. MR 2673022
  • 5. H. Barcelo and E. Ihrig, Lattices of parabolic subgroups in connection with hyperplane arrangements. J. Algebraic Combin. 9 (1999), no. 1, 5-24. MR 1676736 (2000g:52023)
  • 6. H.J. Baues, Geometry of loop spaces and the cobar construction. Mem. Amer. Math. Soc. 25, Amer. Math. Soc., Providence, RI, 1980. MR 567799 (81m:55010)
  • 7. L.J. Billera, M.M. Kapranov and B. Sturmfels, Cellular strings on polytopes. Proc. Amer. Math. Soc. 122 (1994), 549-555. MR 1205482 (95a:52020)
  • 8. L.J. Billera and B. Sturmfels, Fiber polytopes, Ann. of Math. (2) 135 (1992), 527-549. MR 1166643 (93e:52019)
  • 9. A. Björner, Essential chains and homotopy type of posets. Proc. Amer. Math. Soc. 116 (1992), 1179-1181. MR 1140664 (94b:06001)
  • 10. A. Björner and F. Brenti, Combinatorics of Coxeter groups. Graduate Texts in Mathematics, 231. Springer, New York, 2005. MR 2133266 (2006d:05001)
  • 11. A. Björner, P.H. Edelman, and G.M. Ziegler, Hyperplane arrangements with a lattice of regions. Discrete Comput. Geom. 5 (1990), 263-288. MR 1036875 (90k:51036)
  • 12. A. Björner, M. Las Vergnas, B. Sturmfels, N. White, and G.M. Ziegler, Oriented matroids. Encyclopedia of Mathematics and Its Applications 46. Cambridge University Press, Cambridge, 1993. MR 1226888 (95e:52023)
  • 13. R. Cordovil, Sur les matroïdes orientés de rang 3 et les arrangements de pseudodroites dans le plan projectif réel. Europ. J. Combin. 3 (1982), 307-318. MR 687729 (84j:05031)
  • 14. R. Cordovil and M.L. Moreira, A homotopy theorem on oriented matroids. Discrete Math. 111 (1993), 131-136. MR 1210090 (94d:52016)
  • 15. P. Deligne, Les immeubles des groupes de tresses généralisés. Invent. Math. 17 (1972), 273-302. MR 0422673 (54:10659)
  • 16. P.H. Edelman, A partial order on the regions of $ \mathbb{R}^n$ dissected by hyperplanes. Trans. Amer. Math. Soc. 283 (1984), 617-631. MR 737888 (85k:51030)
  • 17. S. Felsner and H. Weil, A theorem on higher Bruhat orders. Discrete Comput. Geom. 23 (2000), 121-127. MR 1727126 (2001e:52044)
  • 18. J.E. Humphreys, Reflection groups and Coxeter groups. Cambridge Studies in Advanced Mathematics. 29. Cambridge University Press, Cambridge, 1990. MR 1066460 (92h:20002)
  • 19. Yu.I. Manin and V.V. Schechtman, Arrangements of hyperplanes, higher braid groups and higher Bruhat orders. Algebraic number theory, 289-308, Adv. Stud. Pure Math. 17, Academic Press, Boston, MA, 1989. MR 1097620 (91m:32042)
  • 20. P. Orlik and H. Terao, Arrangements of hyperplanes. Grundlehren der Mathematischen Wissenschaften 300. Springer-Verlag, Berlin, 1992 MR 1217488 (94e:52014)
  • 21. J. Rambau, A suspension lemma for bounded posets. J. Combin. Theory Ser. A 80 (1997), 374-379. MR 1485152 (99a:06005)
  • 22. V. Reiner, The generalized Baues problem. New perspectives in algebraic combinatorics (Berkeley, CA, 1996-97), 293-336, Math. Sci. Res. Inst. Publ. 38, Cambridge Univ. Press, Cambridge, 1999. MR 1731820 (2000i:52023)
  • 23. V. Reiner, Note on the expected number of Yang-Baxter moves applicable to reduced decompositions. European J. Combin. 26 (2005), 1019-1021. MR 2143207 (2005m:05236)
  • 24. J. Richter-Gebert, Oriented matroids with few mutations, Discrete and Computational Geometry 10 (1993), 251-269. MR 1226979 (94f:52019)
  • 25. M. Salvetti, Topology of the complement of real hyperplanes in $ \mathbb{C}^n$. Invent. Math. 88 (1987), 603-618. MR 884802 (88k:32038)
  • 26. B. Shapiro, M. Shapiro and A. Vainshtein, Connected components in the intersection of two open opposite Schubert cells in $ {\rm SL}\sb n(R)/B$. Internat. Math. Res. Notices 1997, no. 10, 469-493. MR 1446839 (98e:14054)
  • 27. R.P. Stanley, Supersolvable lattices. Algebra Universalis 2 (1972), 197-217. MR 0309815 (46:8920)
  • 28. R.P. Stanley, On the number of reduced decompositions of elements of Coxeter groups. European J. Combin. 5 (1984), 359-372. MR 782057 (86i:05011)
  • 29. R.P. Stanley, An introduction to hyperplane arrangements. Geometric combinatorics, 389-496, IAS/Park City Math. Ser. 13, Amer. Math. Soc., Providence, RI, 2007. MR 2383131
  • 30. J.A. Tits, Le problème des mots dans les groupes de Coxeter. Symposia Mathematica (INDAM, Rome, 1967/68), 1(1969), 175-185 Academic Press, London. MR 0254129 (40:7339)
  • 31. J.A. Tits, A local approach to buildings. The geometric vein, pp. 519-547, Springer, New York-Berlin, 1981.
  • 32. G.M. Ziegler, Higher Bruhat orders and cyclic hyperplane arrangements. Topology 32 (1993), no. 2, 259-279. MR 1217068 (94e:52015)
  • 33. G.M. Ziegler, Lectures on polytopes. Graduate Texts in Mathematics 152. Springer-Verlag, New York, 1995. MR 1311028 (96a:52011)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 20F55, 20F05

Retrieve articles in all journals with MSC (2010): 20F55, 20F05


Additional Information

Victor Reiner
Affiliation: School of Mathematics, University of Minnesota, Minneapolis, Minnesota 55455
Email: reiner@math.umn.edu

Yuval Roichman
Affiliation: Department of Mathematics, Bar-Ilan University, 52900 Ramat-Gan, Israel
Email: yuvalr@math.biu.ac.il

DOI: https://doi.org/10.1090/S0002-9947-2012-05719-9
Keywords: Coxeter group, reduced words, supersolvable, hyperplane arrangement, weak order, reflection order, cellular string, zonotope, monotone path, diameter
Received by editor(s): June 28, 2011
Received by editor(s) in revised form: October 5, 2011
Published electronically: November 26, 2012
Additional Notes: The first author was supported by NSF grant DMS–0245379.
The second author was supported in part by the Israel Science Foundation grant # 947/04.
Article copyright: © Copyright 2012 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society