[{"day":"01","arxiv":1,"acknowledgement":"This research was funded in whole or in part by the Austrian Science Fund (FWF) [10.55776/P36131 (Joshua Erde), 10.55776/I6502 (Mihyun Kang), 10.55776/ESP3863424 (Michael Anastos)] and by the Swiss National Science Foundation (SNSF) [P500-2_235474] (Vincent Pfenninger). For open access purposes, the authors have applied a CC BY public copyright license to any author accepted manuscript version arising from this submission. The authors thank the reviewers for helpful comments on the paper, and for bringing the particular form of Theorem 2.2 to our attention.","PlanS_conform":"1","publication":"Bulletin of the London Mathematical Society","volume":58,"intvolume":"        58","oa":1,"mathsc":["05C80","60F05"],"language":[{"iso":"eng"}],"OA_place":"publisher","year":"2026","supplementarymaterial":"no","date_created":"2026-08-23T22:01:47Z","_id":"22752","file_date_updated":"2026-09-07T13:53:26Z","author":[{"first_name":"Michael","full_name":"Anastos, Michael","last_name":"Anastos","id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb"},{"full_name":"Erde, Joshua","last_name":"Erde","first_name":"Joshua"},{"last_name":"Kang","full_name":"Kang, Mihyun","first_name":"Mihyun"},{"full_name":"Pfenninger, Vincent","last_name":"Pfenninger","first_name":"Vincent"}],"article_type":"original","quality_controlled":"1","title":"A short proof of a central limit theorem for the order of the giant component and k-core","scopus_import":"1","file":[{"content_type":"application/pdf","date_created":"2026-09-07T13:53:26Z","file_name":"2026_BulletinLondonMathSoc_Anastos.pdf","date_updated":"2026-09-07T13:53:26Z","file_size":248641,"file_id":"22845","access_level":"open_access","creator":"dernst","relation":"main_file","success":1,"checksum":"b4b21f05c3fc62fde243a5ddd46cef49"}],"publisher":"Wiley","publication_identifier":{"eissn":["1469-2120"],"issn":["0024-6093"]},"fulldoi":"https://doi.org/10.1112/blms.70464","date_updated":"2026-09-07T13:56:17Z","issue":"8","publication_status":"published","researchdata_availability":"no","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","department":[{"_id":"MaKw"}],"has_accepted_license":"1","article_processing_charge":"Yes (in subscription journal)","article_number":"e70464","license":"https://creativecommons.org/licenses/by/4.0/","OA_type":"hybrid","doi":"10.1112/blms.70464","project":[{"_id":"8f906bd2-16d5-11f0-9cad-e07be8aa9ac9","grant_number":"ESP3863424","name":"Combinatorial Optimisation Problems on Sparse Random Graphs"}],"status":"public","citation":{"ista":"Anastos M, Erde J, Kang M, Pfenninger V. 2026. A short proof of a central limit theorem for the order of the giant component and k-core. Bulletin of the London Mathematical Society. 58(8), e70464.","ama":"Anastos M, Erde J, Kang M, Pfenninger V. A short proof of a central limit theorem for the order of the giant component and k-core. <i>Bulletin of the London Mathematical Society</i>. 2026;58(8). doi:<a href=\"https://doi.org/10.1112/blms.70464\">10.1112/blms.70464</a>","chicago":"Anastos, Michael, Joshua Erde, Mihyun Kang, and Vincent Pfenninger. “A Short Proof of a Central Limit Theorem for the Order of the Giant Component and K-Core.” <i>Bulletin of the London Mathematical Society</i>. Wiley, 2026. <a href=\"https://doi.org/10.1112/blms.70464\">https://doi.org/10.1112/blms.70464</a>.","ieee":"M. Anastos, J. Erde, M. Kang, and V. Pfenninger, “A short proof of a central limit theorem for the order of the giant component and k-core,” <i>Bulletin of the London Mathematical Society</i>, vol. 58, no. 8. Wiley, 2026.","short":"M. Anastos, J. Erde, M. Kang, V. Pfenninger, Bulletin of the London Mathematical Society 58 (2026).","mla":"Anastos, Michael, et al. “A Short Proof of a Central Limit Theorem for the Order of the Giant Component and K-Core.” <i>Bulletin of the London Mathematical Society</i>, vol. 58, no. 8, e70464, Wiley, 2026, doi:<a href=\"https://doi.org/10.1112/blms.70464\">10.1112/blms.70464</a>.","apa":"Anastos, M., Erde, J., Kang, M., &#38; Pfenninger, V. (2026). A short proof of a central limit theorem for the order of the giant component and k-core. <i>Bulletin of the London Mathematical Society</i>. Wiley. <a href=\"https://doi.org/10.1112/blms.70464\">https://doi.org/10.1112/blms.70464</a>"},"ddc":["510"],"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png"},"date_published":"2026-08-01T00:00:00Z","type":"journal_article","external_id":{"arxiv":["2506.11651"]},"oa_version":"Published Version","das_tickbox":"0","abstract":[{"text":"In this note we outline a new and simple approach to proving central limit theorems for various ‘global’ graph parameters that have robust ‘local’ approximations, using the Efron–Stein inequality, which relies on a combinatorial analysis of the stability of these approximations under resampling an edge. As an application, we give short proofs of a central limit theorem for the order of the giant component and of the 𝑘\r\n-core for sparse random graphs.","lang":"eng"}],"month":"08"},{"department":[{"_id":"MaKw"}],"article_processing_charge":"No","publication_status":"published","issue":"9","date_updated":"2025-12-30T08:37:37Z","fulldoi":"https://doi.org/10.1002/jcd.21990","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ec_funded":1,"abstract":[{"lang":"eng","text":"In an  n×n  array filled with symbols, a transversal is a collection of entries with distinct rows, columns and symbols. In this note we show that if no symbol appears more than  βn  times, the array contains a transversal of size  (1−β/4−o(1))n . In particular, if the array is filled with  n  symbols, each appearing  n  times (an equi- n  square), we get transversals of size  (3/4−o(1))n. Moreover, our proof gives a deterministic algorithm with polynomial running time, that finds these transversals."}],"month":"09","external_id":{"arxiv":["2412.05891"],"isi":["001495472300001"]},"type":"journal_article","oa_version":"Preprint","citation":{"ista":"Anastos M, Morris P. 2025. A note on finding large transversals efficiently. Journal of Combinatorial Designs. 33(9), 338–342.","ama":"Anastos M, Morris P. A note on finding large transversals efficiently. <i>Journal of Combinatorial Designs</i>. 2025;33(9):338-342. doi:<a href=\"https://doi.org/10.1002/jcd.21990\">10.1002/jcd.21990</a>","chicago":"Anastos, Michael, and Patrick Morris. “A Note on Finding Large Transversals Efficiently.” <i>Journal of Combinatorial Designs</i>. Wiley, 2025. <a href=\"https://doi.org/10.1002/jcd.21990\">https://doi.org/10.1002/jcd.21990</a>.","ieee":"M. Anastos and P. Morris, “A note on finding large transversals efficiently,” <i>Journal of Combinatorial Designs</i>, vol. 33, no. 9. Wiley, pp. 338–342, 2025.","short":"M. Anastos, P. Morris, Journal of Combinatorial Designs 33 (2025) 338–342.","mla":"Anastos, Michael, and Patrick Morris. “A Note on Finding Large Transversals Efficiently.” <i>Journal of Combinatorial Designs</i>, vol. 33, no. 9, Wiley, 2025, pp. 338–42, doi:<a href=\"https://doi.org/10.1002/jcd.21990\">10.1002/jcd.21990</a>.","apa":"Anastos, M., &#38; Morris, P. (2025). A note on finding large transversals efficiently. <i>Journal of Combinatorial Designs</i>. Wiley. <a href=\"https://doi.org/10.1002/jcd.21990\">https://doi.org/10.1002/jcd.21990</a>"},"date_published":"2025-09-01T00:00:00Z","OA_type":"green","doi":"10.1002/jcd.21990","isi":1,"project":[{"grant_number":"ESP3863424","name":"Combinatorial Optimisation Problems on Sparse Random Graphs","_id":"8f906bd2-16d5-11f0-9cad-e07be8aa9ac9"},{"call_identifier":"H2020","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","name":"IST-BRIDGE: International postdoctoral program","grant_number":"101034413"}],"status":"public","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2412.05891","open_access":"1"}],"OA_place":"repository","language":[{"iso":"eng"}],"year":"2025","intvolume":"        33","oa":1,"publication":"Journal of Combinatorial Designs","volume":33,"acknowledgement":"We are very grateful to Matthew Kwan and Alp Müyesser with whom we had many interesting discussions leading to the results of this note. We also thank the anonymous reviewers for their suggestions improving the presentation of this note.\r\n\r\nMA was supported by the Austrian Science Fund (FWF) [10.55776/ESP3863424] and by the European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant—project number 101034413. PM was supported by the European Union's Horizon Europe Marie Skłodowska-Curie grant RAND-COMB-DESIGN—project number 101106032.","arxiv":1,"day":"01","scopus_import":"1","publication_identifier":{"issn":["1063-8539"],"eissn":["1520-6610"]},"publisher":"Wiley","author":[{"id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb","last_name":"Anastos","full_name":"Anastos, Michael","first_name":"Michael"},{"last_name":"Morris","full_name":"Morris, Patrick","first_name":"Patrick"}],"article_type":"original","title":"A note on finding large transversals efficiently","quality_controlled":"1","_id":"19798","page":"338-342","date_created":"2025-06-08T22:01:23Z"},{"department":[{"_id":"MaKw"}],"article_processing_charge":"Yes (via OA deal)","has_accepted_license":"1","publication_status":"published","date_updated":"2025-07-14T06:33:50Z","fulldoi":"https://doi.org/10.1145/3717823.3718173","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ec_funded":1,"external_id":{"arxiv":["2410.06095"]},"type":"conference","oa_version":"Published Version","abstract":[{"lang":"eng","text":"There is no known polynomial-time algorithm for graph isomorphism testing, but elementary combinatorial “refinement” algorithms seem to be very efficient in practice. Some philosophical justification for this phenomenon is provided by a classical theorem of Babai, Erdős and Selkow: an extremely simple polynomial-time combinatorial algorithm (variously known as “naïve refinement”, “naïve vertex classification”, “colour refinement” or the “1-dimensional Weisfeiler–Leman algorithm”) yields a so-called canonical labelling scheme for “almost all graphs”. More precisely, for a typical outcome of a random graph G(n,1/2), this simple combinatorial algorithm assigns labels to vertices in a way that easily permits isomorphism-testing against any other graph."}],"month":"06","OA_type":"hybrid","doi":"10.1145/3717823.3718173","status":"public","project":[{"_id":"bd95085b-d553-11ed-ba76-e55d3349be45","name":"Randomness and structure in combinatorics","grant_number":"101076777"},{"call_identifier":"H2020","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","name":"IST-BRIDGE: International postdoctoral program","grant_number":"101034413"},{"grant_number":"ESP3863424","name":"Combinatorial Optimisation Problems on Sparse Random Graphs","_id":"8f906bd2-16d5-11f0-9cad-e07be8aa9ac9"}],"citation":{"ieee":"M. Anastos, M. A. Kwan, and B. Moore, “Smoothed analysis for graph isomorphism,” in <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i>, Prague, Czechia, 2025, pp. 2098–2106.","short":"M. Anastos, M.A. Kwan, B. Moore, in:, Proceedings of the 57th Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, 2025, pp. 2098–2106.","ama":"Anastos M, Kwan MA, Moore B. Smoothed analysis for graph isomorphism. In: <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i>. Association for Computing Machinery; 2025:2098-2106. doi:<a href=\"https://doi.org/10.1145/3717823.3718173\">10.1145/3717823.3718173</a>","chicago":"Anastos, Michael, Matthew Alan Kwan, and Benjamin Moore. “Smoothed Analysis for Graph Isomorphism.” In <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i>, 2098–2106. Association for Computing Machinery, 2025. <a href=\"https://doi.org/10.1145/3717823.3718173\">https://doi.org/10.1145/3717823.3718173</a>.","ista":"Anastos M, Kwan MA, Moore B. 2025. Smoothed analysis for graph isomorphism. Proceedings of the 57th Annual ACM Symposium on Theory of Computing. STOC: Symposium on Theory of Computing, 2098–2106.","mla":"Anastos, Michael, et al. “Smoothed Analysis for Graph Isomorphism.” <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i>, Association for Computing Machinery, 2025, pp. 2098–106, doi:<a href=\"https://doi.org/10.1145/3717823.3718173\">10.1145/3717823.3718173</a>.","apa":"Anastos, M., Kwan, M. A., &#38; Moore, B. (2025). Smoothed analysis for graph isomorphism. In <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i> (pp. 2098–2106). Prague, Czechia: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3717823.3718173\">https://doi.org/10.1145/3717823.3718173</a>"},"ddc":["000"],"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png"},"date_published":"2025-06-15T00:00:00Z","conference":{"location":"Prague, Czechia","name":"STOC: Symposium on Theory of Computing","start_date":"2025-06-23","end_date":"2025-06-27"},"oa":1,"OA_place":"publisher","corr_author":"1","language":[{"iso":"eng"}],"year":"2025","acknowledgement":"All authors were supported by ERC Starting Grant “RANDSTRUCT” No. 101076777. Michael Anastos was also supported in part by the Austrian Science Fund (FWF)[10.55776/ESP3863424] and by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 101034413. For Open Access purposes, the authors have applied a CC BY public copyright license to any author accepted manuscript version arising from this submission.","arxiv":1,"day":"15","publication":"Proceedings of the 57th Annual ACM Symposium on Theory of Computing","author":[{"first_name":"Michael","id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb","last_name":"Anastos","full_name":"Anastos, Michael"},{"orcid":"0000-0002-4003-7567","first_name":"Matthew Alan","full_name":"Kwan, Matthew Alan","last_name":"Kwan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3"},{"first_name":"Benjamin","last_name":"Moore","full_name":"Moore, Benjamin","id":"6dc1a1be-bf1c-11ed-8d2b-d044840f49d6"}],"title":"Smoothed analysis for graph isomorphism","quality_controlled":"1","file":[{"relation":"main_file","creator":"dernst","access_level":"open_access","file_id":"20012","checksum":"cf0ab9cb9c6abda188de13dc3f9a4c9b","success":1,"file_size":706445,"date_updated":"2025-07-14T06:13:10Z","date_created":"2025-07-14T06:13:10Z","file_name":"2025_STOC_Anastos.pdf","content_type":"application/pdf"}],"scopus_import":"1","publication_identifier":{"isbn":["9798400715105"],"issn":["0737-8017"]},"publisher":"Association for Computing Machinery","file_date_updated":"2025-07-14T06:13:10Z","page":"2098-2106","_id":"20007","date_created":"2025-07-13T22:01:23Z"}]