Minimum for combinatorial sortingproblem

Question

I'm stuck with a combinatorial problem, maybe one of you can help me out, thanks in advance. So heres the problem:

Consider tuples $(i,j)\in \{1,...,N_1\}\times\{1,....,N_2\}=A$. Let $S_1,...,S_x$ be a disjoint decomposition of $A$ which fulfils the following:

1. $(i,j),(k,l)\in S_m$ then $(i,l),(k,j) \in S_m$.
2. $(i,j),(k,l)\in S_m$ then: If $i \neq k$ $\forall o \neq m$ and $(i,\ast)\in S_o$ $\Rightarrow (k,\ast')\neq S_o$ ($\ast, \ast'$ arbitrary elements).
3. $\forall S_m:$ $\vert\{i \in \mathbb{N} \mid (i,\ast) \in S_m\}\vert < n_1$ and $\vert\{i \in \mathbb{N} \mid (\ast,i) \in S_m\}\vert < n_2$.

I'm looking for a minimal bound on $x$ dependent of $N_1, N_2, n_1$ and $n_2$. An upper bound is obviously given by $N_1 \cdot N_2$. For an easy to see lower bound I get $\frac{N_1}{n_1} \cdot \frac{N_2}{n_1}$ by using the third condition. But I think there should be a better lower bound, because I do not use the second condition.

Thank you for any help and sorry for any language mistakes.

Answer 1

Too long for a comment:

I imagine this is a ridiculously hard problem, since a special case of it relates to finding a large set of mutually orthogonal Latin squares (MOLS), which is an open problem.

Specifically, suppose that $N_1=n_1^2$, and that $n_2=1$. I claim that the lower bound of $(N_1/n_1)\times (N_2/n_2)=n_1\cdot N_2$ can be obtained if and only if there exists an set of $(N_2-2)$ MOLS with dimensions $n_1\times n_1$.

I can illustrate the "only if" part of this claim by showing how to construct your partition given an MOLS of two Latin squares with order $3$:

Given: Two MOLS of order $3$:

Square 1   Square 2
 1 2 3      1 2 3
 2 3 1      3 1 2
 3 1 2      2 3 1

Output: A partition of the $3^2\times (2+2)=9\times 4$ rectangle $A$ into "combinatorial rectangles" of dimensions at most $3\times 1$:

1 1 1 2 2 2 3 3 3   <--- First row is n_1 contiguous blocks
1 2 3 1 2 3 1 2 3   <--- Each group in second row consists of n_1 items, spaced n_1 apart.
1 2 3 2 3 1 3 1 2   <--- The entries of square 1, read left to right, top to bottom
1 2 3 3 1 2 2 3 1   <--- The entries of square 2, read left to right, top to bottom

More generally, I think your problem might relate to "mutually orthogonal Latin rectangles," but this is getting out of my depth.