Diameter of graphs of reduced words and galleries

Reiner, Victor; Roichman, Yuval

doi:10.1090/S0002-9947-2012-05719-9

Diameter of graphs of reduced words and galleries
HTML articles powered by AMS MathViewer

by Victor Reiner and Yuval Roichman PDF

Trans. Amer. Math. Soc. 365 (2013), 2779-2802 Request permission

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

Drew Armstrong, The sorting order on a Coxeter group, J. Combin. Theory Ser. A 116 (2009), no. 8, 1285–1305. MR 2568800, DOI 10.1016/j.jcta.2009.03.009
Christos A. Athanasiadis and Francisco Santos, Monotone paths on zonotopes and oriented matroids, Canad. J. Math. 53 (2001), no. 6, 1121–1140. MR 1863845, DOI 10.4153/CJM-2001-042-3
Christos A. Athanasiadis, Paul H. Edelman, and Victor Reiner, Monotone paths on polytopes, Math. Z. 235 (2000), no. 2, 315–334. MR 1795510, DOI 10.1007/s002090000152
Patrick Dehornoy and Marc Autord, On the distance between the expressions of a permutation, European J. Combin. 31 (2010), no. 7, 1829–1846. MR 2673022, DOI 10.1016/j.ejc.2010.03.003
Hélène Barcelo and Edwin Ihrig, Lattices of parabolic subgroups in connection with hyperplane arrangements, J. Algebraic Combin. 9 (1999), no. 1, 5–24. MR 1676736, DOI 10.1023/A:1018607830027
H. J. Baues, Geometry of loop spaces and the cobar construction, Mem. Amer. Math. Soc. 25 (1980), no. 230, ix+171. MR 567799, DOI 10.1090/memo/0230
L. J. Billera, M. M. Kapranov, and B. Sturmfels, Cellular strings on polytopes, Proc. Amer. Math. Soc. 122 (1994), no. 2, 549–555. MR 1205482, DOI 10.1090/S0002-9939-1994-1205482-0
Louis J. Billera and Bernd Sturmfels, Fiber polytopes, Ann. of Math. (2) 135 (1992), no. 3, 527–549. MR 1166643, DOI 10.2307/2946575
Anders Björner, Essential chains and homotopy type of posets, Proc. Amer. Math. Soc. 116 (1992), no. 4, 1179–1181. MR 1140664, DOI 10.1090/S0002-9939-1992-1140664-6
Anders Björner and Francesco Brenti, Combinatorics of Coxeter groups, Graduate Texts in Mathematics, vol. 231, Springer, New York, 2005. MR 2133266
Anders Björner, Paul H. Edelman, and Günter M. Ziegler, Hyperplane arrangements with a lattice of regions, Discrete Comput. Geom. 5 (1990), no. 3, 263–288. MR 1036875, DOI 10.1007/BF02187790
Anders Björner, Michel Las Vergnas, Bernd Sturmfels, Neil White, and Günter M. Ziegler, Oriented matroids, Encyclopedia of Mathematics and its Applications, vol. 46, Cambridge University Press, Cambridge, 1993. MR 1226888
Raul Cordovil, Sur les matroïdes orientés de rang $3$ et les arrangements de pseudodroites dans le plan projectif réel, European J. Combin. 3 (1982), no. 4, 307–318 (French, with English summary). MR 687729, DOI 10.1016/S0195-6698(82)80015-2
R. Cordovil and M. L. Moreira, A homotopy theorem on oriented matroids, Discrete Math. 111 (1993), no. 1-3, 131–136. Graph theory and combinatorics (Marseille-Luminy, 1990). MR 1210090, DOI 10.1016/0012-365X(93)90149-N
Pierre Deligne, Les immeubles des groupes de tresses généralisés, Invent. Math. 17 (1972), 273–302 (French). MR 422673, DOI 10.1007/BF01406236
Paul H. Edelman, A partial order on the regions of $\textbf {R}^{n}$ dissected by hyperplanes, Trans. Amer. Math. Soc. 283 (1984), no. 2, 617–631. MR 737888, DOI 10.1090/S0002-9947-1984-0737888-6
S. Felsner and H. Weil, A theorem on higher Bruhat orders, Discrete Comput. Geom. 23 (2000), no. 1, 121–127. MR 1727126, DOI 10.1007/PL00009485
James E. Humphreys, Reflection groups and Coxeter groups, Cambridge Studies in Advanced Mathematics, vol. 29, Cambridge University Press, Cambridge, 1990. MR 1066460, DOI 10.1017/CBO9780511623646
Yu. I. Manin and V. V. Schechtman, Arrangements of hyperplanes, higher braid groups and higher Bruhat orders, Algebraic number theory, Adv. Stud. Pure Math., vol. 17, Academic Press, Boston, MA, 1989, pp. 289–308. MR 1097620, DOI 10.2969/aspm/01710289
Peter Orlik and Hiroaki Terao, Arrangements of hyperplanes, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 300, Springer-Verlag, Berlin, 1992. MR 1217488, DOI 10.1007/978-3-662-02772-1
Jörg Rambau, A suspension lemma for bounded posets, J. Combin. Theory Ser. A 80 (1997), no. 2, 374–379. MR 1485152, DOI 10.1006/jcta.1997.2813
Victor Reiner, The generalized Baues problem, New perspectives in algebraic combinatorics (Berkeley, CA, 1996–97) Math. Sci. Res. Inst. Publ., vol. 38, Cambridge Univ. Press, Cambridge, 1999, pp. 293–336. MR 1731820
Victor Reiner, Note on the expected number of Yang-Baxter moves applicable to reduced decompositions, European J. Combin. 26 (2005), no. 6, 1019–1021. MR 2143207, DOI 10.1016/j.ejc.2004.06.010
Jürgen Richter-Gebert, Oriented matroids with few mutations, Discrete Comput. Geom. 10 (1993), no. 3, 251–269. MR 1226979, DOI 10.1007/BF02573980
M. Salvetti, Topology of the complement of real hyperplanes in $\textbf {C}^N$, Invent. Math. 88 (1987), no. 3, 603–618. MR 884802, DOI 10.1007/BF01391833
B. Shapiro, M. Shapiro, and A. Vainshtein, Connected components in the intersection of two open opposite Schubert cells in $\textrm {SL}_n(\textbf {R})/B$, Internat. Math. Res. Notices 10 (1997), 469–493. MR 1446839, DOI 10.1155/S1073792897000329
R. P. Stanley, Supersolvable lattices, Algebra Universalis 2 (1972), 197–217. MR 309815, DOI 10.1007/BF02945028
Richard P. Stanley, On the number of reduced decompositions of elements of Coxeter groups, European J. Combin. 5 (1984), no. 4, 359–372. MR 782057, DOI 10.1016/S0195-6698(84)80039-6
Richard P. Stanley, An introduction to hyperplane arrangements, Geometric combinatorics, IAS/Park City Math. Ser., vol. 13, Amer. Math. Soc., Providence, RI, 2007, pp. 389–496. MR 2383131, DOI 10.1090/pcms/013/08
Jacques Tits, Le problème des mots dans les groupes de Coxeter, Symposia Mathematica (INDAM, Rome, 1967/68) Academic Press, London, 1969, pp. 175–185 (French). MR 0254129
J.A. Tits, A local approach to buildings. The geometric vein, pp. 519–547, Springer, New York–Berlin, 1981.
Günter M. Ziegler, Higher Bruhat orders and cyclic hyperplane arrangements, Topology 32 (1993), no. 2, 259–279. MR 1217068, DOI 10.1016/0040-9383(93)90019-R
Günter M. Ziegler, Lectures on polytopes, Graduate Texts in Mathematics, vol. 152, Springer-Verlag, New York, 1995. MR 1311028, DOI 10.1007/978-1-4613-8431-1