[{"title":"On the chromatic number of powers of subdivisions of graphs","acknowledgement":"This work was initiated at the annual workshop of the Combinatorics and Graph Theory group of Freie Universität Berlin in Wilhelmsaue in September 2023. The authors would like to thank the institution for enabling this research. Finally, the fourth author would like to thank Tibor Szabó and the Combinatorics and Graph Theory group at Freie Universität Berlin for their hospitality during the research visit. Additionally, we thank Moharram Iradmusa for bringing the papers [5], [7] to our attention. Finally, we thank the anonymous referees for their suggestions on the manuscript, which have improved the quality of the document.\r\nM.A.: This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 101034413 .\r\nS.B.: The research leading to these results was supported by EPSRC, UK, grant no. EP/V048287/1. There are no additional data beyond that contained within the main manuscript.\r\nS.R.: Funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy – The Berlin Mathematics Research Center MATH+ (EXC-2046/1, project ID: 390685689).\r\nJ.R. acknowledges the support of the Grant PID2020-113082GB-I00 funded by MICIU/AEI/10.13039/501100011033, Spain, and the Severo Ochoa and María de Maeztu Program for Centers and Units of Excellence in R&D, Spain (CEX2020-001084-M).","language":[{"iso":"eng"}],"OA_place":"publisher","publisher":"Elsevier","type":"journal_article","page":"506-511","publication":"Discrete Applied Mathematics","abstract":[{"text":"For a given graph G=(V,E), we define its \\emph{nth subdivision} as the graph obtained from G by replacing every edge by a path of length n. We also define the \\emph{mth power} of G as the graph on vertex set V where we connect every pair of vertices at distance at most m in G. In this paper, we study the chromatic number of powers of subdivisions of graphs and resolve the case m=n asymptotically. In particular, our result confirms a conjecture of Mozafari-Nia and Iradmusa in the case m=n=3 in a strong sense.","lang":"eng"}],"citation":{"mla":"Anastos, Michael, et al. “On the Chromatic Number of Powers of Subdivisions of Graphs.” <i>Discrete Applied Mathematics</i>, vol. 360, Elsevier, 2025, pp. 506–11, doi:<a href=\"https://doi.org/10.1016/j.dam.2024.10.002\">10.1016/j.dam.2024.10.002</a>.","apa":"Anastos, M., Boyadzhiyska, S., Rathke, S., &#38; Rué, J. (2025). On the chromatic number of powers of subdivisions of graphs. <i>Discrete Applied Mathematics</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.dam.2024.10.002\">https://doi.org/10.1016/j.dam.2024.10.002</a>","ieee":"M. Anastos, S. Boyadzhiyska, S. Rathke, and J. Rué, “On the chromatic number of powers of subdivisions of graphs,” <i>Discrete Applied Mathematics</i>, vol. 360. Elsevier, pp. 506–511, 2025.","ama":"Anastos M, Boyadzhiyska S, Rathke S, Rué J. On the chromatic number of powers of subdivisions of graphs. <i>Discrete Applied Mathematics</i>. 2025;360:506-511. doi:<a href=\"https://doi.org/10.1016/j.dam.2024.10.002\">10.1016/j.dam.2024.10.002</a>","short":"M. Anastos, S. Boyadzhiyska, S. Rathke, J. Rué, Discrete Applied Mathematics 360 (2025) 506–511.","chicago":"Anastos, Michael, Simona Boyadzhiyska, Silas Rathke, and Juanjo Rué. “On the Chromatic Number of Powers of Subdivisions of Graphs.” <i>Discrete Applied Mathematics</i>. Elsevier, 2025. <a href=\"https://doi.org/10.1016/j.dam.2024.10.002\">https://doi.org/10.1016/j.dam.2024.10.002</a>.","ista":"Anastos M, Boyadzhiyska S, Rathke S, Rué J. 2025. On the chromatic number of powers of subdivisions of graphs. Discrete Applied Mathematics. 360, 506–511."},"oa":1,"date_updated":"2025-04-14T07:54:56Z","date_published":"2025-01-15T00:00:00Z","month":"01","external_id":{"isi":["001343647000001"],"arxiv":["2404.05542"]},"date_created":"2024-10-27T23:01:44Z","status":"public","article_processing_charge":"Yes (in subscription journal)","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)","image":"/images/cc_by.png","short":"CC BY (4.0)"},"doi":"10.1016/j.dam.2024.10.002","publication_identifier":{"issn":["0166-218X"]},"corr_author":"1","ec_funded":1,"file_date_updated":"2025-01-13T09:25:59Z","project":[{"call_identifier":"H2020","grant_number":"101034413","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","name":"IST-BRIDGE: International postdoctoral program"}],"publication_status":"published","article_type":"original","intvolume":"       360","volume":360,"oa_version":"Published Version","author":[{"id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb","full_name":"Anastos, Michael","last_name":"Anastos","first_name":"Michael"},{"full_name":"Boyadzhiyska, Simona","first_name":"Simona","last_name":"Boyadzhiyska"},{"full_name":"Rathke, Silas","last_name":"Rathke","first_name":"Silas"},{"full_name":"Rué, Juanjo","first_name":"Juanjo","last_name":"Rué"}],"has_accepted_license":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"date_created":"2025-01-13T09:25:59Z","file_name":"2025_DiscreteApplMath_Anastos.pdf","creator":"dernst","content_type":"application/pdf","access_level":"open_access","file_id":"18836","date_updated":"2025-01-13T09:25:59Z","success":1,"file_size":441060,"checksum":"bd20a13e56b3ea01daf5e7aca5247c60","relation":"main_file"}],"day":"15","arxiv":1,"ddc":["510"],"year":"2025","_id":"18478","scopus_import":"1","department":[{"_id":"MaKw"}],"isi":1,"OA_type":"hybrid","quality_controlled":"1"},{"ec_funded":1,"file_date_updated":"2025-04-03T11:24:35Z","project":[{"call_identifier":"H2020","name":"IST-BRIDGE: International postdoctoral program","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","grant_number":"101034413"},{"grant_number":"101076777","_id":"bd95085b-d553-11ed-ba76-e55d3349be45","name":"Randomness and structure in combinatorics"}],"publication_status":"published","intvolume":"        13","article_type":"original","file":[{"file_size":630297,"checksum":"f396270ad78c1ed67095c8e5a66fca26","relation":"main_file","file_id":"19468","date_updated":"2025-04-03T11:24:35Z","success":1,"content_type":"application/pdf","access_level":"open_access","file_name":"2025_ForumMathSigma_Anastos.pdf","date_created":"2025-04-03T11:24:35Z","creator":"dernst"}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","oa_version":"Published Version","has_accepted_license":"1","author":[{"full_name":"Anastos, Michael","id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb","first_name":"Michael","last_name":"Anastos"},{"last_name":"Jin","first_name":"Zhihan","full_name":"Jin, Zhihan"},{"orcid":"0000-0002-4003-7567","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","full_name":"Kwan, Matthew Alan","last_name":"Kwan","first_name":"Matthew Alan"},{"full_name":"Sudakov, Benny","last_name":"Sudakov","first_name":"Benny"}],"volume":13,"arxiv":1,"day":"14","_id":"19433","ddc":["510"],"year":"2025","department":[{"_id":"MaKw"}],"scopus_import":"1","quality_controlled":"1","OA_type":"gold","isi":1,"language":[{"iso":"eng"}],"acknowledgement":"We would like to thank Timo Seppäläinen for some illuminating discussion about random high-dimensional orders and for bringing our attention to [59]. We would also like to thank the referees for helpful feedback. Michael Anastos is supported by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 101034413. Matthew Kwan is supported by ERC Starting Grant ‘RANDSTRUCT’ No. 101076777, also funded by the European Union. Zhihan Jin and Benny Sudakov are supported by SNSF grant 200021-228014.","title":"Extremal, enumerative and probabilistic results on ordered hypergraph matchings","type":"journal_article","publisher":"Cambridge University Press","OA_place":"publisher","publication":"Forum of Mathematics, Sigma","date_published":"2025-03-14T00:00:00Z","month":"03","article_number":"e55","date_updated":"2025-09-30T11:18:57Z","citation":{"short":"M. Anastos, Z. Jin, M.A. Kwan, B. Sudakov, Forum of Mathematics, Sigma 13 (2025).","ama":"Anastos M, Jin Z, Kwan MA, Sudakov B. Extremal, enumerative and probabilistic results on ordered hypergraph matchings. <i>Forum of Mathematics, Sigma</i>. 2025;13. doi:<a href=\"https://doi.org/10.1017/fms.2024.144\">10.1017/fms.2024.144</a>","ieee":"M. Anastos, Z. Jin, M. A. Kwan, and B. Sudakov, “Extremal, enumerative and probabilistic results on ordered hypergraph matchings,” <i>Forum of Mathematics, Sigma</i>, vol. 13. Cambridge University Press, 2025.","ista":"Anastos M, Jin Z, Kwan MA, Sudakov B. 2025. Extremal, enumerative and probabilistic results on ordered hypergraph matchings. Forum of Mathematics, Sigma. 13, e55.","chicago":"Anastos, Michael, Zhihan Jin, Matthew Alan Kwan, and Benny Sudakov. “Extremal, Enumerative and Probabilistic Results on Ordered Hypergraph Matchings.” <i>Forum of Mathematics, Sigma</i>. Cambridge University Press, 2025. <a href=\"https://doi.org/10.1017/fms.2024.144\">https://doi.org/10.1017/fms.2024.144</a>.","mla":"Anastos, Michael, et al. “Extremal, Enumerative and Probabilistic Results on Ordered Hypergraph Matchings.” <i>Forum of Mathematics, Sigma</i>, vol. 13, e55, Cambridge University Press, 2025, doi:<a href=\"https://doi.org/10.1017/fms.2024.144\">10.1017/fms.2024.144</a>.","apa":"Anastos, M., Jin, Z., Kwan, M. A., &#38; Sudakov, B. (2025). Extremal, enumerative and probabilistic results on ordered hypergraph matchings. <i>Forum of Mathematics, Sigma</i>. Cambridge University Press. <a href=\"https://doi.org/10.1017/fms.2024.144\">https://doi.org/10.1017/fms.2024.144</a>"},"oa":1,"abstract":[{"lang":"eng","text":"An ordered r-matching is an r-uniform hypergraph matching equipped with an ordering on its vertices. These objects can be viewed as natural generalisations of r-dimensional orders. The theory of ordered 2-matchings is well developed and has connections and applications to extremal and enumerative combinatorics, probability and geometry. On the other hand, in the case  r≥3 much less is known, largely due to a lack of powerful bijective tools. Recently, Dudek, Grytczuk and Ruciński made some first steps towards a general theory of ordered r-matchings, and in this paper we substantially improve several of their results and introduce some new directions of study. Many intriguing open questions remain."}],"status":"public","date_created":"2025-03-20T12:59:14Z","external_id":{"arxiv":["2308.12268"],"isi":["001444429200001"]},"publication_identifier":{"issn":["2050-5094"]},"doi":"10.1017/fms.2024.144","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)","image":"/images/cc_by.png","short":"CC BY (4.0)"},"article_processing_charge":"Yes","corr_author":"1"},{"publication":"Random Structures and Algorithms","date_updated":"2025-09-30T11:15:41Z","month":"03","date_published":"2025-03-01T00:00:00Z","article_number":"e21286","abstract":[{"lang":"eng","text":"Let μ(G) denote the minimum number of edges whose addition to G results in a Hamiltonian graph, and let μ^(G) denote the minimum number of edges whose addition to G results in a pancyclic graph. We study the distributions of μ(G),μ^(G) in the context of binomial random graphs. Letting d=d(n):=n⋅p, we prove that there exists a function f:R+→[0,1] of order f(d)=12de−d+e−d+O(d6e−3d) such that, if G∼G(n,p) with 20≤d(n)≤0.4logn, then with high probability μ(G)=(1+o(1))⋅f(d)⋅n. Let ni(G) denote the number of degree i vertices in G. A trivial lower bound on μ(G) is given by the expression n0(G)+⌈12n1(G)⌉. In the denser regime of random graphs, we show that if np−13logn−2loglogn→∞ and G∼G(n,p) then, with high probability, μ(G)=n0(G)+⌈12n1(G)⌉. For completion to pancyclicity, we show that if G∼G(n,p) and np≥20 then, with high probability, μ^(G)=μ(G). Finally, we present a polynomial time algorithm such that, if G∼G(n,p) and np≥20, then, with high probability, the algorithm returns a set of edges of size μ(G) whose addition to G results in a pancyclic (and therefore also Hamiltonian) graph."}],"oa":1,"citation":{"apa":"Alon, Y., &#38; Anastos, M. (2025). The completion numbers of hamiltonicity and pancyclicity in random graphs. <i>Random Structures and Algorithms</i>. Wiley. <a href=\"https://doi.org/10.1002/rsa.21286\">https://doi.org/10.1002/rsa.21286</a>","mla":"Alon, Yahav, and Michael Anastos. “The Completion Numbers of Hamiltonicity and Pancyclicity in Random Graphs.” <i>Random Structures and Algorithms</i>, vol. 66, no. 2, e21286, Wiley, 2025, doi:<a href=\"https://doi.org/10.1002/rsa.21286\">10.1002/rsa.21286</a>.","ista":"Alon Y, Anastos M. 2025. The completion numbers of hamiltonicity and pancyclicity in random graphs. Random Structures and Algorithms. 66(2), e21286.","chicago":"Alon, Yahav, and Michael Anastos. “The Completion Numbers of Hamiltonicity and Pancyclicity in Random Graphs.” <i>Random Structures and Algorithms</i>. Wiley, 2025. <a href=\"https://doi.org/10.1002/rsa.21286\">https://doi.org/10.1002/rsa.21286</a>.","ama":"Alon Y, Anastos M. The completion numbers of hamiltonicity and pancyclicity in random graphs. <i>Random Structures and Algorithms</i>. 2025;66(2). doi:<a href=\"https://doi.org/10.1002/rsa.21286\">10.1002/rsa.21286</a>","short":"Y. Alon, M. Anastos, Random Structures and Algorithms 66 (2025).","ieee":"Y. Alon and M. Anastos, “The completion numbers of hamiltonicity and pancyclicity in random graphs,” <i>Random Structures and Algorithms</i>, vol. 66, no. 2. Wiley, 2025."},"language":[{"iso":"eng"}],"acknowledgement":"The authors would like to express their thanks to the referees of the article for their valuable input towards improving the presentation of our result. This project has received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 101034413.","issue":"2","title":"The completion numbers of hamiltonicity and pancyclicity in random graphs","type":"journal_article","OA_place":"publisher","publisher":"Wiley","publication_identifier":{"issn":["1042-9832"],"eissn":["1098-2418"]},"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by-nc/4.0/legalcode","name":"Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)","image":"/images/cc_by_nc.png","short":"CC BY-NC (4.0)"},"article_processing_charge":"Yes (in subscription journal)","doi":"10.1002/rsa.21286","external_id":{"isi":["001420226800001"],"arxiv":["2304.03710"]},"date_created":"2025-03-23T23:01:26Z","status":"public","article_type":"original","intvolume":"        66","file":[{"content_type":"application/pdf","access_level":"open_access","date_created":"2025-03-25T11:46:27Z","file_name":"2025_RandomStruc_Alon.pdf","creator":"dernst","checksum":"6067747e805fa356d560dc45f2a89918","file_size":549236,"relation":"main_file","file_id":"19459","date_updated":"2025-03-25T11:46:27Z","success":1}],"volume":66,"oa_version":"Published Version","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","has_accepted_license":"1","author":[{"first_name":"Yahav","last_name":"Alon","full_name":"Alon, Yahav"},{"last_name":"Anastos","first_name":"Michael","id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb","full_name":"Anastos, Michael"}],"ec_funded":1,"file_date_updated":"2025-03-25T11:46:27Z","publication_status":"published","project":[{"grant_number":"101034413","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","name":"IST-BRIDGE: International postdoctoral program","call_identifier":"H2020"}],"department":[{"_id":"MaKw"}],"scopus_import":"1","quality_controlled":"1","OA_type":"hybrid","isi":1,"arxiv":1,"day":"01","_id":"19440","year":"2025","ddc":["510"]},{"publication_identifier":{"issn":["1063-8539"],"eissn":["1520-6610"]},"article_processing_charge":"No","doi":"10.1002/jcd.21990","status":"public","date_created":"2025-06-08T22:01:23Z","external_id":{"isi":["001495472300001"],"arxiv":["2412.05891"]},"month":"09","date_published":"2025-09-01T00:00:00Z","date_updated":"2025-12-30T08:37:37Z","citation":{"short":"M. Anastos, P. Morris, Journal of Combinatorial Designs 33 (2025) 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>","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.","ista":"Anastos M, Morris P. 2025. A note on finding large transversals efficiently. Journal of Combinatorial Designs. 33(9), 338–342.","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>.","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>"},"oa":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."}],"main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2412.05891"}],"publication":"Journal of Combinatorial Designs","page":"338-342","type":"journal_article","publisher":"Wiley","OA_place":"repository","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.","language":[{"iso":"eng"}],"title":"A note on finding large transversals efficiently","issue":"9","OA_type":"green","quality_controlled":"1","isi":1,"department":[{"_id":"MaKw"}],"scopus_import":"1","_id":"19798","year":"2025","arxiv":1,"day":"01","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Preprint","author":[{"full_name":"Anastos, Michael","id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb","last_name":"Anastos","first_name":"Michael"},{"last_name":"Morris","first_name":"Patrick","full_name":"Morris, Patrick"}],"volume":33,"intvolume":"        33","article_type":"original","project":[{"name":"Combinatorial Optimisation Problems on Sparse Random Graphs","_id":"8f906bd2-16d5-11f0-9cad-e07be8aa9ac9","grant_number":"ESP3863424"},{"call_identifier":"H2020","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","grant_number":"101034413","name":"IST-BRIDGE: International postdoctoral program"}],"publication_status":"published","ec_funded":1},{"corr_author":"1","doi":"10.1145/3717823.3718173","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)","image":"/images/cc_by.png","short":"CC BY (4.0)"},"article_processing_charge":"Yes (via OA deal)","publication_identifier":{"issn":["0737-8017"],"isbn":["9798400715105"]},"status":"public","date_created":"2025-07-13T22:01:23Z","external_id":{"arxiv":["2410.06095"]},"oa":1,"citation":{"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>","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>.","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.","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.","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>","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."},"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."}],"date_published":"2025-06-15T00:00:00Z","conference":{"end_date":"2025-06-27","name":"STOC: Symposium on Theory of Computing","location":"Prague, Czechia","start_date":"2025-06-23"},"month":"06","date_updated":"2025-07-14T06:33:50Z","publication":"Proceedings of the 57th Annual ACM Symposium on Theory of Computing","page":"2098-2106","publisher":"Association for Computing Machinery","OA_place":"publisher","type":"conference","title":"Smoothed analysis for graph isomorphism","language":[{"iso":"eng"}],"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.","OA_type":"hybrid","quality_controlled":"1","scopus_import":"1","department":[{"_id":"MaKw"}],"ddc":["000"],"year":"2025","_id":"20007","day":"15","arxiv":1,"author":[{"id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb","full_name":"Anastos, Michael","last_name":"Anastos","first_name":"Michael"},{"orcid":"0000-0002-4003-7567","full_name":"Kwan, Matthew Alan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","last_name":"Kwan","first_name":"Matthew Alan"},{"last_name":"Moore","first_name":"Benjamin","full_name":"Moore, Benjamin","id":"6dc1a1be-bf1c-11ed-8d2b-d044840f49d6"}],"oa_version":"Published Version","has_accepted_license":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"date_updated":"2025-07-14T06:13:10Z","file_id":"20012","success":1,"checksum":"cf0ab9cb9c6abda188de13dc3f9a4c9b","file_size":706445,"relation":"main_file","date_created":"2025-07-14T06:13:10Z","file_name":"2025_STOC_Anastos.pdf","creator":"dernst","content_type":"application/pdf","access_level":"open_access"}],"project":[{"grant_number":"101076777","_id":"bd95085b-d553-11ed-ba76-e55d3349be45","name":"Randomness and structure in combinatorics"},{"name":"IST-BRIDGE: International postdoctoral program","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","grant_number":"101034413","call_identifier":"H2020"},{"_id":"8f906bd2-16d5-11f0-9cad-e07be8aa9ac9","grant_number":"ESP3863424","name":"Combinatorial Optimisation Problems on Sparse Random Graphs"}],"publication_status":"published","ec_funded":1,"file_date_updated":"2025-07-14T06:13:10Z"},{"article_processing_charge":"Yes (via OA deal)","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)","image":"/images/cc_by.png","short":"CC BY (4.0)"},"doi":"10.1112/jlms.70010","publication_identifier":{"issn":["0024-6107"],"eissn":["1469-7750"]},"corr_author":"1","status":"public","date_created":"2024-11-24T23:01:48Z","external_id":{"isi":["001374738100001"],"arxiv":["2307.06453"]},"publication":"Journal of the London Mathematical Society","citation":{"ama":"Anastos M, Cooley O, Kang M, Kwan MA. Partitioning problems via random processes. <i>Journal of the London Mathematical Society</i>. 2024;110(6). doi:<a href=\"https://doi.org/10.1112/jlms.70010\">10.1112/jlms.70010</a>","short":"M. Anastos, O. Cooley, M. Kang, M.A. Kwan, Journal of the London Mathematical Society 110 (2024).","ieee":"M. Anastos, O. Cooley, M. Kang, and M. A. Kwan, “Partitioning problems via random processes,” <i>Journal of the London Mathematical Society</i>, vol. 110, no. 6. Wiley, 2024.","ista":"Anastos M, Cooley O, Kang M, Kwan MA. 2024. Partitioning problems via random processes. Journal of the London Mathematical Society. 110(6), e70010.","chicago":"Anastos, Michael, Oliver Cooley, Mihyun Kang, and Matthew Alan Kwan. “Partitioning Problems via Random Processes.” <i>Journal of the London Mathematical Society</i>. Wiley, 2024. <a href=\"https://doi.org/10.1112/jlms.70010\">https://doi.org/10.1112/jlms.70010</a>.","mla":"Anastos, Michael, et al. “Partitioning Problems via Random Processes.” <i>Journal of the London Mathematical Society</i>, vol. 110, no. 6, e70010, Wiley, 2024, doi:<a href=\"https://doi.org/10.1112/jlms.70010\">10.1112/jlms.70010</a>.","apa":"Anastos, M., Cooley, O., Kang, M., &#38; Kwan, M. A. (2024). Partitioning problems via random processes. <i>Journal of the London Mathematical Society</i>. Wiley. <a href=\"https://doi.org/10.1112/jlms.70010\">https://doi.org/10.1112/jlms.70010</a>"},"oa":1,"abstract":[{"text":"There are a number of well-known problems and conjectures about partitioning graphs to satisfy local constraints. For example, the majority colouring conjecture of Kreutzer, Oum, Seymour, van der Zypen and Wood states that every directed graph has a 3-colouring such that for every vertex v, at most half of the out-neighbours of v have the same colour as \r\n. As another example, the internal partition conjecture, due to DeVos and to Ban and Linial, states that for every d, all but finitely many d-regular graphs have a partition into two non-empty parts such that for every vertex v, at least half of the neighbours of v lie in the same part as v. We prove several results in this spirit: in particular, two of our results are that the majority colouring conjecture holds for Erdős–Rényi random directed graphs (of any density), and that the internal partition conjecture holds if we permit a tiny number of ‘exceptional vertices’. Our proofs involve a variety of techniques, including several different methods to analyse random recolouring processes. One highlight is a personality-changing scheme: we ‘forget’ certain information based on the state of a Markov chain, giving us more independence to work with.","lang":"eng"}],"date_published":"2024-12-01T00:00:00Z","article_number":"e70010","month":"12","date_updated":"2025-12-02T13:52:26Z","title":"Partitioning problems via random processes","issue":"6","language":[{"iso":"eng"}],"acknowledgement":"We are grateful to the anonymous referees for their thorough reading of the paper, and for many suggestions which have improved the exposition throughout.\r\n\r\nMichael Anastos was supported by the European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 101034413. Matthew Kwan was supported by ERC Starting Grant ‘RANDSTRUCT’ No. 101076777, also funded by the European Union image. Mihyun Kang was supported in part by the Austrian Science Fund (FWF) [10.55776/I6502]. For the purpose of open access, the authors have applied a CC-BY public copyright licence to any Author Accepted Manuscript version arising from this submission.","publisher":"Wiley","OA_place":"publisher","type":"journal_article","scopus_import":"1","department":[{"_id":"MaKw"}],"isi":1,"OA_type":"hybrid","quality_controlled":"1","day":"01","arxiv":1,"year":"2024","ddc":["510"],"_id":"18583","intvolume":"       110","article_type":"original","has_accepted_license":"1","oa_version":"Published Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb","full_name":"Anastos, Michael","last_name":"Anastos","first_name":"Michael"},{"first_name":"Oliver","last_name":"Cooley","id":"43f4ddd0-a46b-11ec-8df6-ef3703bd721d","full_name":"Cooley, Oliver"},{"first_name":"Mihyun","last_name":"Kang","full_name":"Kang, Mihyun"},{"id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","full_name":"Kwan, Matthew Alan","orcid":"0000-0002-4003-7567","first_name":"Matthew Alan","last_name":"Kwan"}],"volume":110,"file":[{"creator":"dernst","date_created":"2024-12-10T08:10:39Z","file_name":"2024_JournLondonMathSoc_Anastos.pdf","access_level":"open_access","content_type":"application/pdf","success":1,"file_id":"18639","date_updated":"2024-12-10T08:10:39Z","relation":"main_file","file_size":539891,"checksum":"98e301e0565d75e3fb50e10e982a5018"}],"file_date_updated":"2024-12-10T08:10:39Z","ec_funded":1,"publication_status":"published","project":[{"call_identifier":"H2020","grant_number":"101034413","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","name":"IST-BRIDGE: International postdoctoral program"},{"_id":"bd95085b-d553-11ed-ba76-e55d3349be45","grant_number":"101076777","name":"Randomness and structure in combinatorics"}]},{"publication":"Electronic Communications in Probability","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2311.16631","open_access":"1"}],"abstract":[{"text":"Let Qd be the d-dimensional binary hypercube. We say that P={v1,…,vk} is an increasing path of length k−1 in Qd, if for every i∈[k−1] the edge vivi+1 is obtained by switching some zero coordinate in vi to a one coordinate in vi+1.\r\nForm a random subgraph Qdp by retaining each edge in E(Qd) independently with probability p. We show that there is a phase transition with respect to the length of a longest increasing path around p=ed. Let α be a constant and let p=αd. When α<e, then there exists a δ∈[0,1) such that whp a longest increasing path in Qdp is of length at most δd. On the other hand, when α>e, whp there is a path of length d−2 in Qdp, and in fact, whether it is of length d−2,d−1, or d depends on whether the all-zero and all-one vertices percolate or not.","lang":"eng"}],"citation":{"mla":"Anastos, Michael, et al. “Climbing up a Random Subgraph of the Hypercube.” <i>Electronic Communications in Probability</i>, vol. 29, 70, Duke University Press, 2024, doi:<a href=\"https://doi.org/10.1214/24-ECP639\">10.1214/24-ECP639</a>.","apa":"Anastos, M., Diskin, S., Elboim, D., &#38; Krivelevich, M. (2024). Climbing up a random subgraph of the hypercube. <i>Electronic Communications in Probability</i>. Duke University Press. <a href=\"https://doi.org/10.1214/24-ECP639\">https://doi.org/10.1214/24-ECP639</a>","ieee":"M. Anastos, S. Diskin, D. Elboim, and M. Krivelevich, “Climbing up a random subgraph of the hypercube,” <i>Electronic Communications in Probability</i>, vol. 29. Duke University Press, 2024.","short":"M. Anastos, S. Diskin, D. Elboim, M. Krivelevich, Electronic Communications in Probability 29 (2024).","ama":"Anastos M, Diskin S, Elboim D, Krivelevich M. Climbing up a random subgraph of the hypercube. <i>Electronic Communications in Probability</i>. 2024;29. doi:<a href=\"https://doi.org/10.1214/24-ECP639\">10.1214/24-ECP639</a>","chicago":"Anastos, Michael, Sahar Diskin, Dor Elboim, and Michael Krivelevich. “Climbing up a Random Subgraph of the Hypercube.” <i>Electronic Communications in Probability</i>. Duke University Press, 2024. <a href=\"https://doi.org/10.1214/24-ECP639\">https://doi.org/10.1214/24-ECP639</a>.","ista":"Anastos M, Diskin S, Elboim D, Krivelevich M. 2024. Climbing up a random subgraph of the hypercube. Electronic Communications in Probability. 29, 70."},"oa":1,"date_updated":"2025-09-09T11:46:53Z","month":"11","date_published":"2024-11-24T00:00:00Z","article_number":"70","title":"Climbing up a random subgraph of the hypercube","acknowledgement":"Research supported by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 101034413.\r\nThe authors wish to thank Ross Pinsky for his comments on an earlier version of the paper, and for bringing reference [12] to our attention. The authors are grateful to the anonymous referees for their helpful comments and suggestions.","language":[{"iso":"eng"}],"OA_place":"repository","publisher":"Duke University Press","DOAJ_listed":"1","type":"journal_article","article_processing_charge":"Yes","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)","image":"/images/cc_by.png","short":"CC BY (4.0)"},"doi":"10.1214/24-ECP639","publication_identifier":{"eissn":["1083-589X"]},"corr_author":"1","date_created":"2024-12-15T23:01:51Z","external_id":{"isi":["001356019700001"],"arxiv":["2311.16631"]},"status":"public","article_type":"original","intvolume":"        29","volume":29,"has_accepted_license":"1","oa_version":"Published Version","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","author":[{"id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb","full_name":"Anastos, Michael","last_name":"Anastos","first_name":"Michael"},{"first_name":"Sahar","last_name":"Diskin","full_name":"Diskin, Sahar"},{"full_name":"Elboim, Dor","first_name":"Dor","last_name":"Elboim"},{"first_name":"Michael","last_name":"Krivelevich","full_name":"Krivelevich, Michael"}],"file":[{"success":1,"date_updated":"2024-12-16T07:33:34Z","file_id":"18657","relation":"main_file","file_size":530169,"checksum":"307a9d049325e6ca9bfe8b4a1f275983","creator":"dernst","date_created":"2024-12-16T07:33:34Z","file_name":"2024_ElectrCommProbability_Anastos.pdf","access_level":"open_access","content_type":"application/pdf"}],"ec_funded":1,"file_date_updated":"2024-12-16T07:33:34Z","project":[{"call_identifier":"H2020","name":"IST-BRIDGE: International postdoctoral program","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","grant_number":"101034413"}],"publication_status":"published","scopus_import":"1","department":[{"_id":"MaKw"}],"isi":1,"OA_type":"gold","quality_controlled":"1","day":"24","arxiv":1,"year":"2024","ddc":["510"],"_id":"18655"},{"intvolume":"     15364","volume":15364,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Preprint","author":[{"id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb","full_name":"Anastos, Michael","last_name":"Anastos","first_name":"Michael"},{"orcid":"0000-0002-7553-6606","id":"D33D2B18-E445-11E9-ABB7-15F4E5697425","full_name":"Auerbach, Benedikt","last_name":"Auerbach","first_name":"Benedikt"},{"full_name":"Baig, Mirza Ahad","id":"3EDE6DE4-AA5A-11E9-986D-341CE6697425","first_name":"Mirza Ahad","last_name":"Baig"},{"orcid":"0000-0002-2505-4246","id":"ffc563a3-f6e0-11ea-865d-e3cce03d17cc","full_name":"Cueto Noval, Miguel","first_name":"Miguel","last_name":"Cueto Noval"},{"orcid":"0000-0002-4003-7567","full_name":"Kwan, Matthew Alan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","last_name":"Kwan","first_name":"Matthew Alan"},{"orcid":"0000-0001-8630-415X","id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87","full_name":"Pascual Perez, Guillermo","first_name":"Guillermo","last_name":"Pascual Perez"},{"first_name":"Krzysztof Z","last_name":"Pietrzak","orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","full_name":"Pietrzak, Krzysztof Z"}],"publication_status":"published","scopus_import":"1","department":[{"_id":"MaKw"},{"_id":"KrPi"}],"alternative_title":["LNCS"],"isi":1,"quality_controlled":"1","OA_type":"green","day":"02","year":"2024","_id":"18702","page":"413-443","publication":"22nd International Conference on Theory of Cryptography","main_file_link":[{"url":"https://eprint.iacr.org/2024/1097","open_access":"1"}],"abstract":[{"text":"In this work we prove lower bounds on the (communication) cost of maintaining a shared key among a dynamic group of users. Being “dynamic” means one can add and remove users from the group. This captures important protocols like multicast encryption (ME) and continuous group-key agreement (CGKA), which is the primitive underlying many group messaging applications. We prove our bounds in a combinatorial setting where the state of the protocol progresses in rounds. The state of the protocol in each round is captured by a set system, with each of its elements specifying a set of users who share a secret key. We show this combinatorial model implies bounds in symbolic models for ME and CGKA that capture, as building blocks, PRGs, PRFs, dual PRFs, secret sharing, and symmetric encryption in the setting of ME, and PRGs, PRFs, dual PRFs, secret sharing, public-key encryption, and key-updatable public-key encryption in the setting of CGKA. The models are related to the ones used by Micciancio and Panjwani (Eurocrypt’04) and Bienstock et al. (TCC’20) to analyze ME and CGKA, respectively. We prove – using the Bollobás’ Set Pairs Inequality – that the cost (number of uploaded ciphertexts) for replacing a set of d users in a group of size n is Ω(dln(n/d)). Our lower bound is asymptotically tight and both improves on a bound of Ω(d) by Bienstock et al. (TCC’20), and generalizes a result by Micciancio and Panjwani (Eurocrypt’04), who proved a lower bound of Ω(log(n)) for d=1. ","lang":"eng"}],"citation":{"chicago":"Anastos, Michael, Benedikt Auerbach, Mirza Ahad Baig, Miguel Cueto Noval, Matthew Alan Kwan, Guillermo Pascual Perez, and Krzysztof Z Pietrzak. “The Cost of Maintaining Keys in Dynamic Groups with Applications to Multicast Encryption and Group Messaging.” In <i>22nd International Conference on Theory of Cryptography</i>, 15364:413–43. Springer Nature, 2024. <a href=\"https://doi.org/10.1007/978-3-031-78011-0_14\">https://doi.org/10.1007/978-3-031-78011-0_14</a>.","ista":"Anastos M, Auerbach B, Baig MA, Cueto Noval M, Kwan MA, Pascual Perez G, Pietrzak KZ. 2024. The cost of maintaining keys in dynamic groups with applications to multicast encryption and group messaging. 22nd International Conference on Theory of Cryptography. TCC: Theory of Cryptography, LNCS, vol. 15364, 413–443.","ieee":"M. Anastos <i>et al.</i>, “The cost of maintaining keys in dynamic groups with applications to multicast encryption and group messaging,” in <i>22nd International Conference on Theory of Cryptography</i>, Milan, Italy, 2024, vol. 15364, pp. 413–443.","ama":"Anastos M, Auerbach B, Baig MA, et al. The cost of maintaining keys in dynamic groups with applications to multicast encryption and group messaging. In: <i>22nd International Conference on Theory of Cryptography</i>. Vol 15364. Springer Nature; 2024:413-443. doi:<a href=\"https://doi.org/10.1007/978-3-031-78011-0_14\">10.1007/978-3-031-78011-0_14</a>","short":"M. Anastos, B. Auerbach, M.A. Baig, M. Cueto Noval, M.A. Kwan, G. Pascual Perez, K.Z. Pietrzak, in:, 22nd International Conference on Theory of Cryptography, Springer Nature, 2024, pp. 413–443.","apa":"Anastos, M., Auerbach, B., Baig, M. A., Cueto Noval, M., Kwan, M. A., Pascual Perez, G., &#38; Pietrzak, K. Z. (2024). The cost of maintaining keys in dynamic groups with applications to multicast encryption and group messaging. In <i>22nd International Conference on Theory of Cryptography</i> (Vol. 15364, pp. 413–443). Milan, Italy: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-78011-0_14\">https://doi.org/10.1007/978-3-031-78011-0_14</a>","mla":"Anastos, Michael, et al. “The Cost of Maintaining Keys in Dynamic Groups with Applications to Multicast Encryption and Group Messaging.” <i>22nd International Conference on Theory of Cryptography</i>, vol. 15364, Springer Nature, 2024, pp. 413–43, doi:<a href=\"https://doi.org/10.1007/978-3-031-78011-0_14\">10.1007/978-3-031-78011-0_14</a>."},"oa":1,"date_updated":"2025-12-02T13:55:46Z","date_published":"2024-12-02T00:00:00Z","conference":{"location":"Milan, Italy","start_date":"2024-12-02","name":"TCC: Theory of Cryptography","end_date":"2024-12-06"},"month":"12","title":"The cost of maintaining keys in dynamic groups with applications to multicast encryption and group messaging","language":[{"iso":"eng"}],"OA_place":"repository","publisher":"Springer Nature","type":"conference","doi":"10.1007/978-3-031-78011-0_14","article_processing_charge":"No","publication_identifier":{"issn":["0302-9743"],"isbn":["9783031780103"],"eissn":["1611-3349"]},"corr_author":"1","external_id":{"isi":["001545628900014"]},"date_created":"2024-12-22T23:01:47Z","status":"public"},{"volume":30,"has_accepted_license":"1","oa_version":"Published Version","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","author":[{"full_name":"Anastos, Michael","id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb","first_name":"Michael","last_name":"Anastos"}],"file":[{"relation":"main_file","file_size":448736,"checksum":"6269ed3b3eded6536d3d9d6baad2d5b9","success":1,"file_id":"13046","date_updated":"2023-05-22T07:43:19Z","access_level":"open_access","content_type":"application/pdf","creator":"dernst","file_name":"2023_JourCombinatorics_Anastos.pdf","date_created":"2023-05-22T07:43:19Z"}],"article_type":"original","intvolume":"        30","publication_status":"published","file_date_updated":"2023-05-22T07:43:19Z","isi":1,"quality_controlled":"1","scopus_import":"1","department":[{"_id":"MaKw"}],"year":"2023","ddc":["510"],"_id":"13042","day":"05","arxiv":1,"abstract":[{"text":"Let Lc,n denote the size of the longest cycle in G(n, c/n),c >1 constant.  We show that there exists a continuous function f(c) such that Lc,n/n→f(c) a.s.  for c>20,  thus  extending  a  result  of  Frieze  and  the  author  to  smaller  values  of c. Thereafter,  for c>20,  we  determine  the  limit  of  the  probability  that G(n, c/n)contains  cycles  of  every  length  between  the  length  of  its  shortest  and  its  longest cycles as n→∞.","lang":"eng"}],"oa":1,"citation":{"chicago":"Anastos, Michael. “A Note on Long Cycles in Sparse Random Graphs.” <i>Electronic Journal of Combinatorics</i>. Electronic Journal of Combinatorics, 2023. <a href=\"https://doi.org/10.37236/11471\">https://doi.org/10.37236/11471</a>.","ista":"Anastos M. 2023. A note on long cycles in sparse random graphs. Electronic Journal of Combinatorics. 30(2), P2.21.","ieee":"M. Anastos, “A note on long cycles in sparse random graphs,” <i>Electronic Journal of Combinatorics</i>, vol. 30, no. 2. Electronic Journal of Combinatorics, 2023.","ama":"Anastos M. A note on long cycles in sparse random graphs. <i>Electronic Journal of Combinatorics</i>. 2023;30(2). doi:<a href=\"https://doi.org/10.37236/11471\">10.37236/11471</a>","short":"M. Anastos, Electronic Journal of Combinatorics 30 (2023).","apa":"Anastos, M. (2023). A note on long cycles in sparse random graphs. <i>Electronic Journal of Combinatorics</i>. Electronic Journal of Combinatorics. <a href=\"https://doi.org/10.37236/11471\">https://doi.org/10.37236/11471</a>","mla":"Anastos, Michael. “A Note on Long Cycles in Sparse Random Graphs.” <i>Electronic Journal of Combinatorics</i>, vol. 30, no. 2, P2.21, Electronic Journal of Combinatorics, 2023, doi:<a href=\"https://doi.org/10.37236/11471\">10.37236/11471</a>."},"date_updated":"2024-10-09T21:05:26Z","date_published":"2023-05-05T00:00:00Z","article_number":"P2.21","month":"05","publication":"Electronic Journal of Combinatorics","publisher":"Electronic Journal of Combinatorics","type":"journal_article","issue":"2","title":"A note on long cycles in sparse random graphs","acknowledgement":"We would like to thank the reviewers for their helpful comments and remarks.","language":[{"iso":"eng"}],"corr_author":"1","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)","image":"/images/cc_by.png","short":"CC BY (4.0)"},"doi":"10.37236/11471","article_processing_charge":"No","publication_identifier":{"eissn":["1077-8926"]},"external_id":{"isi":["000988285500001"],"arxiv":["2105.13828"]},"date_created":"2023-05-21T22:01:05Z","status":"public"},{"publication":"Electronic Journal of Combinatorics","abstract":[{"lang":"eng","text":"We study multigraphs whose edge-sets are the union of three perfect matchings, M1, M2, and M3. Given such a graph G and any a1; a2; a3 2 N with a1 +a2 +a3 6 n - 2, we show there exists a matching M of G with jM \\ Mij = ai for each i 2 f1; 2; 3g. The bound n - 2 in the theorem is best possible in general. We conjecture however that if G is bipartite, the same result holds with n - 2 replaced by n - 1. We give a construction that shows such a result would be tight. We\r\nalso make a conjecture generalising the Ryser-Brualdi-Stein conjecture with colour\r\nmultiplicities."}],"oa":1,"citation":{"apa":"Anastos, M., Fabian, D., Müyesser, A., &#38; Szabó, T. (2023). Splitting matchings and the Ryser-Brualdi-Stein conjecture for multisets. <i>Electronic Journal of Combinatorics</i>. Electronic Journal of Combinatorics. <a href=\"https://doi.org/10.37236/11714\">https://doi.org/10.37236/11714</a>","mla":"Anastos, Michael, et al. “Splitting Matchings and the Ryser-Brualdi-Stein Conjecture for Multisets.” <i>Electronic Journal of Combinatorics</i>, vol. 30, no. 3, P3.10, Electronic Journal of Combinatorics, 2023, doi:<a href=\"https://doi.org/10.37236/11714\">10.37236/11714</a>.","chicago":"Anastos, Michael, David Fabian, Alp Müyesser, and Tibor Szabó. “Splitting Matchings and the Ryser-Brualdi-Stein Conjecture for Multisets.” <i>Electronic Journal of Combinatorics</i>. Electronic Journal of Combinatorics, 2023. <a href=\"https://doi.org/10.37236/11714\">https://doi.org/10.37236/11714</a>.","ista":"Anastos M, Fabian D, Müyesser A, Szabó T. 2023. Splitting matchings and the Ryser-Brualdi-Stein conjecture for multisets. Electronic Journal of Combinatorics. 30(3), P3.10.","ieee":"M. Anastos, D. Fabian, A. Müyesser, and T. Szabó, “Splitting matchings and the Ryser-Brualdi-Stein conjecture for multisets,” <i>Electronic Journal of Combinatorics</i>, vol. 30, no. 3. Electronic Journal of Combinatorics, 2023.","ama":"Anastos M, Fabian D, Müyesser A, Szabó T. Splitting matchings and the Ryser-Brualdi-Stein conjecture for multisets. <i>Electronic Journal of Combinatorics</i>. 2023;30(3). doi:<a href=\"https://doi.org/10.37236/11714\">10.37236/11714</a>","short":"M. Anastos, D. Fabian, A. Müyesser, T. Szabó, Electronic Journal of Combinatorics 30 (2023)."},"date_updated":"2025-09-09T12:54:51Z","article_number":"P3.10","date_published":"2023-07-28T00:00:00Z","month":"07","issue":"3","title":"Splitting matchings and the Ryser-Brualdi-Stein conjecture for multisets","acknowledgement":"Anastos has received funding from the European Union’s Horizon 2020 research and in-novation programme under the Marie Sk lodowska-Curie grant agreement No 101034413.Fabian’s research is supported by the Deutsche Forschungsgemeinschaft (DFG, GermanResearch Foundation) Graduiertenkolleg “Facets of Complexity” (GRK 2434).","language":[{"iso":"eng"}],"publisher":"Electronic Journal of Combinatorics","type":"journal_article","tmp":{"short":"CC BY-ND (4.0)","image":"/image/cc_by_nd.png","name":"Creative Commons Attribution-NoDerivatives 4.0 International (CC BY-ND 4.0)","legal_code_url":"https://creativecommons.org/licenses/by-nd/4.0/legalcode"},"article_processing_charge":"Yes","doi":"10.37236/11714","publication_identifier":{"eissn":["1077-8926"]},"external_id":{"arxiv":["2212.03100"],"isi":["001042382200001"]},"date_created":"2023-09-10T22:01:12Z","status":"public","article_type":"original","intvolume":"        30","volume":30,"oa_version":"Published Version","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","has_accepted_license":"1","author":[{"last_name":"Anastos","first_name":"Michael","id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb","full_name":"Anastos, Michael"},{"first_name":"David","last_name":"Fabian","full_name":"Fabian, David"},{"first_name":"Alp","last_name":"Müyesser","full_name":"Müyesser, Alp"},{"full_name":"Szabó, Tibor","first_name":"Tibor","last_name":"Szabó"}],"file":[{"access_level":"open_access","content_type":"application/pdf","creator":"dernst","file_name":"2023_elecJournCombinatorics_Anastos.pdf","date_created":"2023-09-15T08:02:09Z","relation":"main_file","checksum":"52c46c8cb329f9aaee9ade01525f317b","file_size":247917,"success":1,"file_id":"14338","date_updated":"2023-09-15T08:02:09Z"}],"file_date_updated":"2023-09-15T08:02:09Z","ec_funded":1,"project":[{"_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","grant_number":"101034413","name":"IST-BRIDGE: International postdoctoral program","call_identifier":"H2020"}],"publication_status":"published","scopus_import":"1","department":[{"_id":"MaKw"}],"isi":1,"quality_controlled":"1","day":"28","arxiv":1,"ddc":["510"],"year":"2023","_id":"14319"},{"scopus_import":"1","department":[{"_id":"MaKw"}],"quality_controlled":"1","day":"01","arxiv":1,"year":"2023","_id":"14344","intvolume":"      2023","volume":2023,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Preprint","author":[{"first_name":"Michael","last_name":"Anastos","full_name":"Anastos, Michael","id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb"}],"publication_status":"published","doi":"10.1137/1.9781611977554.ch88","article_processing_charge":"No","publication_identifier":{"isbn":["9781611977554"]},"corr_author":"1","date_created":"2023-09-17T22:01:10Z","external_id":{"arxiv":["2111.14759"]},"status":"public","page":"2286-2323","publication":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2111.14759"}],"abstract":[{"text":"We study the Hamilton cycle problem with input a random graph G ~ G(n,p) in two different settings. In the first one, G is given to us in the form of randomly ordered adjacency lists while in the second one, we are given the adjacency matrix of G. In each of the two settings we derive a deterministic algorithm that w.h.p. either finds a Hamilton cycle or returns a certificate that such a cycle does not exist for p = p(n) ≥ 0. The running times of our algorithms are O(n) and  respectively, each being best possible in its own setting.","lang":"eng"}],"citation":{"chicago":"Anastos, Michael. “Fast Algorithms for Solving the Hamilton Cycle Problem with High Probability.” In <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>, 2023:2286–2323. Society for Industrial and Applied Mathematics, 2023. <a href=\"https://doi.org/10.1137/1.9781611977554.ch88\">https://doi.org/10.1137/1.9781611977554.ch88</a>.","ista":"Anastos M. 2023. Fast algorithms for solving the Hamilton cycle problem with high probability. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms vol. 2023, 2286–2323.","ieee":"M. Anastos, “Fast algorithms for solving the Hamilton cycle problem with high probability,” in <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Florence, Italy, 2023, vol. 2023, pp. 2286–2323.","ama":"Anastos M. Fast algorithms for solving the Hamilton cycle problem with high probability. In: <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>. Vol 2023. Society for Industrial and Applied Mathematics; 2023:2286-2323. doi:<a href=\"https://doi.org/10.1137/1.9781611977554.ch88\">10.1137/1.9781611977554.ch88</a>","short":"M. Anastos, in:, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2023, pp. 2286–2323.","apa":"Anastos, M. (2023). Fast algorithms for solving the Hamilton cycle problem with high probability. In <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i> (Vol. 2023, pp. 2286–2323). Florence, Italy: Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/1.9781611977554.ch88\">https://doi.org/10.1137/1.9781611977554.ch88</a>","mla":"Anastos, Michael. “Fast Algorithms for Solving the Hamilton Cycle Problem with High Probability.” <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>, vol. 2023, Society for Industrial and Applied Mathematics, 2023, pp. 2286–323, doi:<a href=\"https://doi.org/10.1137/1.9781611977554.ch88\">10.1137/1.9781611977554.ch88</a>."},"oa":1,"date_updated":"2024-10-09T21:07:01Z","date_published":"2023-01-01T00:00:00Z","conference":{"end_date":"2023-01-25","name":"SODA: Symposium on Discrete Algorithms","start_date":"2023-01-22","location":"Florence, Italy"},"month":"01","title":"Fast algorithms for solving the Hamilton cycle problem with high probability","language":[{"iso":"eng"}],"publisher":"Society for Industrial and Applied Mathematics","type":"conference"},{"isi":1,"quality_controlled":"1","department":[{"_id":"MaKw"}],"ddc":["510"],"year":"2023","_id":"14867","day":"01","arxiv":1,"oa_version":"Published Version","has_accepted_license":"1","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","author":[{"last_name":"Anastos","first_name":"Michael","id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb","full_name":"Anastos, Michael"}],"file":[{"success":1,"file_id":"14881","date_updated":"2024-01-24T09:34:43Z","relation":"main_file","file_size":464230,"checksum":"fb1d9a1e7389d90ec0e5e76934373cf8","creator":"dernst","date_created":"2024-01-24T09:34:43Z","file_name":"2023_Eurocomb_Anastos.pdf","access_level":"open_access","content_type":"application/pdf"}],"project":[{"name":"IST-BRIDGE: International postdoctoral program","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","grant_number":"101034413","call_identifier":"H2020"}],"publication_status":"published","file_date_updated":"2024-01-24T09:34:43Z","ec_funded":1,"corr_author":"1","article_processing_charge":"No","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode","name":"Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)","image":"/images/cc_by_nc_nd.png","short":"CC BY-NC-ND (4.0)"},"doi":"10.5817/cz.muni.eurocomb23-005","publication_identifier":{"eissn":["2788-3116"]},"external_id":{"arxiv":["2209.09860"],"isi":["001448447300005"]},"date_created":"2024-01-22T12:20:15Z","status":"public","abstract":[{"text":"<jats:p>Starting with the empty graph on $[n]$, at each round, a set of $K=K(n)$ edges is presented chosen uniformly at random from the ones that have not been presented yet. We are then asked to choose at most one of the presented edges and add it to the current graph. Our goal is to construct a Hamiltonian graph with $(1+o(1))n$ edges within as few rounds as possible. We show that in this process, one can build a Hamiltonian graph of size $(1+o(1))n$ in $(1+o(1))(1+(\\log n)/2K) n$ rounds w.h.p. The case $K=1$ implies that w.h.p. one can build a Hamiltonian graph by choosing $(1+o(1))n$ edges in an online fashion as they appear along the first $(0.5+o(1))n\\log n$ rounds of the random graph process. This answers a question of Frieze, Krivelevich and Michaeli. Observe that the number of rounds is asymptotically optimal as the first $0.5n\\log n$ edges do not span a Hamilton cycle w.h.p. The case $K=\\Theta(\\log n)$ implies that the Hamiltonicity threshold of the corresponding Achlioptas process is at most $(1+o(1))(1+(\\log n)/2K) n$. This matches the $(1-o(1))(1+(\\log n)/2K) n$ lower bound due to Krivelevich, Lubetzky and Sudakov and resolves the problem of determining the Hamiltonicity threshold of the Achlioptas process with $K=\\Theta(\\log n)$. We also show that in the above process one can construct a graph $G$ that spans a matching of size $\\lfloor V(G)/2) \\rfloor$ and $(0.5+o(1))n$ edges within $(1+o(1))(0.5+(\\log n)/2K) n$ rounds w.h.p. Our proof relies on a robust Hamiltonicity property of the strong $4$-core of the binomial random graph which we use as a black-box. This property allows it to absorb paths covering vertices outside the strong $4$-core into a cycle.</jats:p>","lang":"eng"}],"oa":1,"citation":{"ieee":"M. Anastos, “Constructing Hamilton cycles and perfect matchings efficiently,” in <i>Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications</i>, Prague, Czech Republic, 2023, pp. 36–41.","short":"M. Anastos, in:, Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications, Masaryk University Press, 2023, pp. 36–41.","ama":"Anastos M. Constructing Hamilton cycles and perfect matchings efficiently. In: <i>Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications</i>. Masaryk University Press; 2023:36-41. doi:<a href=\"https://doi.org/10.5817/cz.muni.eurocomb23-005\">10.5817/cz.muni.eurocomb23-005</a>","chicago":"Anastos, Michael. “Constructing Hamilton Cycles and Perfect Matchings Efficiently.” In <i>Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications</i>, 36–41. Masaryk University Press, 2023. <a href=\"https://doi.org/10.5817/cz.muni.eurocomb23-005\">https://doi.org/10.5817/cz.muni.eurocomb23-005</a>.","ista":"Anastos M. 2023. Constructing Hamilton cycles and perfect matchings efficiently. Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications. EUROCOMB: European Conference on Combinatorics, Graph Theory and Applications, 36–41.","mla":"Anastos, Michael. “Constructing Hamilton Cycles and Perfect Matchings Efficiently.” <i>Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications</i>, Masaryk University Press, 2023, pp. 36–41, doi:<a href=\"https://doi.org/10.5817/cz.muni.eurocomb23-005\">10.5817/cz.muni.eurocomb23-005</a>.","apa":"Anastos, M. (2023). Constructing Hamilton cycles and perfect matchings efficiently. In <i>Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications</i> (pp. 36–41). Prague, Czech Republic: Masaryk University Press. <a href=\"https://doi.org/10.5817/cz.muni.eurocomb23-005\">https://doi.org/10.5817/cz.muni.eurocomb23-005</a>"},"date_updated":"2025-09-09T14:24:21Z","month":"09","date_published":"2023-09-01T00:00:00Z","conference":{"location":"Prague, Czech Republic","start_date":"2023-08-28","end_date":"2023-09-01","name":"EUROCOMB: European Conference on Combinatorics, Graph Theory and Applications"},"page":"36-41","publication":"Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications","publisher":"Masaryk University Press","type":"conference","title":"Constructing Hamilton cycles and perfect matchings efficiently","language":[{"iso":"eng"}],"acknowledgement":"This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 101034413.\r\n"},{"publisher":"Institute of Electrical and Electronics Engineers","type":"conference","title":"Solving the Hamilton cycle problem fast on average","language":[{"iso":"eng"}],"acknowledgement":"This project has received funding from the European Union’s Horizon 2020\r\nresearch and innovation programme under the Marie Skłodowska-Curie grant\r\nagreement No 101034413","citation":{"ista":"Anastos M. 2022. Solving the Hamilton cycle problem fast on average. 63rd Annual IEEE Symposium on Foundations of Computer Science. FOCS: Foundations of Computer Science vol. 2022–October, 919–930.","chicago":"Anastos, Michael. “Solving the Hamilton Cycle Problem Fast on Average.” In <i>63rd Annual IEEE Symposium on Foundations of Computer Science</i>, 2022–October:919–30. Institute of Electrical and Electronics Engineers, 2022. <a href=\"https://doi.org/10.1109/FOCS54457.2022.00091\">https://doi.org/10.1109/FOCS54457.2022.00091</a>.","ama":"Anastos M. Solving the Hamilton cycle problem fast on average. In: <i>63rd Annual IEEE Symposium on Foundations of Computer Science</i>. Vol 2022-October. Institute of Electrical and Electronics Engineers; 2022:919-930. doi:<a href=\"https://doi.org/10.1109/FOCS54457.2022.00091\">10.1109/FOCS54457.2022.00091</a>","short":"M. Anastos, in:, 63rd Annual IEEE Symposium on Foundations of Computer Science, Institute of Electrical and Electronics Engineers, 2022, pp. 919–930.","ieee":"M. Anastos, “Solving the Hamilton cycle problem fast on average,” in <i>63rd Annual IEEE Symposium on Foundations of Computer Science</i>, Denver, CO, United States, 2022, vol. 2022–October, pp. 919–930.","apa":"Anastos, M. (2022). Solving the Hamilton cycle problem fast on average. In <i>63rd Annual IEEE Symposium on Foundations of Computer Science</i> (Vol. 2022–October, pp. 919–930). Denver, CO, United States: Institute of Electrical and Electronics Engineers. <a href=\"https://doi.org/10.1109/FOCS54457.2022.00091\">https://doi.org/10.1109/FOCS54457.2022.00091</a>","mla":"Anastos, Michael. “Solving the Hamilton Cycle Problem Fast on Average.” <i>63rd Annual IEEE Symposium on Foundations of Computer Science</i>, vol. 2022–October, Institute of Electrical and Electronics Engineers, 2022, pp. 919–30, doi:<a href=\"https://doi.org/10.1109/FOCS54457.2022.00091\">10.1109/FOCS54457.2022.00091</a>."},"abstract":[{"text":"We present CertifyHAM, a deterministic algorithm that takes a graph G as input and either finds a Hamilton cycle of G or outputs that such a cycle does not exist. If G ∼ G(n, p) and p ≥\r\n100 log n/n then the expected running time of CertifyHAM is O(n/p) which is best possible. This improves upon previous results due to Gurevich and Shelah, Thomason and Alon, and\r\nKrivelevich, who proved analogous results for p being constant, p ≥ 12n −1/3 and p ≥ 70n\r\n−1/2 respectively.","lang":"eng"}],"conference":{"end_date":"2022-11-03","name":"FOCS: Foundations of Computer Science","location":"Denver, CO, United States","start_date":"2022-10-31"},"month":"12","date_published":"2022-12-01T00:00:00Z","date_updated":"2025-07-10T11:50:26Z","publication":"63rd Annual IEEE Symposium on Foundations of Computer Science","page":"919-930","status":"public","date_created":"2023-01-29T23:00:59Z","external_id":{"isi":["000909382900084"]},"corr_author":"1","doi":"10.1109/FOCS54457.2022.00091","article_processing_charge":"No","publication_identifier":{"issn":["0272-5428"],"isbn":["9781665455190"]},"publication_status":"published","project":[{"name":"IST-BRIDGE: International postdoctoral program","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","grant_number":"101034413","call_identifier":"H2020"}],"ec_funded":1,"oa_version":"None","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"full_name":"Anastos, Michael","id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb","first_name":"Michael","last_name":"Anastos"}],"volume":"2022-October","year":"2022","_id":"12432","day":"01","isi":1,"quality_controlled":"1","scopus_import":"1","department":[{"_id":"MaKw"}]}]