Prove part of partition readiness computation

1 files changed, 44 insertions, 16 deletions

diff --git a/mgr.tex b/mgr.tex
index 195e6ba..b414db7 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -783,22 +783,50 @@ singletons constructed according to the following rules:
         were assigned to parts when its children were handled.
 \end{enumerate}
 
-Note that in the last rule, both $v_l$ and $v_r$ will either themselves be
-elements of $W$ or will have descendants in $W$ in only one of their subtrees.
-In the first case, we will have already handled them. Otherwise, we will handle
-them with a rule different than the last one, thus only one part will be added
-to the partition for each of them. In particular, each element of $W$ will
-contribute only a constant number of parts to the partition (one part if handled
-with one of the first three rules, three parts if handled with the last one).
-
-To see that indeed, for example $v_l$, won't need to be handled with rule 4, if
-it wasn't in $W$ but had descendants from $W$ in both its subtrees, then $W$
-wouldn't have been LCA closed.
-
-Thus the partition covers the entire tree with $O(|W|)$ parts.
-
-If $W$ is not LCA closed, we will call the LCA partition with respect to $W$
-simply the partition with respect to $W$'s LCA closure.
+If $W$ is not parition ready, we will call the LCA partition with respect to $W$
+the partition with respect to the minimal partition ready set that contains $W$.
+Skipping ahead, the LCA partition of the set of vertices relabeled in a
+relabeling question will be the partition we alluded to at the end of the
+previous section. We promised that this partition will have $O(m)$ parts, so we
+must show that for a set $W$, the minimal partition ready set containing it is
+of size $O(|W|)$.
+
+Take a set of $m$ tree vertices $W$ and consider the following procedure:
+
+\begin{enumerate}
+    \item Let $W'$ be $W$ with the tree's root added.
+    \item\label{partition-ready-lca-step} Let $W''$ be the LCA closure of $W'$.
+    \item\label{partition-ready-last-step} Let $W'''$ be $W''$ plus, for every element of $W''$ that has
+        elements of $W''$ in both its subtrees, the element's both children.
+\end{enumerate}
+
+\begin{claim}
+    The above procedure produces the minimal parition ready set containing $W$
+    and each step adds at most $O(m)$ new vertices.
+\end{claim}
+
+By defintition of LCA closure, $W''$ above is the smallest LCA closed set
+containing $W$ and the tree's root. Step \ref{partition-ready-last-step} adds at
+most $2|W''|$ new vertices, we will now prove that these are exactly the only
+vertices still needed to be added to arrive at a partition ready set. That only
+$O(m)$ vertices are added in step \ref{partition-ready-lca-step} will be proved in
+the next section.
+
+It's easy to see that $W'''$ is still LCA closed. It is obvious that it is
+necessary to add at least all the vertices added in step
+\ref{partition-ready-last-step}, otherwise property \ref{both-subtrees-property}
+of partition readiness won't be satisfied. What we will show is that no other
+new vertices need to be added. Take $v \in W''$ that had descendants in $W''$ in
+both its subtrees, let $v_l$ and $v_r$ be its left and right child,
+respectively. Without loss of generality, suppose $v_l$ was not an element of
+$W''$. Then we claim that it has descendants in $W''$ in only one of its
+subtrees. Indeed, if it did have descendants from $W''$ in both its subtrees,
+$W''$ wouldn't have been LCA closed -- $v_l$ would have been the LCA of the
+topmost members of $W''$ of its left and right subtrees. Note that newly added
+elements of $W'''$ can appear only underneath vertices that were originally in
+$W''$, so if $v_l$ didn't have an element of $W''$ in one of its subtrees, then
+it also doesn't have elements of $W'''$ in that subtree. Thus $W'''$ is indeed
+the minimal partition ready set containing $W$.
 
 \subsection{Computing the LCA closure}\label{computing-closure}