Replacement-bijection conjecture for equivalent binary tree patterns

From papers

Let ss and tt be equivalent binary tree patterns, meaning that the binary trees avoiding ss and those avoiding tt 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 ss and tt 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 ss to binary trees avoiding tt.

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 77 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

No solutions have been posted yet.