Posets from Admissible Coxeter Sequences

  • Matthew Macauley
  • Henning S. Mortveit


We study the equivalence relation on the set of acyclic orientations of an undirected graph $\Gamma$ 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 $\Gamma$ to those over $\Gamma'$ and $\Gamma"$, the graphs obtained from $\Gamma$ 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.

Article Number