Nakamuta's conjecture on c-Wilf equivalence of permutation patterns

Let vv and ww be permutation patterns. They are c-Wilf-equivalent in permutations if

g0v(Sn)=g0w(Sn)g_0^v({\mathcal S}_n)=g_0^w({\mathcal S}_n)

for every nNn\in{\mathbb N}, and they are strongly c-Wilf-equivalent in permutations if

grv(Sn)=grw(Sn)g_r^v({\mathcal S}_n)=g_r^w({\mathcal S}_n)

for every nNn\in{\mathbb N} and rN0r\in{\mathbb N}_0, where grv(Sn)g_r^v({\mathcal S}_n) counts permutations in Sn{\mathcal S}_n containing vv consecutively exactly rr times. Nakamuta's conjecture. If two patterns are c-Wilf-equivalent in permutations, then they are also strongly c-Wilf-equivalent in permutations. This conjecture asserts that equality of consecutive-avoidance counts already determines the full distribution of consecutive occurrences for permutation patterns. It is presented as an important open problem; the analogous classification problem for classical pattern avoidance is also described as wide open.

Sources & referencesView supporting material

Primary source

Reza Rastegar, “Consecutive Pattern Containment and c-Wilf Equivalence”, arXiv:2304.14733 (2024).

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.