Common Parse Words for Rooted Tree Pairs

Definitions and mathematical statement

The supplied record asks about common parse words for pairs of rooted trees. It does not specify the admissible class of trees, their leaf ordering and correspondence, the label alphabet, or the parsing rules. Consequently, the following is a conditional formulation template, not a complete formalization of the intended conjecture.

Suppose that the intended trees $T_1,T_2$ have the same finite number $n\geq 2$ of leaves, with specified ordered leaves $\ell^{(k)}_1,\ldots,\ell^{(k)}_n$ in $T_k$, for $k\in\{1,2\}$. These finiteness, ordering, and correspondence conventions require confirmation from the source. Write $p_k(v)$ for the parent of a nonroot vertex $v$ in $T_k$. Under the usual genealogical interpretation, two distinct vertices are siblings if they have the same parent, and a vertex $u$ is an uncle of $v$ if $u$ is a sibling of $p_k(v)$. All parent expressions must be defined. Let $U_k(i)$ mean that either $\ell^{(k)}_i$ is an uncle of $\ell^{(k)}_{i+1}$, or conversely. Define \[ I(T_1,T_2)=\{i\in\{1,\ldots,n-1\}:U_1(i)\land U_2(i)\}. \] The record describes a pair as not mutually crooked when some consecutive leaves have an uncle--nephew relationship in both trees; under the preceding conventions, this means $I(T_1,T_2)\neq\varnothing$. The record does not clarify whether the uncle--nephew orientation must agree in the two trees.

For an intended label alphabet $A$, let $\mathcal P(T_k)\subseteq A^n$ denote the words that parse $T_k$ according to the intended parsing rules. A common parse word is an element of $\mathcal P(T_1)\cap\mathcal P(T_2)$. This notation leaves the missing alphabet and parsing rules unresolved; it does not define a particular parsing system.

An existential reading of the question is: for every admissible tree pair $(T_1,T_2)$, does \[ I(T_1,T_2)\neq\varnothing \quad\Longrightarrow\quad \exists i\in I(T_1,T_2)\ \exists w\in\mathcal P(T_1)\cap\mathcal P(T_2),\qquad w_i=w_{i+1} \] hold? The phrase "those uncle and nephew leaves" could instead require a common parse word for each prescribed eligible pair, giving the stronger quantifier pattern \[ \forall i\in I(T_1,T_2)\ \exists w\in\mathcal P(T_1)\cap\mathcal P(T_2),\qquad w_i=w_{i+1}. \] The supplied wording does not resolve this distinction. Neither formulation is asserted here as the definitive intended conjecture.

Short English statement

The question asks whether two trees with a shared consecutive uncle--nephew leaf pair admit a common parse word assigning equal labels to such a pair. The tree conventions, parsing system, orientation requirement, and choice of eligible pair need clarification. The supplied dated curation labels the problem partially solved, with special classes proved and the general case reported unproved; these claims have not been independently verified.

Sources

• Local UnsolvedMath registry: supplied complete source record, permanent ID $30001556$, title Common Parse Words for Rooted Tree Pairs, exact source problem code catalogue entry, in the Oberwolfach Reports Open Problems collection. No individual proposer is supplied; the proposed year is recorded as 2010.
• Supplied source citation: Mini-Workshop: Combinatorics on Words (2011), Oberwolfach Reports, pp. 2195--2244, DOI 10.4171/owr/2010/37. Original workshop report: https://doi.org/10.4171/owr/2010/37. The background identifies Oberwolfach Reports as documenting mathematical workshops and their open-problem discussions. The citation's 2011 date and the record's 2010 proposed year and year tag are retained without reconciliation.
• Supplied literature reference, labeled "Kryuchkov tree-pair results": https://www.combinatorics.org/ojs/index.php/eljc/article/download/v18i2p32/pdf/. No full bibliographic details or precise supporting theorem are supplied.
• Literature assessment checked at 2026-08-21: the supplied curation labels the problem partially_solved and states that the conjecture is proved for several special classes of tree pairs, while the general non-mutually-crooked case remains unproved. This is supplied dated curation derived from the OWR record, not an independently verified literature assessment; its time-sensitive status and cited claims require independent verification. The listed sources checked are the two links above.
• The registry labels the statement corrected_verified, with the explanation that TeX-style punctuation was normalized without changing mathematical content. This supplied label does not establish mathematical verification of the formulation above.