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

作者：Qian Jianguo^*; Engel Konrad; Xu Wei

来源：Discrete Applied Mathematics, 2009, 157(9): 2170-2176.

DOI：10.1016/j.dam.2007.09.025

• Sperner's theorem
• Average distance
• Graph orientation
• Multifamily of subsets

A generalization of Sperner's theorem is established: For a Multifamily M = {Y(1),..., Y(p)} of subsets of {1,..., n) in which the repetition of subsets is allowed, a sharp lower bound for the number phi(M) of ordered pairs (i, j) satisfying i not equal j and Y(i) subset of Y(j) is determined. As an application, the minimum average distance of orientations of complete bipartite graphs is determined.

• 出版日期2009-5-6
• 单位厦门大学