Abstract
Let X be an n-element finite set and k a positive an integer less than or equal to n/2. Suppose that {A1,A2} and {B1,B2} are pairs of disjoint k-element subsets of X (that is, |A1|=|A2|=|B1|=|B2|=k, the intersection of A1 and A2 is empty, and so is the intersection of B1 and B2).
Define the distance of these pairs by d({A1,A2},{B1,B2}) to be the min{|A1-B1|+|A2-B2|,|A1-B2|+|A2-B1|}. This is the minimum number of elements of the union of A1and A2 that one has to move to obtain the other pair {B1,B2}.
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 approaches infinity.
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.