Quadratic edge-count conjecture for the (1,1) edge-addition process
Quadratic edge-count conjecture for the (1,1) edge-addition process
Let denote the expected number of edges in the task-dependency graph generated by the edge-addition process on vertices.
Quadratic edge-count conjecture.
The source gives that the expectation is , with approximate lower and upper bounds of and , 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.