In the context of some other construction (which is irrelevant here), I was looking for a way to generate a collection "orthogonal partitions" on a set of nodes with a fixed and uniform set size, and I wanted it to be scalable in the number of partitions and nodes.
Example
On the set $\{0,...,8\}$ one can easily find such an arrangement by putting the numbers into a 3x3 grid (with "wrap around", like a torus), and separately take the rows, columns and both diagonals, getting the following 4 "orthogonal set covers / partitions":
- $\{\{0,1,2\},\{3,4,5\},\{6,7,8\}\}$
- $\{\{0,3,6\},\{1,4,7\},\{2,5,8\}\}$
- $\{\{0,4,8\},\{1,5,6\},\{2,3,7\}\}$
- $\{\{2,4,6\},\{1,3,8\},\{0,5,7\}\}$
which satisfy the desired properties (uniform + orthogonal partitions).
Research I did
I figured out that this is connected to variants of combinatorial designs. I found MOLS, the Wikipedia article also shows how to convert a MOLS via Orthogonal Arrays into a "net", which looks like (a subclass of) what I want. I also found this code and learned how to easily generate MOLS(n) for prime n.
So for a prime $n \in \mathbb{N}$, I can generate $(n-1)$ MOLS and transform those into $(n+1)$ different partitions $n^2$ nodes, using sets of size $n$, so that the partitions are "orthogonal" in the sense above.
I also randomly stumbled on the social golfer problem, which finally led me to resolvable group divisible designs - that looks like exactly the kind of definition I was looking for.
So apparently, what I am actually interested in, are RGDDs with $\lambda=1$ (i.e. intersect at most in 1 element between sets of different partitions), and more precisely, families of RGDDs with fixed and singleton $K$ (i.e. uniform block size), but variable $\nu$ (i.e. number of elements).
Questions
My background is computer science, I have no deep background in combinatorics or statistics (where apparently most "designs" are used), and there is a confusingly large number of related concepts and names for what I'm looking for. So I wonder if I found everything useful and/or interesting about existence and construction of such sets.
Is there something known about effectively and systematically constructing RGDDs of that type for sets different from the MOLS-based approach / finite field constructions for prime numbers?
Is there a already working algorithm or implementation for generating RGDDs of the type I want which also directly works with powers of primes?
What is known about RGDDs for (powers of) composite numbers?
Mostly I am interested in "constructable" results (ideally, with constructions that don't need me to be an expert in combinatorics or finite field theory), but "(non)-existence" results are also good to know for orientation.
Furthermore, I believe that I managed to build a recursive construction that takes a set of "base RGDDs" (e.g. obtained from MOLS), and lifts them to larger node sets. For example, for the "base" 3, I take the RGDD in the example above (which is the solution for size $3^2$) and lift it to produce for any $i\in\mathbb{N}$, an RGDD with $3^i$ nodes and $3^{i-1}$ groups, each with $3^{i-1}$ blocks of size 3.
I have not proved it yet (just ran multiple tests for different parameters), but at least by Theorem 2.2 of that paper what I am doing looks at least plausible and like an iterated "RGDD multiplication" (at least it matches with the expected parameters of the RGDD according to the theorem), in fact it is actually "exponentiation".
- Is this known/folklore/trivial, or is there already some paper explaining in more detail how to practically generate such families, or a library/implementation that can do that? Or would it be interesting if I write up the concrete algorithm I came up with and try proving it? In fact, I found the mentioned paper/theorem after having my construction, so I am not yet sure how/whether it relates to the actual steps in the proof.
The field-based construction might yield the complete set of partitions for prime powers ($p^k+1$ should be possible, right? from $p^k{-}1$ MOLS($p$)), but I cannot fully understand or implement it, and have not seen it implemented in full generality in the wild, and it results in increasingly larger block sizes anyway, while I want to keep mine fixed). So I thought that maybe a different construction for a different variation could be interesting.
If this is something new and non-trivial, this might motivate me to try fleshing it out and writing it up (and maybe to try to generalize it even further).
Would be happy to get some gentle orientation in the sea of combinatorics that I accidentally stumbled into!