Intersecting families, signed sets, and injection

Abstract

Let $k,r,n\ge 1$ be integers, and let ${\S }_{n,k,r}$ be the family of $r$-signed $k$-sets on $[n]=\{1,\dots ,n\}$ given by $${\mathcal{S}}_{n,k,r}=\{\{(x_1,a_1),\dots ,(x_k,a_k)\}:\{x_1,\dots ,x_k\}\in (\genfrac{}{}{0ex}{}{[n]}{k}),a_1,\dots ,a_k\in [r]\}.$$ A family $\mathcal{A}\subseteq {\S }_{n,k,r}$ is \emph{intersecting} if $A,B\in \mathcal{A}$ implies $A\cap B\ne \varnothing$. A well-known result (first stated by Meyer and proved using different methods by Deza and Frankl, and Bollobás and Leader) states that if $\mathcal{A}\subseteq {\mathcal{S}}_{n,k,r}$ is intersecting, $r\ge 2$ and $1\le k\le n$, then $$|\mathcal{A}|\le r^{k-1}\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right).$$ We provide a proof of this result by injection (in the same spirit as Frankl and Füredi's and Hurlbert and Kamat's injective proofs of the Erdős--Ko--Rado Theorem, and Frankl's and Hurlbert and Kamat's injective proofs of the Hilton--Milner Theorem) whenever $r\ge 2$ and $1\le k\le n/2$, leaving open only some cases when $k\le n$.

7 pages; differs from the journal version in that reference 7 has been added