Component-size conjecture for random graphs locally modelled on lattices

Let Ld\mathbb{L}^d denote the dd-dimensional lattice. Define

r0(2)=2,r0(d)=3for all d3.r_0(2)=2,\qquad r_0(d)=3\quad\text{for all }d\geq 3.

Let dNd\in\mathbb{N} with d2d\geq 2, and let rNr\in\mathbb{N} with rr0(d)r\geq r_0(d). Component-size conjecture. With high probability, the largest component of Gn(Ld,r)G_n(\mathbb{L}^d,r) has order

Θd,r ⁣(n1/(d+1)logn).\Theta_{d,r}\!\left(n^{1/(d+1)}\log n\right).

This is proposed as a refinement of the preceding largest-component results, which give the corresponding phenomenon in a less precise or more general setting; the asserted asymptotic order remains conjectural.

Sources & referencesView supporting material

Primary source

Itai Benjamini and David Ellis, “On the structure of random graphs with constant r-balls”, arXiv:1802.02002 (2020).

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.