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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.