The critical-window product conjecture for random digraph components

About 7 years old · traced to

Let D(n,p)D(n,p) be the random directed graph and G(n,p)G(n,p) the random graph, with p=n−1+λn−4/3p=n^{-1}+\lambda n^{-4/3}. Let Xλ=n−2/3∣C1(G(n,p))∣X^\lambda=n^{-2/3}|\mathcal{C}_1(G(n,p))| and Yλ=n−1/3∣C1(D(n,p))∣Y^\lambda=n^{-1/3}|\mathcal{C}_1(D(n,p))|, and let X1λX_1^\lambda and X2λX_2^\lambda be independent copies of XλX^\lambda. Critical-window product conjecture. The distributions satisfy

Yλ=X1λX2λ.Y^\lambda=X_1^\lambda X_2^\lambda.

This conjecture proposes an exact relation between the critical-window component-size distributions of random directed and undirected graphs, extending the known connection between giant strongly connected components in D(n,p)D(n,p) and giant components in G(n,p)G(n,p) for larger pp.

References

Primary source

Matthew Coulson, “The critical window in random digraphs”, arXiv:1905.00624 (2019).

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.