3
$\begingroup$

Let $C_1,\dots, C_m$ be a family of ordered set partitions of $[n]$ with exactly $k$ blocks.

Write $C_i = \{B_{i1}, \dots, B_{ik}\}$ for $i=1,\dots, m$ where $B_{ij}$ are the blocks of the ordered set partition $C_i$.

Suppose this family also has the property that for each $j=1,\dots, k$

$$B_{1j} \cup \cdots \cup B_{mj}$$

is also a partition of $[n]$

Can one determine the maximal number of members in such a family $m$, or at least a decent upper bound on $m$?

Edit:

It might also be worth noting that if we take $k=n$, then $m=n$ since this would be equivalent to the existence of a latin square. I am in particular interested in the case $k=2$.

$\endgroup$
4
$\begingroup$

We have $$mn=\sum_i\sum_j |B_{ij}|=\sum_j\sum_i |B_{ij}|=kn,$$ thus $m=k$.

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

Answer: $m=k$.

Put indeed your blocks $B_{ij}$ in a $m\times k$ array and then "read" this array:

-- row-wise: any element of $[n]$ appears then $m$ times.

-- column-wise: any element of $[n]$ appears then $k$ times.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 26 seconds slower than Fedor, but my answer is better, does not use multiplication :) $\endgroup$ – Richard Apr 9 '19 at 17:09
  • $\begingroup$ you actually multiply 1 by $m$ and by $k$ :) $\endgroup$ – Fedor Petrov Apr 9 '19 at 17:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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