Threshold conjecture for the local pooling factor in random graphs

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 r2o(1/n6/5)r^2\in o(1/n^{6/5}); the conjecture asserts that the corresponding threshold scale also governs the 11-statement.

Sources & referencesView supporting material

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.