We use cookies to enhance your experience on our website. By continuing to use our website, you are agreeing to our use of cookies. You can change your cookie settings at any time. Find out more
maximum product of weights of cross-intersecting families | Journal of the London Mathematical Society | Oxford Academic
Skip to Main Content

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

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.