Threshold conjecture for the local pooling factor in random graphs

About 12 years old · traced to

Let G(n,r)G(n,r) be the random graph model under consideration, with edge-probability parameter r2r^2, and let LoP⁡\operatorname{LoP} denote the graph property that the local pooling factor has the specified value. A function f(n)f(n) is a threshold function for a graph property if the property changes from holding with probability tending to 00 to holding with probability tending to 11 as the parameter crosses the scale f(n)f(n). Threshold conjecture for the local pooling factor. The function

r2=1/n6/5r^2=1/n^{6/5}

is a threshold function for the graph property LoP⁡\operatorname{LoP}. The preceding corollary establishes a 00-statement when r2∈o(1/n6/5)r^2\in o(1/n^{6/5}); the conjecture asserts that the corresponding threshold scale also governs the 11-statement.

References

Primary source

Jeffrey Wildman and Steven Weber, “On Characterizing the Local Pooling Factor of Greedy Maximal Scheduling in Random Graphs”, arXiv:1409.0932 (2015).

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.