The critical-window conjecture for giant jj-components in random hypergraphs

Let Hk(n,p)\mathcal{H}^k(n,p) be the random kk-uniform hypergraph with edge probability pp, and let jj-components denote components under the adjacency notion used in the paper. Write p^g\hat{p}_\mathrm{g} for the threshold appearing in Theorem~, let ε=ε(n)\varepsilon=\varepsilon(n), and let whp\operatorname{whp} mean with high probability. Critical-window conjecture. Theorem~ should hold for all ε=ε(n)\varepsilon=\varepsilon(n) satisfying

ε0andε3nj.\varepsilon\to 0 \qquad\text{and}\qquad \varepsilon^3 n^j\to\infty.

Furthermore, if

p=(1+cnj/3)p^gp=(1+cn^{-j/3})\hat{p}_\mathrm{g}

for some fixed cRc\in\mathbb{R}, then with high probability all jj-components have size O(n2j/3)O(n^{2j/3}), and there is more than one jj-component of Hk(n,p)\mathcal{H}^k(n,p) of size Θ(n2j/3)\Theta(n^{2j/3}). The conjecture would sharpen the known lower bound on the width of the critical window for the emergence of a unique largest jj-component. The surrounding discussion indicates that the existing condition ε2n1δ\varepsilon^2n^{1-\delta}\to\infty is probably not best possible for j2j\ge 2; the proposed scale is motivated by the nj/3n^{-j/3} critical-window parameter, but no resolution is supplied here.

Sources & referencesView supporting material

Primary source

Oliver Cooley, Mihyun Kang and Christoph Koch, “The size of the giant component in random hypergraphs: a short proof”, arXiv:1803.02809 (2018).

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.