Linear chemical distances in scale-free Gilbert graphs

About 12 years old · traced to

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 n→∞n\to\infty. The preceding theorem proves only a lower bound of order n/(log⁡n)α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.

References

Primary source

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

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.