Intersecting and cross-intersecting families of labeled sets

Abstract

A family A of sets is said to be intersecting if any two sets in A intersect. Families A1,...,Ap are said to be cross-intersecting if, for any i, j ∈ {1, ...,p} such that i ≠ j, any set in Ai intersects any set in Aj. For k = (k 1,..., kn) ∈ Nn, 2 ≤ k1 ≤ ... ≤ kn, let ℒk be the family of labeled n-sets given by ℒk := {{(1,l1),..., (n, ln)}: li ∈ [1,...,ki},i = 1,...,n}. We point out a relationship between intersecting families and cross-intersecting families of labeled sets, and we show that, if A1,...,Ap are cross-intersecting sub-families of ℒk, then Σ j=1p|Aj|≤ {pk2...knk1k2...knif p≥k1. if p ≤k1; We also determine the cases of equality. We then obtain a more general inequality, a special case of which is a sharp bound for cross-intersecting families of permutations.