Anticlusters and Intersecting Families of Sets and $t$-valued Functions

Abstract

It is shown that if $[n]=X_1\cup X_2\cup \cdots \cup X_l$ is a partition of $[n]$ and if $S_t$ is a family of $t$-valued functions intersecting on at least one element of $k$ (circularly) consecutive blocks, then $|S_t|<t^{n-k}$. If given $a_1<a_2<\cdots <a_y\le l$, ${\acute{S}}_t$ is a family of $t$-valued functions intersecting on at least one element of $X_{a_1+m},X_{a_2+m},\dots ,X_{a_k+m}$ for some $m$ with $1-a_1\le m\le n–a_k$, then $|{\acute{S}}_t|\le t^{n-k}$. Both these results were conjectured by Faudree, Schelp, and Sós [FSS]. The main idea of our proofs is that of anticlusters introduced by Griggs and Walker [GW] which we discuss in some detail. We also discuss several related intersection theorems about sets, $2$-valued functions, and $t$-valued functions.