  We extend several results of the third author and C. Malvenuto on
graph-different permutations to the case of directed graphs and introduce new
open problems. Permutation capacity is a natural extension of Sperner capacity
from finite directed graphs to infinite digraphs. Our subject is combinatorial
in nature, but can be equally regarded as zero-error information theory.
