Document Type

Article

Publication Date

11-2007

Publication Title

Proceedings of the American Mathematical Society

Publisher

American Mathematical Society

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.

Comments

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):

http://www.ams.org/journals/proc/2008-136-12/S0002-9939-08-09543-9/

Download

Included in

Mathematics Commons

Share

COinS