2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – Neal Young Oct 27 '18 at 19:52
  • $\begingroup$ 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)$. $\endgroup$ – Chao Xu Oct 28 '18 at 1:44
  • $\begingroup$ 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)$? $\endgroup$ – Neal Young Oct 28 '18 at 1:54
  • $\begingroup$ 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$.) $\endgroup$ – Neal Young Oct 28 '18 at 1:59
  • $\begingroup$ 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. $\endgroup$ – Chao Xu Oct 28 '18 at 8:49

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.