The Rearrangement Conjecture for generalized factor order

From papers

Let P=PP=\mathbb{P} be the positive integers with their usual order, and let u,vPu,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 wxwyw.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.

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

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

Solutions 0

No solutions have been posted yet.