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

<p>A family <span class="math-container">$\mathcal{B}$</span> is a <em>disjoint union chain</em>, if every set in <span class="math-container">$\mathcal{B}$</span> of size at least <span class="math-container">$2$</span> can be expressed as a union of two disjoint non-empty sets in <span class="math-container">$\mathcal{B}$</span>.</p>

<p>The smallest disjoint union chain containing <span class="math-container">$\mathcal{A}$</span> has size <span class="math-container">$O(n\log n)$</span>.</p>

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

<p>Is there an example where this upper bound is tight?</p>

CC BY-SA 4.0
2018-10-27T19:52:08.077Z
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
CC BY-SA 4.0
2018-10-28T01:44:32.347Z
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
CC BY-SA 4.0
2018-10-28T01:54:27.320Z
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
CC BY-SA 4.0
2018-10-28T01:59:41.280Z
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
CC BY-SA 4.0
2018-10-28T08:49:31.280Z
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
<co.combinatorics>
Smallest disjoint union chain containing a sequence of sets
Chao Xu
# Smallest disjoint union chain containing a sequence of sets

(Asked by: username_0 on 2018-10-22)

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?

**Tags:** co.combinatorics

> **Comments:**
> **username_1**: 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$?  
> **username_0**: 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)$.  
> **username_1**: 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)$?  
> **username_1**: 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$.)  
> **username_0**: 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.  

---

## 0 answers

