Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4655696 | Journal of Combinatorial Theory, Series A | 2011 | 8 Pages |
Let X be a finite set and p⊆X2p⊆2X, the power set of X , satisfying three conditions: (a) pp is an ideal in X22X, that is, if A∈pA∈p and B⊂AB⊂A, then B∈pB∈p; (b) for A∈X2A∈2X with |A|⩾2|A|⩾2, A∈pA∈p if {x,y}∈p{x,y}∈p for any x,y∈Ax,y∈A with x≠yx≠y; (c) {x}∈p{x}∈p for every x∈Xx∈X. The pair (X,p)(X,p) is called a symmetric system if there is a group Γ transitively acting on X and preserving the ideal pp. A family {A1,A2,…,Am}⊆X2{A1,A2,…,Am}⊆2X is said to be a cross-pp-family of X if {a,b}∈p{a,b}∈p for any a∈Aia∈Ai and b∈Ajb∈Aj with i≠ji≠j. We prove that if (X,p)(X,p) is a symmetric system and {A1,A2,…,Am}⊆X2{A1,A2,…,Am}⊆2X is a cross-pp-family of X, then∑i=1m|Ai|⩽{|X|if m⩽|X|α(X,p),mα(X,p)if m⩾|X|α(X,p), where α(X,p)=max{|A|:A∈p}α(X,p)=max{|A|:A∈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.