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

Improve this question
$\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
    Commented 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$
    – Peter Taylor
    Commented 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$
    – Peter Taylor
    Commented 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$
    – Peter Taylor
    Commented 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$
    – Max Alekseyev
    Commented Nov 15, 2022 at 16:38

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .