Pairs of Disjoint $q$-element Subsets Far from Each Other

Abstract

Let $n$ and $q$ be given integers and $X$ a finite set with $n$ elements. The following theorem is proved for $n>n_0(q)$. The family of all $q$-element subsets of $X$ can be partitioned into disjoint pairs (except possibly one if $n\choose q$ is odd), so that $|A_1\cap A_2|+|B_1\cap B_2|\leq q$, $|A_1\cap B_2|+|B_1\cap A_2| \leq q$ holds for any two such pairs $\{ A_1,B_1\} $ and $\{ A_2,B_2\} $. This is a sharpening of a theorem in [2]. It is also shown that this is a coding type problem, and several problems of similar nature are posed.