Replacement-bijection conjecture for equivalent binary tree patterns
Let and be equivalent binary tree patterns, meaning that the binary trees avoiding and those avoiding are equinumerous. A top-down replacement, bottom-up replacement, and left--right reflection are the pattern transformations described in the paper, each inducing the corresponding transformation on binary trees.
Replacement-bijection conjecture. If and are equivalent, then there is a sequence of top-down replacements, bottom-up replacements, and left--right reflections that produces a bijection from binary trees avoiding to binary trees avoiding .
The conjecture proposes that these explicit transformations generate all equivalences between binary tree pattern-avoidance classes. The paper states that the assertion holds computationally for patterns with at most leaves, while the general case remains open.
References
- Eric S. Rowland, “Pattern avoidance in binary trees”, arXiv:0809.0488 (2010).
Progress summary
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.