INCREASING PATHS IN RANDOM TEMPORAL GRAPHS

• 成果类型: Article
• 署名作者: Broutin, Nicolas; Kamcev, Nina; Ugosi, Gabor
• 署名单位: Sorbonne Universite; Universite Paris Cite; University of Zagreb; ICREA
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/24-AAP2097
• 发表日期: 2024
• 页码: 5498-5521
• 关键词: random exchanges; heights

摘要

We consider random temporal graphs, a version of the classical Erdos- R & eacute;nyi random graph G(n, p) where additionally, each edge has a distinct random time stamp, and connectivity is constrained to sequences of edges with increasing time stamps. We study the asymptotics for the distances in such graphs, mostly in the regime of interest where np is of order log n. We establish the first order asymptotics for the lengths of increasing paths: the lengths of the shortest and longest paths between typical vertices, the maxima of these lengths from a given vertex, as well as the maxima between any two vertices; this covers the (temporal) diameter.