Cross-intersecting integer sequences

Abstract

We call $(a_1,\dots ,a_n)$ an \emph{$r$-partial sequence} if exactly $r$ of its entries are positive integers and the rest are all zero. For $\mathbf{c}=(c_1,\dots ,c_n)$ with $1\le c_1\le \cdots \le c_n$, let $S_{\mathbf{c}}^{(r)}$ be the set of $r$-partial sequences $(a_1,\dots ,a_n)$ with $0\le a_i\le c_i$ for each $i$ in $\{1,\dots ,n\}$, and let $S_{\mathbf{c}}^{(r)}(1)$ be the set of members of $S_{\mathbf{c}}^{(r)}$ which have $a_1=1$. We say that $(a_1,\dots ,a_n)$ \emph{meets} $(b_1,\dots ,b_m)$ if $a_i=b_i\ne 0$ for some $i$. Two sets $A$ and $B$ of sequences are said to be \emph{cross-intersecting} if each sequence in $A$ meets each sequence in $B$. Let $\mathbf{d}=(d_1,\dots ,d_m)$ with $1\le d_1\le \cdots \le d_m$. Let $A\subseteq S_{\mathbf{c}}^{(r)}$ and $B\subseteq S_{\mathbf{d}}^{(s)}$ such that $A$ and $B$ are cross-intersecting. We show that $|A||B|\le |S_{\mathbf{c}}^{(r)}(1)||S_{\mathbf{d}}^{(s)}(1)|$ if either $c_1\ge 3$ and $d_1\ge 3$ or $\mathbf{c}=\mathbf{d}$ and $r=s=n$. We also determine the cases of equality. We obtain this by proving a general cross-intersection theorem for \emph{weighted} sets. The bound generalises to one for $k\ge 2$ cross-intersecting sets.

20 pages, submitted for publication, presentation improved

References in corpus (1)

• Intersecting families of sets and permutations: a survey

Cited by in corpus (2)

• A cross-intersection theorem for subsets of a set
• Cross-intersecting families of vectors