Prove
Lemma 9. If the logical activities are balanced, then for every even set U of…Lemma 8 ([Pairings in a hierarchy]). Let B≥1 be a symmetric similarity on a…Proposition
We give a recursive splitting rule. A subproblem is an admissible odd arc J=(v_0,…,v_s) ; its exterior is its complementary arc in the full cycle. Choose a label P∈S_ v_0 ∩S_ v_s , and write a_i for the label of v_iv_ i+1 , 0≤i<s . Adjacent terms of this sequence are equal or adjacent in the tree. If s=1 , no cell is needed. For s≥3 , we find indices 0<p_1<p_2<s, p_1 odd, p_2 even, such that the three subarcs with successive endpoint pairs (v_0,v_ p_1 ), (v_ p_1 ,v_ p_2 ), (v_ p_2 ,v_s) are admissible. They and the exterior arc form the four sides of the new cell. We call these the first, middle, third, and exterior sides, respectively. We repeatedly use the following elementary fact about a tree. If a contiguous part of the label walk avoids P and its first and last labels are adjacent to P , these two labels coincide: the walk lies in a single component of the tree with P removed, and that component has just one node adjacent to P . The exterior is good. It suffices to make either the middle side short or both the first and third sides short. Either alternative immediately implies (i) and (ii), because the exterior is good. First ensure that some a_i equals P . If none does, a_0 and a_ s-1 are adjacent to P , because the endpoint sets contain P . The elementary tree fact gives a_0=a_ s-1 =Q for a neighbor Q of P . Replace P by Q , which also lies in both endpoint sets. We now distinguish the exhaustive possibilities below. Suppose a_i=P for an odd i . Set p_1=i and p_2=i+1 . The middle side is short. The first side's two endpoints contain P , as do the third side's two endpoints, so all three sides are admissible. Otherwise all occurrences of P have even indices. If their first index is i>0 , set p_1=i-1 and p_2=i . The prefix a_0,…,a_ i-1 avoids P , and its first and last labels are adjacent to P . They therefore equal the same neighbor Q . The first side's endpoints both contain Q , and the third side's endpoints both contain P . The middle side is short. Suppose the first occurrence is at 0 , but the last occurrence is at j<s-1 . Set p_1=j+1 and p_2=j+2 . The suffix a_ j+1 ,…,a_ s-1 avoids P and has its two end labels adjacent to P , so they equal one neighbor Q . The first side's endpoints contain P , the third side's endpoints contain Q , and the middle side is short. In the remaining case a_0=a_ s-1 =P . Set p_1=1 and p_2=s-1 . Both outer sides are short, and the middle side's endpoints both contain P . All indices satisfy. For example, in (b) the even index i is at least 2 , and in (c) the even index j is at most s-3 . The exterior is not good. The exterior is then long. At least one of its leaves lacks P in its fixed label set, since otherwise its two leaves would share P . Reverse the indexing of J if necessary so that this leaf is the exterior neighbor of v_0 . The exterior edge at v_0 cannot have label P . Since P∈S_ v_0 , the first edge of J must have label a_0=P . If a_ s-1 =P as well, choose p_1=1,p_2=s-1 . Both outer sides are short, and the middle side is admissible. Otherwise let t-1 be the last index with a_ t-1 =P . Thus 1≤t≤s-1 . The suffix a_t,…,a_ s-1 avoids P . Its first label is adjacent to P , and its last label is adjacent to P because P∈S_ v_s . Hence a_t=a_ s-1 =Q for the same neighbor Q of P . If t is even, set p_1=1,p_2=t . The first side is short. The middle side's endpoints both contain P , and the third side's endpoints both contain Q . The third side is good: if long, both its boundary edges have label Q , so both its leaves contain Q . If t is odd, set p_1=t,p_2=s-1 . The third side is short. The first side's endpoints both contain P , and the middle side's endpoints both contain Q . The first side is good because, if long, both its boundary edges have label P . The required strict inequalities follow from t≥2 in the even case and t≤s-2 in the odd case. In either case the first and third sides are good and at least one is short. This proves (i). The only opposite pair that can contain two long sides is the middle--exterior pair, and its other pair is good, proving (ii). Recursion and consistent diagonals. Start with any arc of length m-1 , whose exterior is the remaining single cycle edge. Its endpoints share that edge's label. Apply the splitting rule and recurse on each of the three subarcs whose length exceeds one, always using the original sets S_v and the complement in the original cycle as exterior. The three subpolygons have disjoint interiors, so all diagonals are noncrossing. Each recursive child has odd length and admissible endpoints by the construction. The splitting label P is only an auxiliary witness to admissibility; it does not constrain the color of the closing diagonal. Thus each diagonal can be colored once and the same color used on both sides. For an odd arc of length s , the resulting number of cells is (s-1)/2 : this is zero for s=1 , and a split into odd lengths s_1+s_2+s_3=s gives 1+∑_ i=1 ^ 3 (s_i-1)/(2)=(s-1)/(2). The root therefore gives (m-2)/2 cells. Each nonroot recursive subproblem that creates a cell has one closing diagonal, giving one fewer interior diagonals than cells. A direct implementation scans at most m labels in each of the (m-2)/2 nontrivial subproblems; the recursion also has m-1 short leaf arcs. Fixing total orders for any choices makes the construction deterministic, with O(m^2) label comparisons and polynomial bit cost.