On enumeration of conjugacy classes of Coxeter elements
HTML articles powered by AMS MathViewer
- by Matthew Macauley and Henning S. Mortveit PDF
- Proc. Amer. Math. Soc. 136 (2008), 4157-4165 Request permission
Erratum: Proc. Amer. Math. Soc. 137 (2009), 3167-3167.
Abstract:
In this paper we study the equivalence relation on the set of acyclic orientations of a graph $Y$ that arises through source-to-sink conversions. This source-to-sink conversion encodes, e.g. conjugation of Coxeter elements of a Coxeter group. We give a direct proof of a recursion for the number of equivalence classes of this relation for an arbitrary graph $Y$ using edge deletion and edge contraction of non-bridge edges. We conclude by showing how this result may also be obtained through an evaluation of the Tutte polynomial as $T_Y(1,0)$, and we provide bijections to two other classes of acyclic orientations that are known to be counted in the same way. A transversal of the set of equivalence classes is given.References
- Anders Björner, László Lovász, and Peter W. Shor, Chip-firing games on graphs, European J. Combin. 12 (1991), no. 4, 283–291. MR 1120415, DOI 10.1016/S0195-6698(13)80111-4
- B. Chen, Orientations, lattice polytopes, and group arrangements I. Chromatic and tension polynomials of graphs. Preprint at arXiv:0706.3273.
- Emeric Gioan, Enumerating degree sequences in digraphs and a cycle-cocycle reversing system, European J. Combin. 28 (2007), no. 4, 1351–1366. MR 2305596, DOI 10.1016/j.ejc.2005.11.006
- 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
- Matthew Macauley and Henning S. Mortveit, Cycle equivalence of graph dynamical systems, submitted. Preprint at arXiv:0802.4412.
- Robert Marsh, Markus Reineke, and Andrei Zelevinsky, Generalized associahedra via quiver representations, Trans. Amer. Math. Soc. 355 (2003), no. 10, 4171–4186. MR 1990581, DOI 10.1090/S0002-9947-03-03320-8
- Isabella Novik, Alexander Postnikov, and Bernd Sturmfels, Syzygies of oriented matroids, Duke Math. J. 111 (2002), no. 2, 287–317. MR 1882136, DOI 10.1215/S0012-7094-02-11124-7
- 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
- C. M. Reidys, Acyclic orientations of random graphs, Adv. in Appl. Math. 21 (1998), no. 2, 181–192. MR 1634697, DOI 10.1006/aama.1998.0595
- Jian-Yi Shi, The enumeration of Coxeter elements, J. Algebraic Combin. 6 (1997), no. 2, 161–171. MR 1436533, DOI 10.1023/A:1008695121783
- Jian-yi Shi, Conjugacy relation on Coxeter elements, Adv. Math. 161 (2001), no. 1, 1–19. MR 1857933, DOI 10.1006/aima.2001.1985
Additional Information
- Matthew Macauley
- Affiliation: Department of Mathematics, University of California, Santa Barbara, Santa Barbara, California 93106-3080 – and – NDSSL, Virginia Bioinformatics Institute, Virginia Tech, Blacksburg, Virginia 24061
- Address at time of publication: Department of Mathematical Sciences, Clemson University, Clemson, South Carolina 29634 - and - NDSSL, Virginia Bioinformatics Institute, Virginia Tech, Blacksburg, Virginia 24061
- MR Author ID: 836395
- Email: macauley@vt.edu, mmacaul@clemson.edu
- Henning S. Mortveit
- Affiliation: Department of Mathematics, Virginia Tech, Blacksburg, Virginia 24061 – and – NDSSL, Virginia Bioinformatics Institute, Virginia Tech, Blacksburg, Virginia 24061
- Email: henning.mortveit@vt.edu
- Received by editor(s): November 7, 2007
- Published electronically: June 20, 2008
- Communicated by: Jim Haglund
- © Copyright 2008 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 136 (2008), 4157-4165
- MSC (2000): Primary 20F55, 05A99, 06A06
- DOI: https://doi.org/10.1090/S0002-9939-08-09543-9
- MathSciNet review: 2431028