Acyclic digraphs and local hierarchy theory

The degree of a vertex of a digraph is the number of outgoing edges minus the number of incoming edges. Acyclic digraphs give a model for networks such as citation networks and organizational charts. Motivated by a ''local hierarchy theory'' developed for this model, we consider the set [email protected]^(@d) of acyclic digraphs with a specified degree sequence @d. We show that all digraphs in this set can be generated from any one such digraph using just one kind of basic transformation. In the case of degree sequences @d that are minimal in the ''Lorenz order'', we investigate the maximum number of edges in an acyclic digraph in [email protected]^(@d) and show how to construct digraphs in [email protected]^(@d) with many edges. Determining this maximum number of edges seems to be a very difficult problem.