Asymptotic success probability conjecture for the edge-addition process

About 3 years old · traced to

For fixed x,y≥1x,y\geq 1, let ax,y,na_{x,y,n} denote the probability that the (x,y)(x,y) edge-addition process on nn vertices generates an (x,y)(x,y) task-dependency graph.

Edge-addition success-probability conjecture.

lim⁡n→∞ax,y,n=1.\lim_{n\rightarrow\infty}a_{x,y,n}=1.

This conjecture is based on experimental results indicating that the probability approaches 11 as the number of vertices grows. No proof or resolution is provided in the source.

References

Primary source

Jesse Geneson and Shen-Fu Tsai, “Random processes for generating task-dependency graphs”, arXiv:2305.05205 (2023).

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.