Quadratic edge-count conjecture for the (1,1) edge-addition process

Let fnf_n denote the expected number of edges in the task-dependency graph generated by the (1,1)(1,1) edge-addition process on nn vertices.

Quadratic edge-count conjecture.

limnfnn20.37.\lim_{n\rightarrow\infty}\frac{f_n}{n^2}\approx 0.37.

The source gives that the expectation is Θ(n2)\Theta(n^2), with approximate lower and upper bounds of n2/4n^2/4 and n2/2n^2/2, and uses experimental results to conjecture a limiting ratio slightly closer to the lower bound. No resolution is provided.

Sources & referencesView supporting material

Primary source

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

Additional references

2 papers in this index state this conjecture (2021–2023). The statement above is taken from the most recent of them; the others are arXiv:2111.07050.

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.