# Does a disjoint set forest have multiple distinct “upwards closed” partitions?

The following is an excerpt from a powerpoint on the role of the inverse Ackermann function in determining the complexity of path compression.

• Dissection of a disjoint set forest $F$ with node set $X$

• Partition of $X$ into “top part” $X_t$ and “bottom part” $X_b$ so that top part $X_t$ is “upwards closed”

• i.e. $x∈X_t ⇒$ every ancestor of $x$ is in $X_t$ also

Using the definition of a "upwards closed" partition mentioned above, aren't there several distinct $X_t$ partitions that meet this criteria? Consider the following partitions that all appear to meet the aforementioned definition:

• The first distinct partition is only the root.
• The second distinct partition is the root and its children
• The third distinct partition is the root, its children and its grandchildren
• The remaining distinct partitions consist of the root and up to the $n^{th}$ generation of children

Do there exist multiple distinct "upwards closed" partitions in a disjoint set forest?

-

The next few slides basically argue that you can analyze the effect of a series of path compressions on a forest $F$ by analyzing a corresponding sequence of path compressions in an arbitrary dissection of $F$. Then later, the slides show that by choosing a particular dissection (and arguing recursively), one obtains the inverse-Ackermann amortized time bound.