|
On enumeration of conjugacy classes of Coxeter elements
Author(s):
Matthew
Macauley;
Henning
S.
Mortveit
Journal:
Proc. Amer. Math. Soc.
136
(2008),
4157-4165.
MSC (2000):
Primary 20F55, 05A99, 06A06
Posted:
June 20, 2008
Errata:
Proc. Amer. Math. Soc. 137 (2009), 3167
MathSciNet review:
2431028
Retrieve article in:
PDF
Abstract |
References |
Similar articles |
Additional information
Abstract:
In this paper we study the equivalence relation on the set of acyclic orientations of a graph  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  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  , 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:
-
- 1.
- Anders Björner, László Lovász, and Peter Shor, Chip-firing games on graphs, European Journal of Combinatorics 12 (1991), 283-291. MR 1120415 (92g:90193)
- 2.
- B. Chen, Orientations, lattice polytopes, and group arrangements I. Chromatic and tension polynomials of graphs. Preprint at arXiv:0706.3273.
- 3.
- Emeric Gioan, Enumerating degree sequences in digraphs and a cycle-cocycle reversing system, European Journal of Combinatorics 28 (2007), 1351-1366. MR 2305596 (2008a:05108)
- 4.
- James E. Humphreys, Reflection groups and Coxeter groups, Cambridge Studies in Advanced Mathematics, no. 29, Cambridge University Press, 1990. MR 1066460 (92h:20002)
- 5.
- Matthew Macauley and Henning S. Mortveit, Cycle equivalence of graph dynamical systems, submitted. Preprint at arXiv:0802.4412.
- 6.
- R. Marsh, M. Reineke, and A. Zelevinsky, Generalized associahedra via quiver representations, Transactions of the American Mathematical Society 355 (2003), 4171-4186. MR 1990581 (2004g:52014)
- 7.
- Isabella Novik, Alexander Postnikov, and Bernd Sturmfels, Syzygies of oriented matroids, Duke Mathematical Journal 111 (2002), 287-317. MR 1882136 (2003b:13023)
- 8.
- Peter Orlik and Hiroaki Terao, Arrangements of hyperplanes, A Series of Comprehensive Studies in Mathematics, Springer-Verlag, 1992. MR 1217488 (94e:52014)
- 9.
- C. M. Reidys, Acyclic orientations of random graphs, Advances in Applied Mathematics 21 (1998), no. 2, 181-192. MR 1634697 (99e:05110)
- 10.
- J. Y. Shi, The enumeration of Coxeter elements, Journal of Algebraic Combinatorics 6 (1997), 161-171. MR 1436533 (98d:20048)
- 11.
- Jian Yi Shi, Conjugacy relation on Coxeter elements, Advances in Mathematics 161 (2001), 1-19. MR 1857933 (2002g:20072)
Similar Articles:
Retrieve articles in Proceedings of the American Mathematical
Society
with
MSC (2000):
20F55, 05A99, 06A06
Retrieve articles in all Journals with
MSC (2000):
20F55, 05A99, 06A06
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
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
DOI:
10.1090/S0002-9939-08-09543-9
PII:
S 0002-9939(08)09543-9
Received by editor(s):
November 7, 2007
Posted:
June 20, 2008
Communicated by:
Jim Haglund
Copyright of article:
Copyright
2008,
American Mathematical Society
|
