1
$\begingroup$

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

$\endgroup$
9
  • $\begingroup$ $C_k$ does not depend on $k$. $k$ is just a distinguisher for the $C$s, ie, $\mid \{ C_1, .., C_{se} \} \mid = se$ $\endgroup$
    – petern0691
    Nov 15, 2022 at 12:10
  • 1
    $\begingroup$ 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. $\endgroup$ Nov 15, 2022 at 12:17
  • 1
    $\begingroup$ 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$. $\endgroup$ Nov 15, 2022 at 13:04
  • 1
    $\begingroup$ 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. $\endgroup$ Nov 15, 2022 at 14:50
  • 1
    $\begingroup$ 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$. $\endgroup$ Nov 15, 2022 at 16:38

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.