{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T19:04:43Z","timestamp":1775070283195,"version":"3.50.1"},"reference-count":11,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2025,6,26]],"date-time":"2025-06-26T00:00:00Z","timestamp":1750896000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2025,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A <jats:italic>random temporal graph<\/jats:italic> is an Erd\u0151s-R\u00e9nyi random graph <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000100_inline1.png\"\/><jats:tex-math>\n$G(n,p)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, together with a random ordering of its edges. A path in the graph is called <jats:italic>increasing<\/jats:italic> if the edges on the path appear in increasing order. A set <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000100_inline2.png\"\/><jats:tex-math>\n$S$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> of vertices forms a <jats:italic>temporal clique<\/jats:italic> if for all <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000100_inline3.png\"\/><jats:tex-math>\n$u,v \\in S$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, there is an increasing path from <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000100_inline4.png\"\/><jats:tex-math>\n$u$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> to <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000100_inline5.png\"\/><jats:tex-math>\n$v$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. Becker, Casteigts, Crescenzi, Kodric, Renken, Raskin and Zamaraev [(2023) Giant components in random temporal graphs. arXiv,2205.14888] proved that if <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000100_inline6.png\"\/><jats:tex-math>\n$p=c\\log n\/n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> for <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000100_inline7.png\"\/><jats:tex-math>\n$c\\gt 1$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, then, with high probability, there is a temporal clique of size <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000100_inline8.png\"\/><jats:tex-math>\n$n-o(n)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. On the other hand, for <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000100_inline9.png\"\/><jats:tex-math>\n$c\\lt 1$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, with high probability, the largest temporal clique is of size <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000100_inline10.png\"\/><jats:tex-math>\n$o(n)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. In this note, we improve the latter bound by showing that, for <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000100_inline11.png\"\/><jats:tex-math>\n$c\\lt 1$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, the largest temporal clique is of <jats:italic>constant<\/jats:italic> size with high probability.<\/jats:p>","DOI":"10.1017\/s0963548325000100","type":"journal-article","created":{"date-parts":[[2025,6,26]],"date-time":"2025-06-26T10:59:13Z","timestamp":1750935553000},"page":"671-679","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":1,"title":["On the size of temporal cliques in subcritical random temporal graphs"],"prefix":"10.1017","volume":"34","author":[{"given":"Caelan","family":"Atamanchuk","sequence":"first","affiliation":[{"name":"McGill University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luc","family":"Devroye","sequence":"additional","affiliation":[{"name":"McGill University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"G\u00e1bor","family":"Lugosi","sequence":"additional","affiliation":[{"name":"Pompeu Fabra University"},{"name":"ICREA"},{"name":"Barcelona School of Economics"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2025,6,26]]},"reference":[{"key":"S0963548325000100_ref2","unstructured":"[2] Becker, R. , Casteigts, A. , Crescenzi, P. , et\u00a0al. (2023) Giant components in random temporal graphs. arXiv: 2205.14888."},{"key":"S0963548325000100_ref6","doi-asserted-by":"publisher","DOI":"10.4153\/CMB-1971-028-8"},{"key":"S0963548325000100_ref3","doi-asserted-by":"publisher","DOI":"10.2307\/3213094"},{"key":"S0963548325000100_ref9","doi-asserted-by":"publisher","DOI":"10.2307\/3213330"},{"key":"S0963548325000100_ref10","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20592"},{"key":"S0963548325000100_ref4","doi-asserted-by":"publisher","DOI":"10.1214\/24-AAP2097"},{"key":"S0963548325000100_ref1","doi-asserted-by":"publisher","DOI":"10.1017\/S096354831900018X"},{"key":"S0963548325000100_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/BF02018469"},{"key":"S0963548325000100_ref7","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199809)13:2<99::AID-RSA1>3.0.CO;2-M"},{"key":"S0963548325000100_ref5","doi-asserted-by":"crossref","unstructured":"[5] Casteigts, A. , Raskin, M. , Renken, M. and Zamaraev, V. (2023) Sharp thresholds in random simple temporal graphs. arXiv:2011.03738.","DOI":"10.1109\/FOCS52979.2021.00040"},{"key":"S0963548325000100_ref11","first-page":"246","article-title":"Random exchanges of information","volume":"20","author":"Moon","year":"1972","journal-title":"Nieuw Arch. Wisk (3)"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548325000100","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,16]],"date-time":"2025-09-16T00:12:19Z","timestamp":1757981539000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548325000100\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,26]]},"references-count":11,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2025,9]]}},"alternative-id":["S0963548325000100"],"URL":"https:\/\/doi.org\/10.1017\/s0963548325000100","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,26]]},"assertion":[{"value":"\u00a9 The Author(s), 2025. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}