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?