Cross-intersecting families and primitivity of symmetric systems
Let X be a finite set and p⊆2X, the power set of X, satisfying three conditions: (a) p is an ideal in 2X, that is, if A∈p and B⊂A, then B∈p; (b) For A∈2X with ∣A∣≥2, A∈p if {x,y}∈p for any x,y∈A with x=y; (c) {x}∈p for every x∈X. The pair (X,p) is called a symmetric system if there is a group Γ transitively acting on X and preserving the ideal p. A family {A1,A2,…,Am}⊆2X is said to be a cross-p-family of X if {a,b}∈p for any a∈Ai and b∈Aj with i=j. We prove that if (X,p) is a symmetric system and {A1,A2,…,Am}⊆2X is a cross-p-family of X, then ∑i=1m∣Ai∣≤{∣X∣mα(X,p)if m≤α(X,p)∣X∣,if m≥α(X,p)∣X∣, where α(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.