m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--mgr.tex23
1 files changed, 13 insertions, 10 deletions
diff --git a/mgr.tex b/mgr.tex
index 1bfba88..9328809 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -770,14 +770,14 @@ singletons constructed according to the following rules:
\item If $v \in W$ is a maximal in $W$ with respect to the ancestor
relation $<$ (i.e. there are no other elements of $W$ in the subtree of
$v$), then the subtree of $v$ is a part of the partition.
- \item If $v \in W$ has descendants that are in $W$ only in its left subtree,
- let $w$ be the highest such descendant (there is a unique highest
- descendant because $W$ is LCA closed). The subtree of $v$ with hole $w$
- is a part of the partition.
+ \item If $v \in W$ has descendants that are in $W$ only in its left child's
+ subtree, let $w$ be the highest such descendant (there is a unique
+ highest descendant because $W$ is LCA closed). The subtree of $v$ with
+ hole $w$ is a part of the partition.
\item Symmetrically if $v \in W$ only has descendants that are in $W$ in its
- right subtree.
- \item If $v \in W$ has descendants that are in $W$ in both its subtrees we
- know that $v$'s left and right child are also elements of $W$ by
+ right child's subtree.
+ \item If $v \in W$ has descendants that are in $W$ in both its children's
+ subtrees we know that $v$'s children are also elements of $W$ by
property \ref{both-subtrees-property} of being partition ready. Put $v$
into a singleton part on its own, all the other elements of its subtree
were assigned to parts when its children were handled.
@@ -796,8 +796,9 @@ 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.
+ \item\label{partition-ready-last-step} Let $W'''$ be $W''$ plus, for every
+ element of $W''$ that has elements of $W''$ in both its children's
+ subtrees, the element's both children.
\end{enumerate}
\begin{claim}
@@ -819,7 +820,9 @@ 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
+$W''$. The only reason we would need to add even more vertices after adding
+$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