Extremal Uniquely Resolvable Multisets

Abstract

For positive integers $n$ and $m$, consider a multiset of non-empty subsets of $[m]$ such that there is a \textit{unique} partition of these subsets into $n$ partitions of $[m]$. We study the maximum possible size $g(n,m)$ of such a multiset. We focus on the regime $n\le 2^{m-1}-1$ and show that $g(n,m)\ge \Omega (\frac{nm}{{\log }_{2}n})$. When $n=2^{cm}$ for any $c\in (0,1)$, this lower bound simplifies to $\Omega (\frac{n}{c})$, and we show a matching upper bound $g(n,m)\le O(\frac{n}{c}{\log }_2(\frac{1}{c}))$ that is optimal up to a factor of ${\log }_2(\frac{1}{c})$. We also compute $g(n,m)$ exactly when $n\ge 2^{m-1}-O(2^{\frac{m}{2}})$.

arXiv comment12 pages, 4 figures. Accepted to SIAM Journal on Discrete Mathematics (SIDMA)