The extremal-function classification conjecture for binary (3, t)-formations

Let t6t\geq 6. A (3,t)(3,t)-formation is a concatenation of tt permutations of three distinct letters. Consider formations uu whose first permutation is abca b c and whose remaining permutations are each either abca b c or acba c b. The formation-width fw(u)\operatorname{fw}(u) is the least integer ss such that every binary (3,s)(3,s)-formation contains uu as a subsequence.

Extremal-function classification conjecture. Among these formations, fw(u)=2t1\operatorname{fw}(u)=2t-1 if and only if uu is one of

(abc)t,abc(acb)t1,abc(acb)t2abc,abcacb(abc)t3acb,(a b c)^{t},\quad a b c (a c b)^{t-1},\quad a b c (a c b)^{t-2} a b c,\quad a b c a c b (a b c)^{t-3} a c b, abcacb(abc)t2,abcabc(acb)t2,(abc)t2acbacb,(abc)t2acbabc,(abc)t1acb.a b c a c b (a b c)^{t-2},\quad a b c a b c (a c b)^{t-2},\quad (a b c)^{t-2} a c b a c b,\quad (a b c)^{t-2} a c b a b c,\quad (a b c)^{t-1} a c b.

This conjecture proposes a complete classification of the formations attaining the extremal value 2t12t-1, extending the evidence and preceding proposition in the paper; its resolution would determine precisely which binary (3,t)(3,t)-formations have maximal formation-width in this setting.

Sources & referencesView supporting material

Primary source

Jesse Geneson, “An algorithm for bounding extremal functions of forbidden sequences”, arXiv:1912.04897 (2019).

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.