{"ID":2855776,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.12543","arxiv_id":"2510.12543","title":"The Diameter of (Threshold) Geometric Inhomogeneous Random Graphs","abstract":"We prove that the diameter of threshold (zero temperature) Geometric Inhomogeneous Random Graphs (GIRG) is $Θ(\\log n)$. This has strong implications for the runtime of many distributed protocols on those graphs, which often have runtimes bounded as a function of the diameter. The GIRG model exhibits many properties empirically found in real-world networks, and the runtime of various practical algorithms has empirically been found to scale in the same way for GIRG and for real-world networks, in particular related to computing distances, diameter, clustering, cliques and chromatic numbers. Thus the GIRG model is a promising candidate for deriving insight about the performance of algorithms in real-world instances. The diameter was previously only known in the one-dimensional case, and the proof relied very heavily on dimension one. Our proof employs a similar Peierls-type argument alongside a novel renormalization scheme. Moreover, instead of using topological arguments (which become complicated in high dimensions) in establishing the connectivity of certain boundaries, we employ some comparatively recent and clearer graph-theoretic machinery. The lower bound is proven via a simple ad-hoc construction.","short_abstract":"We prove that the diameter of threshold (zero temperature) Geometric Inhomogeneous Random Graphs (GIRG) is $Θ(\\log n)$. This has strong implications for the runtime of many distributed protocols on those graphs, which often have runtimes bounded as a function of the diameter. The GIRG model exhibits many properties emp...","url_abs":"https://arxiv.org/abs/2510.12543","url_pdf":"https://arxiv.org/pdf/2510.12543v1","authors":"[\"Zylan Benjert\",\"Kostas Lakis\",\"Johannes Lengler\",\"Raghu Raman Ravi\"]","published":"2025-10-14T14:07:07Z","proceeding":"math.PR","tasks":"[\"math.PR\",\"cs.SI\"]","methods":"[]","has_code":false}