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

At least 7 years old · documented by

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+cn−j/3)p^gp=(1+cn^{-j/3})\hat{p}_\mathrm{g}

for some fixed c∈Rc\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 j≥2j\ge 2; the proposed scale is motivated by the n−j/3n^{-j/3} critical-window parameter, but no resolution is supplied here.

References

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.