Document Type


Publication Date


Publication Title

Proceedings of the American Mathematical Society


American Mathematical Society


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.


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

Included in

Mathematics Commons