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

At least 1 year old · documented by

Let Σs={0,…,s−1}\Sigma_s=\{0,\ldots,s-1\}, and for variables xi≥0x_i\geq 0 with

x1+⋯+x⌊(s−1)/2⌋≤12,x_1+\cdots+x_{\lfloor (s-1)/2\rfloor}\leq\frac12,

let hs(x1,…,x⌊(s−1)/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⌊(s−1)/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)=min⁡xi≥0,  x1+⋯+x⌊(s−1)/2⌋≤12hs(x1,…,x⌊(s−1)/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.

References

Primary source

Raphael Yuster, “On the minimum density of monotone subwords”, arXiv:2407.20641 (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.