Construction of asymmetric connectors of depth two

An (n,N)-connector of depth d is an acyclic digraph with n inputs and N outputs in which for any injective mapping of input vertices into output vertices there exist n vertex disjoint paths of length at most d joining each input to its corresponding output. In this paper we consider the problem of construction of sparse depth two connectors with n?N. We use posets of star products and their matching properties to construct such connectors. In particular, this gives a simple explicit construction for connectors of size O(Nlogn/loglogn). Thus our earlier idea to use other posets than the family of subsets of a finite set was successful.