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

被引：6

作者：

Qian, Jianguo ^{[1
]}

Engel, Konrad ^{[2
]}

Xu, Wei ^{[1
]}

机构：

[1] Xiamen Univ, Sch Math Sci, Xiamen 361005, Fujian, Peoples R China

[2] Univ Rostock, Inst Math, D-18051 Rostock, Germany

来源：

DISCRETE APPLIED MATHEMATICS | 2009年 / 157卷 / 09期

基金：

中国国家自然科学基金;

关键词：

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

D O I：

10.1016/j.dam.2007.09.025

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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. (C) 2007 Elsevier B.V. All rights reserved.

引用

页码：2170 / 2176

页数：7

共 8 条

[1]

Anderson I., 1987, Combinatorics of finite sets

[2] Minimum average distance of strong orientations of graphs [J].

Dankelmann, P ;

Ollermann, OR ;

Wu, HL .

DISCRETE APPLIED MATHEMATICS, 2004, 143 (1-3) :204-212

[3]

Engel Konrad, 1997, SPERNER THEORY

[4]

GUTIN G, 1989, IZV AKAD NAUK BS FMN, V5, P101

[5] Optimal orientations of graphs and digraphs: A survey [J].

Koh, KM ;

Tay, EG .

GRAPHS AND COMBINATORICS, 2002, 18 (04) :745-756

[6] The diameter of an orientation of a complete multipartite graph [J].

Koh, KM ;

Tan, BP .

DISCRETE MATHEMATICS, 1996, 149 (1-3) :131-139

[7] ON THE SUM OF ALL DISTANCES IN A GRAPH OR DIGRAPH [J].

PLESNIK, J .

JOURNAL OF GRAPH THEORY, 1984, 8 (01) :1-21

[8] A clause about subsets in a fiurts set [J].

Sperner, E .

MATHEMATISCHE ZEITSCHRIFT, 1928, 27 :544-548

← 1 →