Equivalences on Acyclic Orientations
From MaRDI portal
Publication:6206673
arXiv0709.0291MaRDI QIDQ6206673FDOQ6206673
Authors: M. Macauley, Henning S. Mortveit 
Publication date: 3 September 2007
Abstract: 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 ~kappa and ~delta, 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 of these graphs are denoted kappa(Y) and delta(Y), respectively. We characterize the structure of C(Y) and D(Y), show how delta(Y) can be derived from kappa(Y), and give enumeration results for kappa(Y). Moreover, we show how to associate a poset structure to each kappa-equivalence class, and we characterize these posets. This allows us to create a bijection from Acyc(Y)/~kappa to the union of Acyc(Y')/~kappa and Acyc(Y)/~kappa, Y' and Y denote edge deletion and edge contraction for a cycle-edge in Y, respectively, which in turn shows that kappa(Y) may be obtained by an evaluation of the Tutte polynomial at (1,0).
Enumerative combinatorics (05A99) Directed graphs (digraphs), tournaments (05C20) Partial orders, general (06A06) Reflection and Coxeter groups (group-theoretic aspects) (20F55)
This page was built for publication: Equivalences on Acyclic Orientations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6206673)
