A generalization of Sperner’s theorem and an application to graph orientations |
| |
| Authors: | Jianguo Qian Konrad Engel |
| |
| Institution: | a School of Mathematical Sciences, Xiamen University, Xiamen 361005, Fujian, PR China
b University of Rostock, Institute of Mathematics, D-18051 Rostock, Germany |
| |
| Abstract: | A 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. |
| |
| Keywords: | Sperner&rsquo s theorem Average distance Graph orientation Multifamily of subsets |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
