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

• DOI: 10.1016/j.dam.2007.09.025
• Publication Date: 2007-12-21T17:56:26Z
• Authors: Jianguo Qian; Konrad Engel; Wei Xu
• Keywords: Sperner's theorem; Applied Mathematics; Multifamily of subsets; Discrete Mathematics and Combinatorics; Average distance; Sperner’s theorem; 0102 computer and information sciences; Graph orientation; 0101 mathematics; 01 natural sciences

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