The critical-window product conjecture for random digraph components

Let D(n,p)D(n,p) be the random directed graph and G(n,p)G(n,p) the random graph, with p=n1+λn4/3p=n^{-1}+\lambda n^{-4/3}. Let Xλ=n2/3C1(G(n,p))X^\lambda=n^{-2/3}|\mathcal{C}_1(G(n,p))| and Yλ=n1/3C1(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.

Sources & referencesView supporting material

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.