Negative-binomial conjecture for the number of geodesic paths

About 10 years old · traced to

Let G(n,π)G(n,\pi) be the unit disk graph, and let two vertices be displaced by rxyr_{xy}. Write σrxy\sigma_{r_{xy}} for the number of geodesic paths between them. Negative-binomial conjecture. The random variable σrxy\sigma_{r_{xy}} is distributed as

P(σrxy=k)=(k+r−1k)pr(1−p)k,\mathbb{P}(\sigma_{r_{xy}}=k)={k+r-1\choose k}p^{r}(1-p)^{k},

where pp and rr solve

E(σrxy)=(1−p)rp,\mathbb{E}(\sigma_{r_{xy}})=\frac{(1-p)r}{p}, E(σrxy2)=E(σrxy)(1p+E(σrxy)).\mathbb{E}(\sigma_{r_{xy}}^{2})=\mathbb{E}(\sigma_{r_{xy}})\left(\frac{1}{p}+\mathbb{E}(\sigma_{r_{xy}})\right).

This conjecture proposes a negative-binomial model for geodesic-path counts at larger displacements, where the variance exceeds the mean; the supplied text gives no resolution status.

References

Primary source

Alexander P. Kartun-Giles, “Connectivity and Centrality in Dense Random Geometric Graphs”, arXiv:1601.03296 (2019).

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.