Replacement-bijection conjecture for equivalent binary tree patterns
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.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Eric S. Rowland, “Pattern avoidance in binary trees”, arXiv:0809.0488 (2010).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.