The random-interval sequence k-width scaling conjecture

Let k2k\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

limnE[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 k2k\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.

Sources & referencesView supporting material

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.