Asymptotic success probability conjecture for the edge-addition process

For fixed x,y1x,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.

limnax,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.

Sources & referencesView supporting material

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.