A generalization of Sperner’s theorem and an application to graph orientations

A generalization of Sperner’s theorem is established: For a multifamily M={Y1,…,Yp}M={Y1,…,Yp} of subsets of {1,…,n}{1,…,n} in which the repetition of subsets is allowed, a sharp lower bound for the number φ(M)φ(M) of ordered pairs (i,j)(i,j) satisfying i≠ji≠j and Yi⊆YjYi⊆Yj is determined. As an application, the minimum average distance of orientations of complete bipartite graphs is determined.