# A coding problem for pairs of subsets

Research paper by **Bela Bollobas, Zoltan Furedi, Ida Kantor, G. O. H. Katona, Imre Leader**

Indexed on: **12 May '14**Published on: **12 May '14**Published in: **Mathematics - Combinatorics**

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join for free

#### Abstract

Let $X$ be an $n$--element finite set, $0<k\leq n/2$ an integer. Suppose that
$\{A_1,A_2\} $ and $\{B_1,B_2\} $ are pairs of disjoint $k$-element subsets of
$X$ (that is, $|A_1|=|A_2|=|B_1|=|B_2|=k$, $A_1\cap A_2=\emptyset$, $B_1\cap
B_2=\emptyset$). Define the distance of these pairs by $d(\{A_1,A_2\}
,\{B_1,B_2\})=\min \{|A_1-B_1|+|A_2-B_2|, |A_1-B_2|+|A_2-B_1|\} $. This is the
minimum number of elements of $A_1\cup A_2$ one has to move to obtain the other
pair $\{B_1,B_2\}$. Let $C(n,k,d)$ be the maximum size of a family of pairs of
disjoint subsets, such that the distance of any two pairs is at least $d$.
Here we establish a conjecture of Brightwell and Katona concerning an
asymptotic formula for $C(n,k,d)$ for $k,d$ are fixed and $n\to \infty$. Also,
we find the exact value of $C(n,k,d)$ in an infinite number of cases, by using
special difference sets of integers. Finally, the questions discussed above are
put into a more general context and a number of coding theory type problems are
proposed.