The random-interval set k-width scaling conjecture

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

limnE[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 k2k\geq 2:

dk=ck=1k+1for all k2.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.

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.