Linear chemical distances in scale-free Gilbert graphs

From papers

Let G(X(n))G(X^{(n)}) be the scale-free Gilbert graph on the point set X(n)X^{(n)} in the torus Tn\mathbb{T}_n, let e1=(1,0,,0)\mathsf{e}_1=(1,0,\ldots,0), and let q(x)q(x) denote the closest point of XX to xx. Assume s>ds>d. Linear chemical-distance conjecture. There exists a constant c=c(β,d)>0c=c(\beta,d)>0 such that the chemical distance between q(ne1/4)q(-n\mathsf{e}_1/4) and q(ne1/4)q(n\mathsf{e}_1/4) is at least cncn with high probability as nn\to\infty. The preceding theorem proves only a lower bound of order n/(logn)αn/(\log n)^{\alpha} for every α>0\alpha>0; the conjecture asserts that this sublogarithmic loss is an artifact of the proof and that distances are instead bounded below linearly.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Christian Hirsch, “From heavy-tailed Boolean models to scale-free Gilbert graphs”, arXiv:1411.6824 (2014).

Solutions 0

No solutions have been posted yet.