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$.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
4
$\begingroup$

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

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.

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

You must log in to answer this question.

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