Abstract

A set of sets is called a family. Two families $$\mathcal {A}$$ and $$\mathcal {B}$$ are said to be cross-$$t$$-intersecting if each set in $$\mathcal {A}$$ intersects each set in $$\mathcal {B}$$ in at least $$t$$ elements. An active problem in extremal set theory is to determine the maximum product of sizes of cross-$$t$$-intersecting subfamilies of a given family. This incorporates the classical Erdös–Ko–Rado (EKR) problem. We prove a cross-$$t$$-intersection theorem for weighted subsets of a set by means of a new subfamily alteration method, and use the result to provide solutions for three natural families. For $$r \in [n] = \{1, 2,\ldots , n\}$$, let $${[n] \choose r}$$ be the family of $$r$$-element subsets of $$[n]$$, and let $${[n] \choose \leq r}$$ be the family of subsets of $$[n]$$ that have at most $$r$$ elements. Let $$\mathcal {F}_{n,r,t}$$ be the family of sets in $${[n] \choose \leq r}$$ that contain $$[t]$$. We show that if $$g : {[m] \choose \leq r} \rightarrow \mathbb {R}^+$$ and $$h : {[n] \choose \leq s} \rightarrow \mathbb {R}^+$$ are functions that obey certain conditions, $$\mathcal {A} \subseteq {[m] \choose \leq r}$$, $$\mathcal {B} \subseteq {[n] \choose \leq s}$$, and $$\mathcal {A}$$ and $$\mathcal {B}$$ are cross-$$t$$-intersecting, then  

\[ \sum_{A \in \mathcal{A}} g(A) \sum_{B \in \mathcal{B}} h(B) \leq \sum_{C \in \mathcal{F}_{m,r,t}} g(C) \sum_{D \in \mathcal{F}_{n,s,t}} h(D), \]
and equality holds if $$\mathcal {A} = \mathcal {F}_{m,r,t}$$ and $$\mathcal {B} = \mathcal {F}_{n,s,t}$$. We prove this in a more general setting and characterize the cases of equality. We use the result to show that the maximum product of sizes of two cross-$$t$$-intersecting families $$\mathcal {A} \subseteq {[m] \choose r}$$ and $$\mathcal {B} \subseteq {[n] \choose s}$$ is $${m-t \choose r-t}{n-t \choose s-t}$$ for $$\min \{m,n\} \geq n_0(r,s,t)$$, where $$n_0(r,s,t)$$ is close to best possible. We obtain analogous results for families of integer sequences and for families of multisets. The results yield generalizations for $$k \geq 2$$ cross-$$t$$-intersecting families, and EKR-type results.

You do not currently have access to this article.