|
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. |