{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:42:08Z","timestamp":1787341328330,"version":"build-2736575974"},"reference-count":51,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-16-CE25-0009-03"],"award-info":[{"award-number":["ANR-16-CE25-0009-03"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["NI 369\/17"],"award-info":[{"award-number":["NI 369\/17"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["787367"],"award-info":[{"award-number":["787367"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"name":"French ANR","award":["ANR-22-CE48-0001 (TEMPOGRAL)"],"award-info":[{"award-number":["ANR-22-CE48-0001 (TEMPOGRAL)"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2024,4,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>A graph whose edges only appear at certain points in time is called a temporal graph (among other names). Such a graph is temporally connected if each ordered pair of vertices is connected by a path which traverses edges in chronological order (i.e., a temporal path). In this paper, we consider a simple model of random temporal graph, obtained from an Erd\u0151s\u2013R\u00e9nyi random graph, [Formula: see text], by considering a random permutation [Formula: see text] of the edges and interpreting the ranks in [Formula: see text] as presence times. We give a thorough study of the temporal connectivity of such graphs and derive implications for the existence of several kinds of sparse spanners. It turns out that temporal reachability in this model exhibits a surprisingly regular sequence of thresholds. In particular, we show that at [Formula: see text], any fixed pair of vertices can asymptotically almost surely (a.a.s.) reach each other; at [Formula: see text], at least one vertex (and, in fact, any fixed vertex) can a.a.s. reach all others; and at [Formula: see text], all the vertices can a.a.s. reach each other; i.e., the graph is temporally connected. Furthermore, the graph admits a temporal spanner of size [Formula: see text] as soon as it becomes temporally connected, which is nearly optimal, as [Formula: see text] is a lower bound. This result is quite significant because temporal graphs do not admit spanners of size [Formula: see text] in general [Kempe, Kleinberg, and Kumar, J. Comput. System Sci., 64 (2002), pp. 820\u2013842]. In fact, they do not even always admit spanners of size [Formula: see text] [Axiotis and Fotakis, On the size and the approximability of minimum temporally connected subgraphs, 2016, pp. 149:1\u2013149:14]. Thus, our result implies that the obstructions found in these works\u2014and more generally any non-negligible obstruction\u2014are statistically insignificant: nearly optimal spanners always exist in random temporal graphs. All the above thresholds are sharp. Carrying the study of temporal spanners a step further, we show that pivotal spanners\u2014i.e., spanners of size [Formula: see text] composed of two spanning trees glued at a single vertex (one descending in time, the other ascending subsequently)\u2014exist a.a.s. at [Formula: see text], this threshold being also sharp. Finally, we show that optimal spanners (of size [Formula: see text]) also exist a.a.s. at [Formula: see text]. Whether this value is a sharp threshold is open; we conjecture that it is. For completeness, we compare the above results to existing results in related areas, including edge-ordered graphs, gossip theory, and population protocols, showing that our results can be interpreted in these settings as well and that in some cases they improve known results therein. Finally, we discuss an intriguing connection between our results and Janson\u2019s celebrated results on percolation in weighted graphs.<\/jats:p>","DOI":"10.1137\/22m1511916","type":"journal-article","created":{"date-parts":[[2024,3,19]],"date-time":"2024-03-19T04:21:24Z","timestamp":1710822084000},"page":"346-388","source":"Crossref","is-referenced-by-count":5,"title":["Sharp Thresholds in Random Simple Temporal Graphs"],"prefix":"10.1137","volume":"53","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7819-7013","authenticated-orcid":true,"given":"Arnaud","family":"Casteigts","sequence":"first","affiliation":[{"name":"Computer Science Department, University of Geneva, Geneva, Switzerland. Part of this project was done while the author was at LaBRI, CNRS, University of Bordeaux, France."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6660-5673","authenticated-orcid":true,"given":"Michael","family":"Raskin","sequence":"additional","affiliation":[{"name":"LaBRI, CNRS, University of Bordeaux, Bordeaux, France. Part of this project was done while the author was at Department of Informatics, Technical University of Munich, Germany."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1450-1901","authenticated-orcid":true,"given":"Malte","family":"Renken","sequence":"additional","affiliation":[{"name":"Algorithmics and Computational Complexity group, Technical University of Berlin, Berlin, Germany."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5755-4141","authenticated-orcid":true,"given":"Viktor","family":"Zamaraev","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Liverpool, Liverpool L69 3BX, United Kingdom."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2024,3,19]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-017-9757-x"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2020.05.005"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2019.08.002"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1017\/S096354831900018X"},{"key":"ref5","doi-asserted-by":"crossref","unstructured":"D. Angluin , \nJ. Aspnes , \nZ. Diamadi , \nM. J. Fischer , and \nR. Peralta  , Computation in networks of passively mobile finite-state sensors, in Proceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing (PODC), 2004, pp. 290\u2013299, https:\/\/doi.org\/10.1145\/1011767.1011810.","DOI":"10.1145\/1011767.1011810"},{"key":"ref6","doi-asserted-by":"crossref","unstructured":"C. Avin , \nM. Kouck\u1ef3 , and \nZ. Lotker  , How to explore a fast-changing world (cover time of a simple random walk on evolving graphs), in Proceedings of the 35th International Colloquium on Automata, Languages, and Programming (ICALP), 2008, pp. 121\u2013132, https:\/\/doi.org\/10.1007\/978-3-540-70575-8_11.","DOI":"10.1007\/978-3-540-70575-8_11"},{"key":"ref7","unstructured":"K. Axiotis  and \nD. Fotakis  , On the size and the approximability of minimum temporally connected subgraphs, in 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), Leibniz International Proceedings in Informatics (LIPIcs), Vol. 55, Schloss Dagstuhl, Leibniz-Zentrum f\u00fcr Informatik, Wadern, Germany, 2016, pp. 149:1\u2013149:14, https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2016.149."},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.2748\/tmj\/1178243286"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-011-0133-9"},{"key":"ref10","doi-asserted-by":"crossref","unstructured":"S. Bhadra  and \nA. Ferreira  , Complexity of connected components in evolving graphs and the computation of multicast trees in dynamic networks, in Proceedings of the 2nd International Conference on Ad-Hoc Networks and Wireless (ADHOC-NOW), 2003, pp. 259\u2013270, https:\/\/doi.org\/10.1007\/978-3-540-39611-6_23.","DOI":"10.1007\/978-3-540-39611-6_23"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814068"},{"key":"ref12","doi-asserted-by":"crossref","unstructured":"B. Bollob\u00e1s  , The Art of Mathematics: Coffee Time in Memphis, Cambridge University Press, Cambridge, 2006.","DOI":"10.1017\/CBO9780511816574"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.2307\/3213094"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-020-2035-7"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054103001728"},{"key":"ref16","volume":"2","author":"Bumby R. T.","year":"1979","journal-title":"SIAM J. Algeber. Discrete Methods"},{"key":"ref17","doi-asserted-by":"crossref","unstructured":"J. Burman , \nH.L. Chen , \nH.P. Chen , \nD. Doty , \nT. Nowak , \nE. Severson , and \nC. Xu  , Time-optimal self-stabilizing leader election in population protocols, in Proceedings of the 40th Annual ACM Symposium on Principles of Distributed Computing (PODC), 2021, pp. 33\u201344, https:\/\/doi.org\/10.1145\/3465084.3467898.","DOI":"10.1145\/3465084.3467898"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(84)90031-1"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1080\/17445760.2012.668546"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-021-00831-w"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2021.04.004"},{"key":"ref22","doi-asserted-by":"crossref","unstructured":"A. Casteigts , \nM. Raskin , \nM. Renken , and \nV. Zamaraev  , Sharp thresholds in random simple temporal graphs, in Proceedings of the 62nd Annual Symposium on Foundations of Computer Science (FOCS), 2022, pp. 319\u2013326, https:\/\/doi.org\/10.1109\/FOCS52979.2021.00040.","DOI":"10.1109\/FOCS52979.2021.00040"},{"key":"ref23","doi-asserted-by":"crossref","unstructured":"A. Chaintreau , \nA. Mtibaa , \nL. Massoulie , and \nC. Diot  , The diameter of opportunistic mobile networks, in Proceedings of the 3rd International Conference on Emerging Networking Experiments and Technologies (CoNEXT), 2007, pp. 1\u201312, https:\/\/doi.org\/10.1145\/1364654.1364670.","DOI":"10.1145\/1364654.1364670"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.4153\/CMB-1971-028-8"},{"key":"ref25","doi-asserted-by":"crossref","unstructured":"A. Clementi , \nC. Macci , \nA. Monti , \nF. Pasquale , and \nR. Silvestri  , Flooding time in edge-markovian dynamic graphs, in Proceedings of the 27th Annual ACM Symposium on Principles of Distributed Computing (PODC), 2008, pp. 213\u2013222, https:\/\/doi.org\/10.1145\/1400751.1400781.","DOI":"10.1145\/1400751.1400781"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2008.10.004"},{"key":"ref27","unstructured":"B. Doerr  and \nA. Kostrygin  , Randomized rumor spreading revisited, in Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP), Vol. 80, 2017, pp. 138:1\u2013138:14, https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2017.138."},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2020.08.001"},{"key":"ref29","unstructured":"P. Erd\u00f6s  and \nA. R\u00e9nyi  , On the evolution of random graphs, A Magyar Tudom\u00e1nyos Akad\u00e9mia.Matematikai Kutat\u00f3 Int\u00e9zet\u00e9nek K\u00f6zlem\u00e9nyei, 5 (1960), pp. 17\u201361."},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2019.03.031"},{"key":"ref31","doi-asserted-by":"crossref","unstructured":"A. Frieze  and \nM. Karo\u0144ski  , Introduction to Random Graphs, 2015, Cambridge University Press, Cambridge, https:\/\/doi.org\/10.1017\/CBO9781316339831.","DOI":"10.1017\/CBO9781316339831"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(85)90059-9"},{"key":"ref33","doi-asserted-by":"crossref","unstructured":"E. Godard  and \nD. Mazauric  , Computing the dynamic diameter of non-deterministic dynamic networks is hard, in Proceedings of the 10th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS), 2014, pp. 88\u2013102, https:\/\/doi.org\/10.1007\/978-3-662-46018-4_6.","DOI":"10.1007\/978-3-662-46018-4_6"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1007\/BF02018469"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.2009.0456"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.2307\/3213330"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-23495-9"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548399003892"},{"key":"ref39","doi-asserted-by":"crossref","unstructured":"R. Karp , \nC. Schindelhauer , \nS. Shenker , and \nB. Vocking  , Randomized rumor spreading, in Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS), 2000, pp. 565\u2013574, https:\/\/doi.org\/10.1109\/SFCS.2000.892324.","DOI":"10.1109\/SFCS.2000.892324"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2002.1829"},{"key":"ref41","unstructured":"J. Kleinberg  and \n\u00c9. Tardos  , Algorithm Design, Pearson, London, 2006."},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20592"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20803"},{"key":"ref44","unstructured":"G. B. Mertzios , \nH. Molter , \nR. Niedermeier , \nV. Zamaraev , and \nP. Zschoche  , Computing maximum matchings in temporal graphs, in Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science (STACS), Vol. 154, 2020, pp. 27:1\u201327:14, https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2020.27."},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2021.03.005"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2018.0845"},{"key":"ref47","doi-asserted-by":"crossref","unstructured":"Y. Mocquard , \nB. Sericola , \nS. Robert , and \nE. Anceaume  , Analysis of the propagation time of a rumour in large-scale distributed systems, in Proceedings of the 15th IEEE International Symposium on Network Computing and Applications, 2016, pp. 264\u2013271, https:\/\/doi.org\/10.1109\/NCA.2016.7778629.","DOI":"10.1109\/NCA.2016.7778629"},{"key":"ref48","first-page":"246","author":"Moon J. W.","year":"1972","journal-title":"Nieuw Archief voor Wiskunde"},{"key":"ref49","doi-asserted-by":"publisher","DOI":"10.1016\/0898-1221(81)90008-0"},{"key":"ref50","doi-asserted-by":"crossref","unstructured":"H. van Ditmarsch , \nI. Kokkinis , and \nA. Stockmarr  , Reachability and expectation in gossiping, in Proceedings of PRIMA 2017: Principles and Practice of Multi-Agent Systems, 2017, pp. 93\u2013109, https:\/\/doi.org\/10.1007\/978-3-319-69131-2_6.","DOI":"10.1007\/978-3-319-69131-2_6"},{"key":"ref51","doi-asserted-by":"publisher","DOI":"10.1140\/epjb\/e2017-80122-8"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/22M1511916","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:13:59Z","timestamp":1787339639000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/22M1511916"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,19]]},"references-count":51,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,4,30]]}},"alternative-id":["10.1137\/22M1511916"],"URL":"https:\/\/doi.org\/10.1137\/22m1511916","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,19]]}}}