The Rearrangement Conjecture for generalized factor order

About 10 years old · traced to

Let P=PP=\mathbb{P} be the positive integers with their usual order, and let u,v∈P∗u,v\in\mathbb{P}^* be words. Two words are Wilf equivalent if they are avoided by the same number of words of every length and sum; equivalently, if

Fu(x,y)=Fv(x,y),F_u(x,y)=F_v(x,y),

where

Fu(x,y)=∑w:u is not a generalized factor of wx∣w∣y∥w∥.F_u(x,y)=\sum_{\substack{w:\,u\text{ is not a generalized factor of }w}}x^{|w|}y^{\|w\|}.

Rearrangement Conjecture. If uu and vv are Wilf equivalent, then they are rearrangements of each other; that is, they have the same multiset of letters. The converse is false: for example, A132(x,y,0)≠A312(x,y,0)A_{132}(x,y,0)\ne A_{312}(x,y,0). The conjecture asks whether Wilf equivalence forces equality of the letter multisets; it was disproved in this paper, while a weakening for strongly Wilf equivalent words is known.

References

Primary source

Jennifer Fidler, Daniel Glasscock, Brian Miceli, Jay Pantone and Min Xu, “Shift equivalence in the generalized factor order”, arXiv:1612.09003 (2016).

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.