A coding problem for pairs of subsets

Bela Bollobas; Zoltan Furedi; Ida Kantor; G. O. H. Katona; Imre Leader

paper

A coding problem for pairs of subsets

arXiv:1403.3847

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.

11 pages (minor changes, and new citations added)