Article ID Journal Published Year Pages File Type
420541 Discrete Applied Mathematics 2009 7 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,