An Erdos-Ko-Rado Theorem for signed sets

被引：33

作者：

Bollobas, B ^{[1
]}

Leader, I ^{[1
]}

机构：

[1] UNIV CAMBRIDGE,DEPT PURE MATH & MATH STAT,CAMBRIDGE CB2 1TN,ENGLAND

来源：

COMPUTERS & MATHEMATICS WITH APPLICATIONS | 1997年 / 34卷 / 11期

关键词：

extremal problems; intersecting families; discrete isoperimetric inequalities;

D O I：

10.1016/S0898-1221(97)00215-0

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

A signed r-set on [n] = {1,..., n} is a pair (A, f), where A subset of [n] is an r-set and f is a function from A to {-1, 1}. A family A of signed r-sets is intersecting if for any (A, f), (B, g) is an element of A there exists x is an element of A boolean AND B such that f(x)=g(x). Tn this note, we prove that if A is an intersecting family of signed r-sets on [n], then \A\ less than or equal to 2(r-1)(3P:). We also present an application of this result to a diameter problem in the grid.

引用

页码：9 / 13

页数：5

共 5 条

[1]

[Anonymous], 1987, Combinatorics of finite sets

[2] MAXIMAL SETS OF GIVEN DIAMETER IN THE GRID AND THE TORUS [J].

BOLLOBAS, B ;

LEADER, I .

DISCRETE MATHEMATICS, 1993, 122 (1-3) :15-35

[3] INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS [J].

ERDOS, P ;

RADO, R ;

KO, C .

QUARTERLY JOURNAL OF MATHEMATICS, 1961, 12 (48) :313-&

[4]

Katona G. O. H., 1972, J. Comb. Theory Ser. B, V13, P183, DOI [10.1016/0095-8956(72)90054-8, DOI 10.1016/0095-8956(72)90054-8]

[5]

KLEITMAN DJ, 1988, DISCRETE MATH, V73, P119

← 1 →