Richard Hammack

The digraph factorial

Abstract: In 1971, Lov'asz proved the the following cancellation law concerning the direct product of digraphs. If A x C ≅ B x C, then A ≅ B, provided that C admits no homomorphism into a disjoint union of directed cycles. On the other hand, if such a homomorphism does exist, then there are non-isomorphic pairs A \not≅ B for which A x C ≅ B x C. This gives exact conditions on C that govern whether cancellation is guaranteed to hold or fail. Left unresolved was the question of what conditions on A (or B) might guarantee cancellation. I introduce a construction called the factorial of a digraph that settles this issue.
Given a digraph A, its factorial A! is a certain digraph defined on the permutations of the vertex set of A. The construction is in many ways analogous to the factorial operation on integers, as we shall see. In fact, the edges of A! form a group that can be viewed as an extension of the automorphism group of A. This group acts on V(A!), and for a given A and C, the orbits are in one-to-one correspondence with the digraphs B for which A x C ≅ B x C. If the action is transitive, then cancellation holds. In addition to solving the cancellation problem, the digraph factorial poses many interesting questions. If G is an arbitrary finite group, is there a digraph A for which G ≅ E(A!)? Can one characterize those digraphs A for which E(A!) is (say) abelian? Are such questions significant or mere curiosities? There are more unknowns than knowns.