The random-interval sequence k-width scaling conjecture

About 9 years old · traced to

Let k≥2k\geq 2, and let RnR_n be a sequence of nn random intervals. Write E[k-wd⁡(Rn)]E[k\operatorname{-wd}(R_n)] for the expected kk-width of RnR_n. Random-interval sequence scaling conjecture. There exists a positive constant ck>0c_k>0 such that

lim⁡n→∞E[k-wd⁡(Rn)]n=ck,\lim_{n\rightarrow\infty}\frac{E[k\operatorname{-wd}(R_n)]}{n}=c_k,

and moreover

ck=1k+1.c_k=\frac{1}{k+1}.

The conjecture predicts linear scaling for the kk-width of sequences of random intervals when k≥2k\geq 2, contrasting with the known behavior for k=1k=1. The constants are motivated by computational experiments, while the asserted limit and formula remain open.

References

Primary source

János Balogh, Cosmin Bonchiş, Diana Diniş, Gabriel Istrate and Ioan Todinca, “On the heapability of finite partial orders”, arXiv:1706.01230 (2020).

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.