The maximal sum of sizes of cross intersecting families for multisets

Abstract

Let $k$, $t$ and $m$ be positive integers. A $k$-multiset of $[m]$ is a collection of $k$ elements of $[m]$ with repetition and without ordering. We use $\left(\left(\genfrac{}{}{0ex}{}{[m]}{k}\right)\right)$ to denote all the $k$-multisets of $[m]$. Two multiset families $\mathcal{F}$ and $\mathcal{G}$ in $\left(\left(\genfrac{}{}{0ex}{}{[m]}{k}\right)\right)$ are called cross $t$-intersecting if $|F\cap G|\ge t$ for any $F\in \mathcal{F}$ and $G\in \mathcal{G}$. Moreover, if $\mathcal{F}=\mathcal{G}$, we call $\mathcal{F}$ a $t$-intersecting family in $\left(\left(\genfrac{}{}{0ex}{}{[m]}{k}\right)\right)$. Meagher and Purdy~(2011) presented a multiset variant of Erdős-Ko-Rado Theorem for $t$-intersecting family in $\left(\left(\genfrac{}{}{0ex}{}{[m]}{k}\right)\right)$ when $t=1$, and Füredi, Gerbner and Vizer~(2016) extended this result to general $t\ge 2$ with $m\ge 2k-t$, verified a conjecture proposed by Meagher and Purdy~(2011). In this paper, we determine the maximum sum of cross $t$-intersecting families $\mathcal{F}$ and $\mathcal{G}$ in $\left(\left(\genfrac{}{}{0ex}{}{[m]}{k}\right)\right)$ and characterize the extremal families achieving the upper bound. For $t=1$ and $m\ge k+1$, the method involves constructing a bijection between multiset family and set family while preserving the intersecting relation. For $t\ge 2$ and $m\ge 2k-t$, we employ a shifting operation, specifically the down-compression, which was initiated by Füredi, Gerbner and Vizer~(2016). These results extend the sum-type intersecting theorem for set families originally given by Hilton and Milner (1967).

11 pages