A family of sets $\mathcal{F}$ is a union chain if each set in $\mathcal{F}$ of size at least $2$ is the union of two other sets in $\mathcal{F}$. That is, $X\in \mathcal{F}$ and $|X|\geq 2$, then $X=Y\cup Z$ for some $Y,Z\in \mathcal{F}$ and $Y,Z\neq X$.

Let $\mathcal{A}$ be a family of sets. Let $|\mathcal{A}|=n$ and $\left|\bigcup_{A\in \mathcal{A}} A\right|=m$.

What are some upper bounds for $|\mathcal{F}|$ in terms of $n$ and $m$, where $\mathcal{F}$ is the smallest union chain that contains $\mathcal{A}$? Is $|\mathcal{F}| = O(m+n)$?

The terminology comes from addition chain, but instead of addition we have set unions.

  • 1
    $\begingroup$ By binary division, each set in A having k elements can be represented as a union chain of about 2k many sets, so there is an upper bound on the sum of the sizes of the sets. Some savings can be realized by using shared sets of size 2,4,8 and so on. I would be surprised if O(n+m) is always achievable. Gerhard "Chain Isn't The Best Word" Paseman, 2020.05.12. $\endgroup$ – Gerhard Paseman May 13 '20 at 1:18

Your Answer

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

Browse other questions tagged or ask your own question.