The layered extremal word conjecture

Let Π\Pi be a set of layered patterns, and let δ(Π)\delta(\Pi) denote their packing density and δ(Π)\delta'(\Pi) the corresponding density when the alphabet size is fixed as in the paper. A string is layered if it is formed from layers, and a maximal Π\Pi-containing string is one attaining the maximum number of occurrences of patterns in Π\Pi.

Layered extremal word conjecture. If Π\Pi is a set of layered patterns, then

δ(Π)=δ(Π),\delta'(\Pi)=\delta(\Pi),

and among maximal Π\Pi-containing strings in [k]n[k]^n, there is one which is layered.

This conjecture asserts that restricting to layered strings does not reduce the packing density for sets of layered patterns, and that a layered extremal string always exists. The supplied context does not establish the claim or give a resolution status.

Sources & referencesView supporting material

Primary source

A. Burstein, Peter Hästö and T. Mansour, “Packing patterns into words”, arXiv:math/0212343 (2003).

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.