Document Type

Article

Publication Date

11-2011

Publication Title

Journal of Combinatorics

Volume

18

Issue

1

Abstract

We study the equivalence relation on the set of acyclic orientations of an undirected graph Γ generated by source-to-sink conversions. These conversions arise in the contexts of admissible sequences in Coxeter theory, quiver representations, and asynchronous graph dynamical systems. To each equivalence class we associate a poset, characterize combinatorial properties of these posets, and in turn, the admissible sequences. This allows us to construct an explicit bijection from the equivalence classes over Γ to those over Γ′ and Γ′′, the graphs obtained from Γ by edge deletion and edge contraction of a fixed cycle-edge, respectively. This bijection yields quick and elegant proofs of two non-trivial results: (i) A complete combinatorial invariant of the equivalence classes, and (ii) a solution to the conjugacy problem of Coxeter elements for simply-laced Coxeter groups. The latter was recently proven by H. Eriksson and K. Eriksson using a much different approach.

Comments

This manuscript has been published in the Journal of Combinatorics. Please find the published version here (note that a subscription is necessary to access this version):

http://www.combinatorics.org/ojs/index.php/eljc/article/view/v18i1p197/pdf

Share

COinS