The duplicate-leaf parse-word conjecture for binary trees

About 16 years old · traced to

Let T1′T_1' and T2′T_2' be (n−1)(n-1)-leaf binary trees. Let 1≤i≤n−11 \leq i \leq n-1, and let T1T_1 and T2T_2 be the nn-leaf trees obtained from T1′T_1' and T2′T_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=w1⋯wnw = 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.

References

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.