An Erdos-Ko-Rado theorem for restricted signed sets

作者：Li Yu shuang^*

来源：Acta Mathematicae Applicatae Sinica-English Series, 2010, 26(1): 107-112.

DOI：10.1007/s10255-009-6184-z

• Erdos-Ko-Rado theorem
• Restricted signed sets
• Intersecting family
• LYM-type inequality

A restricted signed r-set is a pair (A, f), where A subset of [n] = {1, 2, ..., n} is an r-set and f is a map from A to [n] with f(i) not equal i for all i is an element of A. For two restricted signed sets (A, f) and (B, g), we define an order as (A, f) <= (B, g) if A subset of B and g|A = f. A family A of restricted signed sets on [n] is an intersecting antichain if for any (A, f), (B, g) is an element of A , they are incomparable and there exists x is an element of A boolean AND B such that f(x) = g(x). In this paper, we first give a LYM-type inequality for any intersecting antichain A of restricted signed sets, from which we then obtain vertical bar A vertical bar <= ((r-1) (n-1)) (n-1)(r-1) if A consists of restricted signed r-sets on [n]. Unless r = n = 3, equality holds if and only if A consists of all restricted signed r-sets (A, f) such that x (0) is an element of A and f(x (0)) - epsilon (0) for some fixed x (0) is an element of [n], epsilon (0) is an element of[n] \ {x (0)}.

• 出版日期2010-1
• 单位燕山大学