Superconcentrators

An n-superconcentrator is an acyclic directed graph with n inputs and n outputs for which, for every r n, every set of r inputs, and every set of r outputs, there exists an r-flow (a set of r vertex-disjoint directed paths) from the given inputs to the given outputs. We show that there exist n-superconcentrators with 39n + O(log n) (in fact, at most $40n$) edges, depth O(log n), and maximum degree (in-degree plus out-degree) 16.