# Recombining set elements with no duplicated pairing of elements

This question arises from a request for an algorithm to do such, from 9 sets of 12 elements, arrange 12 groups of the 9 elements, selecting 1 element from each set

Given a set, $$S$$, of sets, $$S_i$$, $$\mid S\mid = s$$ where:

$$\forall S_i \in S, \mid S_i\mid = e$$, all sets in $$S$$ have the same cardinality, $$e$$, and $$e > 1$$

$$\forall S_i, S_j \in S, S_i \cap S_j = \phi, i \ne j$$, all sets in $$S$$ are pairwise disjoint

By choosing one element from each $$S_i \in S$$ create a new set $$C_k$$, and hence $$\mid C_k\mid = s$$.

Let $$P_k = \{ \{c_p, c_q\} : c_p, c_q \in C_k, p \ne q \}$$, $$P$$ is the set of binary subsets of $$C$$.

Do there exist $$C_k, k = 1$$ to $$se$$ such that $$l, m = 1$$ to $$se$$, $$P_l \cap P_m = \phi, l \ne m$$?

My conjecture is that for the $$se$$ sets, $$C_k$$, to exist, then necessarily $$s \le e$$ and $$e$$ is prime.

How might this be proved, or disproved (if there is no readily findable counter example)?

Apologies in advance if this is a known result. If so, please provide a reference. (It has been a very long time since I have done any formal math and I am a very bit "rusty".)

[EDIT - CORRECTION] $$e$$ needs to be prime, not $$s$$ - corrected above

• $C_k$ does not depend on $k$. $k$ is just a distinguisher for the $C$s, ie, $\mid \{ C_1, .., C_{se} \} \mid = se$ Commented Nov 15, 2022 at 12:10
• In essence this is a design problem to select $se$ vectors from $\mathbb{Z}_e^s$ such that the minimum Hamming distance is $s-1$. The Singleton bound requires $s \le e$, which answers half of the question. Commented Nov 15, 2022 at 12:17
• The edited question has easy counterexamples: take $s=2$, then $P_k = \{C_k\}$ so you can take all $e^2$ possible $C_k$. This gives a counterexample for any composite $e$. Commented Nov 15, 2022 at 13:04
• For $s=4$, a pair of mutually orthogonal $e \times e$ Latin squares allows the construction of a solution, so the existence of $4 \times 4$ Graeco-Latin squares gives a counter-example to both the original and the corrected question with $s=e=4$. Using a compact notation we can take the $S_i$ to be 0123 4567 89AB CDEF and e.g. $C_k$ as 048C 059D 06AE 07BF 149F 158E 16BD 17AC 24AD 25BC 268F 279E 34BE 35AF 369C 378D. Commented Nov 15, 2022 at 14:50
• I'd say this problem is more about codes than designs. Essentially it asks for $e$-ary code of length $s$ and distance $s-1$. Commented Nov 15, 2022 at 16:38

Let $$\Sigma$$ be an set of cardinality $$e$$. Then this problem is equivalent to selecting $$se$$ vectors from $$\Sigma^s$$ such that the minimum Hamming distance is $$s−1$$. (To see this, take $$S_i = \{i\} \times \Sigma$$). We could also phrase it as $$\Sigma$$ being an alphabet of cardinality $$s$$ and selecting $$se$$ words of length $$s$$ over the alphabet such that the minimum Hamming distance is $$s−1$$.
The Singleton bound on cardinalities of sets of words with a minimum Hamming distance requires $$s \le e$$, which answers half of the question.
So since we can assume that $$s \le e$$, it's interesting to address the more restrictive problem of selecting $$e^2$$ words of length $$s$$ with minimum Hamming distance $$s-1$$. This is equivalent to finding $$s-2$$ mutually orthogonal Latin squares: label both the cells and the rows and columns of the Latin squares with $$\Sigma$$. Note in particular the construction for finite fields which gives solutions when $$e$$ is a prime power.