Tightness conjecture for the folded-form construction of minimum-density monotone 3-subwords

From papers

Let Σs={0,,s1}\Sigma_s=\{0,\ldots,s-1\}, and for variables xi0x_i\geq 0 with

x1++x(s1)/212,x_1+\cdots+x_{\lfloor (s-1)/2\rfloor}\leq\frac12,

let hs(x1,,x(s1)/2)h_s(x_1,\ldots,x_{\lfloor (s-1)/2\rfloor}) be the degree-33 polynomial such that every folded-form nn-word corresponding to these parameters has monotone 3-subword density hs(x1,,x(s1)/2)+on(1)h_s(x_1,\ldots,x_{\lfloor (s-1)/2\rfloor})+o_n(1). Let f(s,3)f(s,3) denote the limiting minimum density of monotone 3-subwords over Σs\Sigma_s.

Folded-form tightness conjecture. The construction's upper bound is tight:

f(s,3)=minxi0,  x1++x(s1)/212hs(x1,,x(s1)/2).f(s,3)=\min_{x_i\geq 0,\;x_1+\cdots+x_{\lfloor (s-1)/2\rfloor}\leq\frac12}h_s(x_1,\ldots,x_{\lfloor (s-1)/2\rfloor}).

The proposition immediately before the conjecture proves only the corresponding upper bound; equality remains open in the provided text.

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

Raphael Yuster, “On the minimum density of monotone subwords”, arXiv:2407.20641 (2024).

Solutions 0

No solutions have been posted yet.