Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420541 | Discrete Applied Mathematics | 2009 | 7 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Jianguo Qian, Konrad Engel, Wei Xu,