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.