Physical Sciences and Mathematics Commons^™

Equivalences On Acyclic Orientations, Matthew Macauley, Henning S. Mortveit

Publications

The cyclic and dihedral groups can be made to act on the set Acyc(Y ) of acyclic orientations of an undirected graph Y , and this gives rise to the equivalence relations ∼κ and ∼δ, respectively. These two actions and their corresponding equivalence classes are closely related to combinatorial problems arising in the context of Coxeter groups, sequential dynamical systems, the chip-firing game, and representations of quivers.

In this paper we construct the graphs C(Y ) and D(Y ) with vertex sets Acyc(Y ) and whose connected components encode the equivalence classes. The number of connected components …

On Enumeration Of Conjugacy Classes Of Coxeter Elements, Matthew Macauley, Henning S. Mortveit

Publications

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 …