Reword partition readiness

1 files changed, 15 insertions, 14 deletions

diff --git a/mgr.tex b/mgr.tex
index 9328809..7bc1ef2 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -783,9 +783,9 @@ singletons constructed according to the following rules:
         were assigned to parts when its children were handled.
 \end{enumerate}
 
-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
+If $W$ is not parition ready, we will define 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
@@ -809,9 +809,9 @@ Take a set of $m$ tree vertices $W$ and consider the following procedure:
 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.
+vertices still needed to be added to arrive at a partition ready set. For now
+assume that only $O(m)$ vertices were added in step
+\ref{partition-ready-lca-step}, this 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
@@ -825,11 +825,11 @@ $v_l$ would be if $v_l$ had descendants in both its children's subtrees in
 $W'''$. First let's show that it has descendants in $W''$ in at most 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$.
+topmost members of $W''$ of its children's subtrees. 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}
 
@@ -853,7 +853,7 @@ of vertices such that $\infixtable[v_1] < \ldots < \infixtable[v_m]$.
 
 This may be proved by a simple case analysis.
 
-\begin{observation}
+\begin{observation}\label{lca-observation}
     Consider two tree vertices, $u, w \in V(T)$ with $\infixtable[u] <
     \infixtable [w]$, and their least common ancestor
     $v$. Then $\infixtable[u] \leq \infixtable[v] \leq \infixtable[w]$.
@@ -865,8 +865,9 @@ example, if $v = u$, we have that $\infixtable[u] = \infixtable[v] <
 and $w$ must be in its right subtree. Thus an infix walk over $T$ will first
 visit $u$, then $v$, and then $w$.
 
-Now, once $W$ has been sorted by in-order numbers, we can complete our
-computation in time $O(m)$. Consider the following set of vertices:
+Now, once $W$ has been sorted by in-order numbers (which takes time $O(m \log
+m)$ using a standard sorting algorithm), we can complete our computation in time
+$O(m)$. Consider the following set of vertices:
 
 \begin{equation*}
     U := \{ v \;|\; v = LCA(v_i, v_{i+1}) \text{ for $1 \leq i \leq m - 1$} \}