OJDM  Vol.9 No.4 , October 2019
Toric Heaps, Cyclic Reducibility, and Conjugacy in Coxeter Groups
Abstract: In 1986, G.X. Viennot introduced the theory of heaps of pieces as a visualization of Cartier and Foata’s “partially commutative monoids”. These are essentially labeled posets satisfying a few additional properties, and one natural setting where they arise is as models of reduced words in Coxeter groups. In this paper, we introduce a cyclic version of a heap, which loosely speaking, can be thought of as taking a heap and wrapping it into a cylinder. We call this object a toric heap, because we formalize it as a labeled toric poset, which is a cyclic version of an ordinary poset. Defining the category of toric heaps leads to the notion of certain morphisms such as toric extensions. We study toric heaps in Coxeter theory, because a cyclic shift of a reduced word is simply a conjugate by an initial or terminal generator. As such, we formalize and study a framework that we call cyclic reducibility in Coxeter theory, which is closely related to conjugacy. We introduce what it means for elements to be torically reduced, which is a stronger condition than simply being cyclically reduced. Along the way, we encounter a new class of elements that we call torically fully commutative (TFC), which are those that have a unique cyclic commutativity class, and comprise a strictly bigger class than the cyclically fully commutative (CFC) elements. We prove several cyclic analogues of results on fully commutative (FC) elements due to Stembridge. We conclude with how this framework fits into recent work in Coxeter groups, and we correct a minor flaw in a few recently published theorems.
Cite this paper: Chao, S. and Macauley, M. (2019) Toric Heaps, Cyclic Reducibility, and Conjugacy in Coxeter Groups. Open Journal of Discrete Mathematics, 9, 110-143. doi: 10.4236/ojdm.2019.94010.

[1]   Cartier, P. and Foata, D. (1969) Problemes combinatoires de commutation et reárrangements. Volume 85 of Lecture Notes in Mathematics, Springer Verlag, Berlin.

[2]   Viennot, G.X. (1986) Heaps of Pieces, I: Basic Definitions and Combinatorial Lemmas. In: Labelle, G. and Leroux, P., Eds., Combinatoire énumérative, Springer-Verlag, Berlin, 321-350.

[3]   Green, R.M. (2010) On the Combinatorics of Kac’s Asymmetry Function. Commentationes Mathematicae Universitatis Carolinae, 51, 217-235.

[4]   Stembridge, J.R. (1996) On the Fully Commutative Elements of Coxeter Groups. Journal of Algebraic Combinatorics, 5, 353-385.

[5]   Stembridge, J.R. (1998) The Enumeration of Fully Commutative Elements of Coxeter Groups. Journal of Algebraic Combinatorics, 7, 291-320.

[6]   Green, R.M. and Losonczy, J. (2002) Freely Braided Elements in Coxeter Groups. Annals of Combinatorics, 6, 337-348.

[7]   Billey, S.C. and Warrington, G.S. (2001) Kazhdan-Lusztig Polynomials for 321-Hexagon-Avoiding Permutations. Journal of Algebraic Combinatorics, 13, 111-136.

[8]   Green, R.M. (2007) Full Heaps and Representations of Affine Kac-Moody Algebras. International Electronic Journal of Algebra, 2, 137-188.

[9]   Wildberger, N.J. (2003) A Combinatorial Construction for Simply-Laced Lie Algebras. Advances in Applied Mathematics, 30, 385-396.

[10]   Di Francesco, P. and Kedem, R. (2010) Q-Systems, Heaps, Paths and Cluster Positivity. Communications in Mathematical Physics, 293, 727.

[11]   Bousquet-Mélou, M. and Viennot, X.G. (1992) Empilements de segments et q-énumération de polyominos convexes dirigés. Journal of Combinatorial Theory, Series A, 60, 196-224.

[12]   Fédou, J.-M. (1995) Sur les fonctions de Bessel. Discrete Mathematics, 139, 473-480.

[13]   Lalonde, P. (1995) Lyndon Heaps: An Analogue of Lyndon Words in Free Partially Commutative Monoids. Discrete Mathematics, 145, 171-189.

[14]   Bousquet-Mélou, M. and Rechnitzer, A. (2002) Lattice Animals and Heaps of Dimers. Discrete Mathematics, 258, 235-274.

[15]   Brak, R., Iliev, G.K., Rechnitzer, A. and Whittington, S.G. (2007) Motzkin Path Models of Long Chain Polymers in Slits. Journal of Physics A, 40, 4415.

[16]   Viennot, X.G. (2014) Heaps of Pieces and 2D Lorentzian Quantum Gravity. Workshop on 2D Quantum Gravity and Statistical Mechanics.

[17]   Gaubert, S. and Mairesse, J. (1999) Modeling and Analysis of Timed Petri Nets Using Heaps of Pieces. IEEE Transactions on Automatic Control, 44, 683-697.

[18]   Su, R., Van Schuppen, J.H. and Rooda, J.E. (2012) The Synthesis of Time Optimal Supervisors by Using Heaps-of-Pieces. IEEE Transactions on Automatic Control, 57, 105-118.

[19]   Develin, M., Macauley, M. and Reiner, V. (2016) Toric Partial Orders. Transactions of the American Mathematical Society, 368, 2263-2287.

[20]   Macauley, M. (2016) Morphisms and Order Ideals of Toric Posets. Mathematics, 4, 39.

[21]   Adin, R.M., Gessel, I.M., Reiner, V. and Roichman, Y. (2019) Cyclic Quasi-Symmetric Functions. Proceedings of the 314 Conference on Formal Power Series and Algebraic Combinatorics FPSAD Article 67, 12.

[22]   Marquis, T. (2014) Conjugacy Classes and Straight Elements in Coxeter Groups. Journal of Algebra, 407, 68-80.

[23]   Humphreys, J.E. (1990) Reflection Groups and Coxeter Groups. Cambridge University Press, Cambridge.

[24]   Björner, A. and Brenti, F. (2005) Combinatorics of Coxeter Groups. Springer Verlag, New York.

[25]   Matsumoto, H. (1964) Générateurs et relations des groupes de Weyl généralisés. Comptes rendus de l’Académie des Sciences Paris, 258, 3419-3422.

[26]   Pretzel, O. (1986) On Reorienting Graphs by Pushing down Maximal Vertices. Order, 3, 135-153.

[27]   Eriksson, H. and Eriksson, K. (2009) Conjugacy of Coxeter Elements. The Electronic Journal of Combinatorics, 16, R4.

[28]   Speyer, D.E. (2009) Powers of Coxeter Elements in Infinite Groups Are Reduced. Proceedings of the American Mathematical Society, 137, 1295-1302.

[29]   Boothby, T., Burkert, J., Eichwald, M., Ernst, D.C., Green, R.M. and Macauley, M. (2012) On the Cyclically Fully Commutative Elements of Coxeter Groups. Journal of Algebraic Combinatorics, 36, 123-148.

[30]   Pétréolle, M. (2016) Generating Series of Cyclically Fully Commutative Elements Is Rational.

[31]   Pétréolle, M. (2017) Characterization of Cyclically Fully Commutative Elements in Finite and Affine Coxeter Groups. European Journal of Combinatorics, 61, 106-132.

[32]   Fox, B. (2014) Conjugacy Classes of Cyclically Fully Commutative Elements in Coxeter Groups of Type A. Master’s Thesis, Northern Arizona University, Flagstaff.

[33]   Wachs, M.L. (2007) Poset Topology: Tools and Applications. In: Miller, E., Reiner, V. and Sturmfels, B., Eds., Geometric Combinatorics, IAS/Park City Mathematics Series, American Mathematical Society, Providence, 497-615.

[34]   Biagioli, R., Jouhet, F. and Nadeau, P. (2015) Fully Commutative Elements in Finite and Affine Coxeter Groups. Monatshefte für Mathematik, 178, 1-37.

[35]   Deodhar, V.V. (1982) On the Root System of a Coxeter Group. Communications in Algebra, 10, 611-630.

[36]   Krammer, D. (2009) The Conjugacy Problem for Coxeter Groups. Groups, Geometry, and Dynamics, 3, 71-171.

[37]   Eriksson, H. and Eriksson, K. (2010) Words with Intervening Neighbours in Infinite Coxeter Groups Are Reduced. The Electronic Journal of Combinatorics, 17, N9.

[38]   Dranishnikov, A.N. and Januszkiewicz, T. (1999) Every Coxeter Group Acts Amenably on a Compact Space. Topology Proceedings, 24, 135-141.