The path-tree parse-word and level-restriction conjecture

Let n4n \geq 4, and let T1T_1 and T2T_2 be nn-leaf path trees such that leaf 11 is on level 11 in T1T_1 and leaf nn is on level 11 in T2T_2. A pair is mutually crooked if it cannot be obtained by duplicating a leaf in a pair of (n1)(n-1)-leaf trees, and weakly mutually crooked if it cannot be obtained by triplicating a leaf in a pair of (n2)(n-2)-leaf trees. A parse word is a word that parses both trees. Path-tree parse-word and level-restriction conjecture. The following assertions hold: (i) if T1T_1 and T2T_2 have no parse word of the form 00v00v or v00v00, then they have a unique parse word up to permutation of the alphabet; (ii) if they have no parse word of the form 00v00v and are mutually crooked, then they have a parse word of the form 01v0001v00; (iii) if they have no parse word of the form 00v00v, then the only possibilities for the pair of levels of leaves 22 in T1T_1 and n1n-1 in T2T_2 are (2,3)(2,3) and (k,2)(k,2) for some k2k \geq 2; if they are weakly mutually crooked, one has 2k42 \leq k \leq 4, and if they are mutually crooked, one has 2k32 \leq k \leq 3. These claims are proposed as tools toward proving that every pair of binary trees has a parse word; 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.