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](https://stackoverflow.com/questions/74334415/from-9-sets-of-12-elements-arrange-12-groups-of-the-9-elements-selecting-1-ele)


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



Recombining set elements with no duplicated pairing of elements
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](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/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.


