# Smallest disjoint union chain containing a sequence of sets

Let $$\mathcal{A}=\{A_1,\ldots,A_n\}$$ be a family of sets, we have the property that $$A_1=\emptyset$$, and one can obtain $$A_i$$ from $$A_{i-1}$$ by adding or deleting a single element.

A family $$\mathcal{B}$$ is a disjoint union chain, if every set in $$\mathcal{B}$$ of size at least $$2$$ can be expressed as a union of two disjoint non-empty sets in $$\mathcal{B}$$.

The smallest disjoint union chain containing $$\mathcal{A}$$ has size $$O(n\log n)$$.

To see this, view a set $$A_i$$ as leaves of a balanced binary tree. Going from $$A_i$$ to $$A_{i+1}$$, we maintain it dynamically using rotations. For each internal node, the set of leaves would be an element in $$\mathcal{B}$$. Each rotation changes only 2 sets, and there are only $$O(\log n)$$ rotations. Similarly for insertion and deletions too.

Is there an example where this upper bound is tight?

• A assume by "achieved" you mean "is tight"? What examples have you tried? It isn't tight if e.g. $A_i \subset A_{i+1}$ for each $i$. What about if $\cal A$ is the set of all $n={2k \choose i}$ size-$i$ subsets of $\{1,2,\ldots,k\}$, for some $k$ and $i=(1-\epsilon)k/2$ for some $\epsilon>0$? – Neal Young Oct 27 '18 at 19:52
• Yes, I do mean tight. Fixed. In your case, we can let $\mathcal{B}$ to be the family of subsets of size ${2k \choose i/2}$, and $\mathcal{A}$. I thought about what if I first add elements then delete all elements, which also has disjoint union chain of $O(n)$. – Chao Xu Oct 28 '18 at 1:44
• is "we can let $\cal B$ to be the family of subsets of size $2k \choose i/2$, and $\cal A$" correct? You need smaller sets in $\cal B$ too, don't you? But in any case even if you put in all sets of size $i$ or less in $\cal B$, I think that would still be $O(n \sqrt{\log n})$ at worst. Maybe your approach gives $O(n)$ for that $\cal A$? I also considered $\cal A$ of the form $A_i = \{i, i+1,\ldots,(i+k)\bmod n\}$ for any fixed $k$ and $n$, and I believe that can be done with $|{\cal B}| = O(n)$. Do you know any $\cal A$ that can't be done with $|{\cal B}|=O(n)$? – Neal Young Oct 28 '18 at 1:54
• Maybe fix some $k$ and take $A_i = \{1,\ldots,i\}$ for $i\le k$, and for larger $i$ obtained $A_{i+1}$ from $A_i$ by deleting a random element from $A_i$ and adding $i+1$? (Or, to be more precise, for odd $i$ obtain $A_{i+1}$ from $A_i$ by deleting a random element. For even $i$ obtain $A_{i+1}$ from $A_i$ by adding $i+1$.) – Neal Young Oct 28 '18 at 1:59
• Sorry. Yes, I also need smaller sets. It should be "family of subsets of size at most ${2k \choose i/2}$, and $\mathcal{A}$" Then you get $O(n)$ at worst. Unfortunately, I do not know of any $\mathcal{A}$ that can't be done with $|\mathcal{B}|=O(n)$. Indeed your suggestion is a reasonable approach to try, I have yet to figure out a good way to analyze it. – Chao Xu Oct 28 '18 at 8:49