The random-interval set k-width scaling conjecture

About 9 years old · traced to

Let k≥2k\geq 2, and let WnW_n be a set of nn random intervals. Write E[k-wd⁡(Wn)]E[k\operatorname{-wd}(W_n)] for the expected kk-width of WnW_n. Random-interval set scaling conjecture. There exists a positive constant dk>0d_k>0 such that

lim⁡n→∞E[k-wd⁡(Wn)]n=dk.\lim_{n\rightarrow\infty}\frac{E[k\operatorname{-wd}(W_n)]}{n}=d_k.

The experiments suggest that d2=c2=13d_2=c_2=\frac{1}{3} and, for k=3,4k=3,4, dk=ck=1k+1d_k=c_k=\frac{1}{k+1}. The conjecture extends this observed pattern to all k≥2k\geq 2:

dk=ck=1k+1for all k≥2.d_k=c_k=\frac{1}{k+1}\quad\text{for all }k\geq 2.

The claim concerns the asymptotic kk-width of sets of random intervals; the evidence given is experimental, and the general result remains 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.