The duplicate-leaf parse-word conjecture for binary trees

Let T1T_1' and T2T_2' be (n1)(n-1)-leaf binary trees. Let 1in11 \leq i \leq n-1, and let T1T_1 and T2T_2 be the nn-leaf trees obtained from T1T_1' and T2T_2' by duplicating leaf ii. A parse word is a word that parses both trees according to the paper's labeling rule. Duplicate-leaf parse-word conjecture. There exists a parse word w=w1wnw = w_1 \cdots w_n of T1T_1 and T2T_2 such that wi=wi+1w_i = w_{i+1}. This would reduce the search for parse words by showing that duplicated leaves can receive the same letter, but the supplied text gives no resolution.

Sources & referencesView supporting material

Primary source

Bobbe Cooper, Eric Rowland and Doron Zeilberger, “Toward a language theoretic proof of the four color theorem”, arXiv:1006.1324 (2011).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.