From c43e27dfc3418da034eb0601cbc557d61c4083a2 Mon Sep 17 00:00:00 2001
From: Marcin Chrzanowski <mc370754@students.mimuw.edu.pl>
Date: Thu, 25 Nov 2021 17:15:53 +0100
Subject: Reword partitioning

---
 mgr.tex | 47 ++++++++++++++++++++++++++++++++++-------------
 1 file changed, 34 insertions(+), 13 deletions(-)

(limited to 'mgr.tex')

diff --git a/mgr.tex b/mgr.tex
index 41d0941..b5bd246 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -734,17 +734,37 @@ answering the question in the promised time.
 Consider a set of tree vertices $W \subseteq V(T)$. We'll say that $W$ is
 \definedterm{LCA closed} if for every pair of vertices $v, w \in W$, it is the
 case that $\mathlca(v, w) \in W$ (note that one of $v$ or $w$ might be their
-LCA). We also require that the tree's root is in $W$ (just to ensure the
-partition we define next covers the whole tree).
+LCA).
 
-The \definedterm{subtree of $v$} is $v$ along with all its descendants.
-We also consider subtrees with holes: the \definedterm{subtree of $v$ with hole
-$w$} is the subtree of $v$ minus the subtree of $w$ (for $w$ a descendant of
-$v$).
+$W \subseteq V(T)$ is \definedterm{partition ready} if
 
-For an LCA closed set $W$ in tree $T$, we define the \definedterm{LCA partition
-with respect to $W$} to be a partition of $T$'s vertices into subtrees, subtrees
-with holes, and individual vertices created according to the following rules:
+\begin{enumerate}
+    \item it is LCA closed;
+    \item it contains the root of the tree;
+    \item\label{both-subtrees-property} for every $v \in W$, either it has descendants in $W$ in at most one
+        of its subtrees, or both of its children are elements of $W$.
+\end{enumerate}
+
+We will define the \definedterm{LCA partition with respect to $W$} for a
+partition ready subset $W$ of $T$'s vertices. The partition will assign each
+vertex to a unique part, and each part will be rooted in an element of $W$ (in
+particular, there will be as many parts as elements in $W$).
+
+Each part will be of one of three types:
+
+\begin{description}
+    \item[subtree] A \definedterm{subtree of $v$} is $v$ along with all its descendants;
+        it is rooted in $v$.
+    \item[subtree with hole] A \definedterm{subtree of $v$ with hole $w$} is the subtree of $v$
+        minus the subtree of $w$ (for $w$ a descendant of $v$); it is rooted in
+        $v$.
+    \item[singleton] A singleton vertex $v$, which is the root of such a part.
+\end{description}
+
+
+Now, for a partition ready set $W \subseteq V(T)$, the LCA partition of $T$ with
+respect to $W$ is a partition into subtrees, subtrees with holes, and
+singletons constructed according to the following rules:
 
 \begin{enumerate}
     \item If $v \in W$ is a maximal in $W$ with respect to the ancestor
@@ -756,10 +776,11 @@ with holes, and individual vertices created according to the following rules:
         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, let
-        $v_l$ and $v_r$ be $v$'s left and right child, respectively. Treat $v_l$
-        and $v_r$ as if they were in $W$ for the purposes of defining the
-        partition. Put $v$ into a singleton part on its own.
+    \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
+        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.
 \end{enumerate}
 
 Note that in the last rule, both $v_l$ and $v_r$ will either themselves be
-- 
cgit v1.2.3