Cross-intersecting families and primitivity of symmetric systems

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:118

Article

Wang, Jun¹  Zhang, Huajun^1,2 

[1] Shanghai Normal Univ, Dept Math, Shanghai 200234, Peoples R China

[2] Zhejiang Normal Univ, Dept Math, Jinhua 321004, Peoples R China

关键词: Intersecting family;    Cross-intersecting family;    Symmetric system;    Erdos-Ko-Rado theorem;   

DOI  :  10.1016/j.jcta.2010.09.005

来源: Elsevier

【 摘 要 】

Let X be a finite set and p subset of 2(X) the power set of X, satisfying three conditions: (a) p is an ideal in 2(X) that is, if A is an element of p and B subset of A. then B is an element of p; (b) for A is an element of 2(X) with vertical bar A vertical bar >= 2, A is an element of p if {x, y} is an element of p for any x, y is an element of A with x not equal y; (c) {x} is an element of p for every x is an element of X. The pair (X, p) is called a symmetric system if there is a group P transitively acting on X and preserving the ideal p. A family {A1, A2,..., A(m)} subset of 2(X) is said to be a cross-p-family of X if {a, b} is an element of p for any a is an element of A(i) and b is an element of A(j) with i not equal j. We prove that if (X, p) is a symmetric system and {A1, A2,..., A(m)) subset of 2(X) is a cross-p-family of X, then Sigma(m)(i=1) vertical bar Ai vertical bar <= (vertical bar X vertical bar)(m alpha(X, p)) (if m >= vertical bar X vertical bar/alpha(X,p),) (if m <= vertical bar X vertical bar/alpha(X,p), m alpha(X,p)) where alpha(X, p) = max {vertical bar A vertical bar: A is an element of p}. This generalizes Hilton's theorem on cross-intersecting families of finite sets, and provides analogs for cross-t-intersecting families of finite sets, finite vector spaces and permutations, etc. Moreover, the primitivity of symmetric systems is introduced to characterize the optimal families. (C) 2010 Elsevier Inc. All rights reserved.

【 授权许可】

Free