{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T15:30:01Z","timestamp":1787326201973,"version":"build-2736575974"},"reference-count":41,"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-22-CE48-0001"],"award-info":[{"award-number":["ANR-22-CE48-0001"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-22-CE48-0001"],"award-info":[{"award-number":["ANR-22-CE48-0001"]}],"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"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2026,6,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>A temporal graph is a graph whose edges appear only at certain points in time. Recently, the second and the last three authors proposed a natural temporal analog of the Erd\u0151s\u2013R\u00e9nyi random graph model. The proposed model is obtained by randomly permuting the edges of an Erd\u0151s\u2013R\u00e9nyi random graph and interpreting this permutation as an ordering of presence times. It was shown that the connectivity threshold in the Erd\u0151s\u2013R\u00e9nyi model fans out into multiple phase transitions for several distinct notions of reachability in the temporal setting. In the present paper, we identify a sharp threshold for the emergence of a giant temporally connected component. We show that at [Formula: see text] the size of the largest temporally connected component increases from [Formula: see text] to [Formula: see text]. This threshold holds for both open and closed connected components, i.e., components that allow\u00a0(respectively, forbid) their connecting paths to use external nodes.<\/jats:p>","DOI":"10.1137\/24m1673206","type":"journal-article","created":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T07:16:44Z","timestamp":1775027804000},"page":"449-485","source":"Crossref","is-referenced-by-count":0,"title":["Giant Components in Random Temporal Graphs"],"prefix":"10.1137","volume":"40","author":[{"given":"Ruben","family":"Becker","sequence":"first","affiliation":[{"name":"Ca\u2019 Foscari University of Venice, Venezia - Mestre, 30172 Italy."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Arnaud","family":"Casteigts","sequence":"additional","affiliation":[{"name":"University of Geneva, Geneva, Switzerland."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pierluigi","family":"Crescenzi","sequence":"additional","affiliation":[{"name":"Gran Sasso Science Institute, L\u2019Aquila, Italy."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bojana","family":"Kodric","sequence":"additional","affiliation":[{"name":"Ericsson Nikola Tesla, Zagreb, Croatia."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Raskin","sequence":"additional","affiliation":[{"name":"LaBRI, University of Bordeaux, CNRS UMR, 5800 France."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Malte","family":"Renken","sequence":"additional","affiliation":[{"name":"Technical University of Berlin, Berlin, Germany."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Viktor","family":"Zamaraev","sequence":"additional","affiliation":[{"name":"School of Computer Science and Informatics, University of Liverpool, UK."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2026,4,1]]},"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.1017\/S0963548325000100"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.2748\/tmj\/1178243286"},{"key":"ref5","volume-title":"Network Science","author":"Barab\u00e1si A.-L.","year":"2016"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1126\/science.286.5439.509"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-011-0133-9"},{"key":"ref8","doi-asserted-by":"crossref","unstructured":"S. Bhadra and A. 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":"ref9","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814068"},{"key":"ref10","unstructured":"A. Brandenberger, S. Donderwinkel, C. Kerriou, G. Lugosi, and R. Mitchell, Temporal Connectivity of Random Geometric Graphs, preprint, arXiv:2502.15274, 2025."},{"key":"ref11","first-page":"5498","volume":"34","author":"Broutin N.","year":"2024","journal-title":"Increasing paths in random temporal graphs"},{"key":"ref12","first-page":"236","author":"Burova S.","year":"2024","journal-title":"Discrete Math. Days, 2024"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-021-00831-w"},{"key":"ref14","doi-asserted-by":"crossref","unstructured":"A. Casteigts, M. Raskin, M. Renken, and V. Zamaraev, Sharp thresholds in random simple temporal graphs, in Proceedings of the 62nd Annual Symposium on Foundations of Computer Science (FOCS), 2021, pp. 319\u2013326, https:\/\/doi.org\/10.1109\/FOCS52979.2021.00040.","DOI":"10.1109\/FOCS52979.2021.00040"},{"key":"ref15","doi-asserted-by":"crossref","unstructured":"A. Chaintreau, A. Mtibaa, L. Massoulie, and C. 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":"ref16","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2008.10.004"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1137\/090756053"},{"key":"ref18","unstructured":"A. Conte, P. Crescenzi, A. Marino, and G. Punzi, Enumeration of s-d separators in DAGs with application to reliability analysis in temporal graphs, in Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science (MFCS), 2020, pp. 25:1\u201325:14, https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2020.25."},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2021.01.007"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2020.08.001"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.5486\/PMD.1959.6.3-4.12"},{"key":"ref22","first-page":"17","volume":"5","author":"Erd\u0151s P.","year":"1960","journal-title":"Publications of the Mathematical Institute of the Hungarian Academy of Sciences"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1007\/BF01894879"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1007\/BF02066689"},{"key":"ref25","doi-asserted-by":"crossref","unstructured":"T. Fluschnik, H. Molter, R. Niedermeier, M. Renken, and P. Zschoche, Temporal graph classes: A view through temporal separators, 806 (2020), pp. 197\u2013218, https:\/\/doi.org\/10.1016\/j.tcs.2019.03.031.","DOI":"10.1016\/j.tcs.2019.03.031"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781316339831"},{"key":"ref27","doi-asserted-by":"crossref","unstructured":"E. Godard and D. 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":"ref28","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.2009.0456"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-23495-9"},{"key":"ref30","first-page":"97","volume":"519","author":"Holme P.","year":"2012","journal-title":"Temporal networks"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240010106"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2002.1829"},{"key":"ref33","volume-title":"Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis","author":"Mitzenmacher M.","year":"2017","edition":"2"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240060204"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548398003526"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1137\/S003614450342480"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.64.026118"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1093\/oso\/9780198805090.001.0001"},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36461-7_7"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1038\/30918"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1140\/epjb\/e2017-80122-8"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/24M1673206","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:28:13Z","timestamp":1787322493000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/24M1673206"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,1]]},"references-count":41,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,6,30]]}},"alternative-id":["10.1137\/24M1673206"],"URL":"https:\/\/doi.org\/10.1137\/24m1673206","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,1]]}}}