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 …