[{"oa_version":"Published Version","year":"2026","_id":"20422","title":"The Hamilton space of pseudorandom graphs","article_processing_charge":"Yes (via OA deal)","month":"01","status":"public","date_published":"2026-01-01T00:00:00Z","scopus_import":"1","abstract":[{"lang":"eng","text":"We show that if n is odd and p>=Clog n/n, then with high probability Hamilton cycles in G(n,p) span its cycle space. More generally, we show this holds for a class of graphs satisfying certain natural pseudorandom properties. The proof is based on a novel idea of parity-switchers, which can be thought of as analogues of absorbers in the context of cycle spaces. As another application of our method, we show that Hamilton cycles in a near-Dirac graph G, that is, a graph G with odd n vertices and minimum degree n/2+C for sufficiently large constant C, span its cycle space.\r\n"}],"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. Image 1 Part of this research was conducted while the author was at Department of Computer Science, ETH Zürich, Switzerland. This author was supported by grant no. CRSII5 173721 of the Swiss National Science Foundation.","arxiv":1,"ddc":["510"],"OA_type":"hybrid","author":[{"last_name":"Christoph","first_name":"Micha","full_name":"Christoph, Micha"},{"last_name":"Nenadov","first_name":"Rajko","full_name":"Nenadov, Rajko"},{"last_name":"Petrova","id":"554ff4e4-f325-11ee-b0c4-a10dbd523381","full_name":"Petrova, Kalina H","first_name":"Kalina H"}],"project":[{"name":"IST-BRIDGE: International postdoctoral program","call_identifier":"H2020","grant_number":"101034413","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c"}],"publication_status":"published","article_type":"original","oa":1,"file":[{"success":1,"checksum":"60676af4af4b3243ba187e7d65440d99","file_name":"2026_JourCombTheoryB_Christoph.pdf","date_updated":"2026-01-05T13:29:34Z","content_type":"application/pdf","creator":"dernst","date_created":"2026-01-05T13:29:34Z","access_level":"open_access","file_id":"20953","file_size":688924,"relation":"main_file"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","isi":1,"volume":176,"citation":{"ama":"Christoph M, Nenadov R, Petrova KH. The Hamilton space of pseudorandom graphs. <i>Journal of Combinatorial Theory Series B</i>. 2026;176:254-267. doi:<a href=\"https://doi.org/10.1016/j.jctb.2025.09.002\">10.1016/j.jctb.2025.09.002</a>","chicago":"Christoph, Micha, Rajko Nenadov, and Kalina H Petrova. “The Hamilton Space of Pseudorandom Graphs.” <i>Journal of Combinatorial Theory Series B</i>. Elsevier, 2026. <a href=\"https://doi.org/10.1016/j.jctb.2025.09.002\">https://doi.org/10.1016/j.jctb.2025.09.002</a>.","short":"M. Christoph, R. Nenadov, K.H. Petrova, Journal of Combinatorial Theory Series B 176 (2026) 254–267.","ieee":"M. Christoph, R. Nenadov, and K. H. Petrova, “The Hamilton space of pseudorandom graphs,” <i>Journal of Combinatorial Theory Series B</i>, vol. 176. Elsevier, pp. 254–267, 2026.","ista":"Christoph M, Nenadov R, Petrova KH. 2026. The Hamilton space of pseudorandom graphs. Journal of Combinatorial Theory Series B. 176, 254–267.","apa":"Christoph, M., Nenadov, R., &#38; Petrova, K. H. (2026). The Hamilton space of pseudorandom graphs. <i>Journal of Combinatorial Theory Series B</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.jctb.2025.09.002\">https://doi.org/10.1016/j.jctb.2025.09.002</a>","mla":"Christoph, Micha, et al. “The Hamilton Space of Pseudorandom Graphs.” <i>Journal of Combinatorial Theory Series B</i>, vol. 176, Elsevier, 2026, pp. 254–67, doi:<a href=\"https://doi.org/10.1016/j.jctb.2025.09.002\">10.1016/j.jctb.2025.09.002</a>."},"type":"journal_article","ec_funded":1,"page":"254-267","doi":"10.1016/j.jctb.2025.09.002","day":"01","publisher":"Elsevier","publication":"Journal of Combinatorial Theory Series B","publication_identifier":{"issn":["0095-8956"],"eissn":["1096-0902"]},"intvolume":"       176","quality_controlled":"1","language":[{"iso":"eng"}],"external_id":{"isi":["001585783400001"],"arxiv":["2402.01447"]},"corr_author":"1","date_updated":"2026-01-05T13:29:52Z","OA_place":"publisher","has_accepted_license":"1","PlanS_conform":"1","department":[{"_id":"MaKw"}],"file_date_updated":"2026-01-05T13:29:34Z","date_created":"2025-10-05T22:01:34Z","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"}},{"publication_identifier":{"issn":["0195-6698"]},"intvolume":"       131","language":[{"iso":"eng"}],"quality_controlled":"1","external_id":{"arxiv":["2410.05887"],"isi":["001573380700001"]},"corr_author":"1","date_updated":"2026-01-05T13:34:48Z","OA_place":"publisher","has_accepted_license":"1","article_number":"104235","PlanS_conform":"1","department":[{"_id":"MaKw"}],"file_date_updated":"2026-01-05T13:34:40Z","date_created":"2025-10-16T13:14:34Z","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"volume":131,"citation":{"chicago":"Boyadzhiyska, Simona, Shagnik Das, Thomas Lesgourgues, and Kalina H Petrova. “Odd-Ramsey Numbers of Complete Bipartite Graphs.” <i>European Journal of Combinatorics</i>. Elsevier, 2026. <a href=\"https://doi.org/10.1016/j.ejc.2025.104235\">https://doi.org/10.1016/j.ejc.2025.104235</a>.","ama":"Boyadzhiyska S, Das S, Lesgourgues T, Petrova KH. Odd-Ramsey numbers of complete bipartite graphs. <i>European Journal of Combinatorics</i>. 2026;131. doi:<a href=\"https://doi.org/10.1016/j.ejc.2025.104235\">10.1016/j.ejc.2025.104235</a>","ieee":"S. Boyadzhiyska, S. Das, T. Lesgourgues, and K. H. Petrova, “Odd-Ramsey numbers of complete bipartite graphs,” <i>European Journal of Combinatorics</i>, vol. 131. Elsevier, 2026.","mla":"Boyadzhiyska, Simona, et al. “Odd-Ramsey Numbers of Complete Bipartite Graphs.” <i>European Journal of Combinatorics</i>, vol. 131, 104235, Elsevier, 2026, doi:<a href=\"https://doi.org/10.1016/j.ejc.2025.104235\">10.1016/j.ejc.2025.104235</a>.","ista":"Boyadzhiyska S, Das S, Lesgourgues T, Petrova KH. 2026. Odd-Ramsey numbers of complete bipartite graphs. European Journal of Combinatorics. 131, 104235.","apa":"Boyadzhiyska, S., Das, S., Lesgourgues, T., &#38; Petrova, K. H. (2026). Odd-Ramsey numbers of complete bipartite graphs. <i>European Journal of Combinatorics</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.ejc.2025.104235\">https://doi.org/10.1016/j.ejc.2025.104235</a>","short":"S. Boyadzhiyska, S. Das, T. Lesgourgues, K.H. Petrova, European Journal of Combinatorics 131 (2026)."},"ec_funded":1,"type":"journal_article","day":"01","doi":"10.1016/j.ejc.2025.104235","publisher":"Elsevier","publication":"European Journal of Combinatorics","status":"public","abstract":[{"lang":"eng","text":"In his study of graph codes, Alon introduced the concept of the odd-Ramsey number of a family of graphs H in Kn, defined as the minimum number of colours needed to colour the edges of K so that every copy of a graph H E H intersects some colour class in an odd number of edges. In this paper, we focus on complete bipartite graphs. First, we completely resolve the problem when H is the family of all spanning complete bipartite graphs on n vertices. We then focus on its subfamilies, that is, {Kt,n-t : t E T} for a fixed set of integers T c [[n/2]]. We prove that the odd-Ramsey problem is equivalent to determining the maximum dimension of a linear binary code avoiding codewords of given weights, and leverage known results from coding theory to deduce asymptotically tight bounds in our setting. We conclude with bounds for the odd-Ramsey numbers of fixed (that is, non-spanning) complete bipartite subgraphs."}],"scopus_import":"1","date_published":"2026-01-01T00:00:00Z","acknowledgement":"The authors would like to thank Gilles Zémor for a helpful clarification on [3], Deepak Bal and Patrick Bennett for bringing [25] to their attention, and both referees for several helpful comments.\r\nS.B.: Most of this research was conducted while the author was at the School of Mathematics, University of Birmingham, Birmingham, United Kingdom. The research leading to these results was supported by EPSRC, United Kingdom, grant no. EP/V048287/1 and by ERC Advanced Grants “GeoScape”, no. 882971 and “ERMiD”, no. 101054936. There are no additional data beyond that contained within the main manuscript.\r\nS.D.: Research supported by Taiwan NSTC grants 111-2115-M-002-009-MY2 and 113-2628-M-002-008-MY4.\r\nK.P.: 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. Parts of this research was conducted while K.P. was at the Department of Computer Science, ETH Zürich, Switzerland, supported by Swiss National Science Foundation, Switzerland , grant no. CRSII5 173721.","arxiv":1,"ddc":["500"],"OA_type":"hybrid","author":[{"first_name":"Simona","full_name":"Boyadzhiyska, Simona","last_name":"Boyadzhiyska"},{"first_name":"Shagnik","full_name":"Das, Shagnik","last_name":"Das"},{"last_name":"Lesgourgues","full_name":"Lesgourgues, Thomas","first_name":"Thomas"},{"last_name":"Petrova","first_name":"Kalina H","id":"554ff4e4-f325-11ee-b0c4-a10dbd523381","full_name":"Petrova, Kalina H"}],"project":[{"_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","grant_number":"101034413","name":"IST-BRIDGE: International postdoctoral program","call_identifier":"H2020"}],"article_type":"original","publication_status":"published","oa":1,"file":[{"file_id":"20954","relation":"main_file","file_size":563029,"content_type":"application/pdf","creator":"dernst","date_created":"2026-01-05T13:34:40Z","access_level":"open_access","file_name":"2026_EuropJourCombinatorics_Boyadzhiyska.pdf","date_updated":"2026-01-05T13:34:40Z","success":1,"checksum":"52883daa217398396cbf9b8ad9ddae92"}],"isi":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Published Version","year":"2026","_id":"20482","title":"Odd-Ramsey numbers of complete bipartite graphs","article_processing_charge":"Yes (via OA deal)","month":"01"},{"oa_version":"Published Version","year":"2026","_id":"21159","title":"Counting perfect matchings in Dirac hypergraphs","article_processing_charge":"Yes (via OA deal)","month":"02","status":"public","date_published":"2026-02-01T00:00:00Z","scopus_import":"1","abstract":[{"text":"One of the foundational theorems of extremal graph theory is Dirac’s theorem, which\r\nsays that if an n-vertex graph G has minimum degree at least n/2, then G has a\r\nHamilton cycle, and therefore a perfect matching (if n is even). Later work by Sárközy,\r\nSelkow and Szemerédi showed that in fact Dirac graphs have many Hamilton cycles\r\nand perfect matchings, culminating in a result of Cuckler and Kahn that gives a precise\r\ndescription of the numbers of Hamilton cycles and perfect matchings in a Dirac graph\r\nG (in terms of an entropy-like parameter of G). In this paper we extend Cuckler\r\nand Kahn’s result to perfect matchings in hypergraphs. For positive integers d < k,\r\nand for n divisible by k, let md (k, n) be the minimum d-degree that ensures the\r\nexistence of a perfect matching in an n-vertex k-uniform hypergraph. In general, it is\r\nan open question to determine (even asymptotically) the values of md (k, n), but we are\r\nnonetheless able to prove an analogue of the Cuckler–Kahn theorem, showing that if\r\nan n-vertex k-uniform hypergraph G has minimum d-degree at least (1+γ )md (k, n)\r\n(for any constantγ > 0), then the number of perfect matchings in G is controlled by\r\nan entropy-like parameter of G. This strengthens cruder estimates arising from work\r\nof Kang–Kelly–Kühn–Osthus–Pfenninger and Pham–Sah–Sawhney–Simkin.","lang":"eng"}],"acknowledgement":"We would like to thank the referees for a number of helpful comments and suggestions, which have substantially improved the paper. Open access funding provided by Institute of Science and Technology (IST Austria).","ddc":["510"],"arxiv":1,"OA_type":"hybrid","author":[{"id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","full_name":"Kwan, Matthew Alan","first_name":"Matthew Alan","orcid":"0000-0002-4003-7567","last_name":"Kwan"},{"last_name":"Safavi Hemami","full_name":"Safavi Hemami, Roodabeh","id":"72ed2640-8972-11ed-ae7b-f9c81ec75154","first_name":"Roodabeh"},{"orcid":"0000-0002-2856-767X","last_name":"Wang","id":"1917d194-076e-11ed-97cd-837255f88785","full_name":"Wang, Yiting","first_name":"Yiting"}],"publication_status":"published","article_type":"original","oa":1,"file":[{"file_name":"2026_Combinatorica_Kwan.pdf","date_updated":"2026-02-16T09:52:38Z","success":1,"checksum":"47b0031d90b0e6b9a843f422a1486089","file_id":"21228","file_size":539646,"relation":"main_file","content_type":"application/pdf","creator":"dernst","date_created":"2026-02-16T09:52:38Z","access_level":"open_access"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","volume":46,"citation":{"ama":"Kwan MA, Safavi Hemami R, Wang Y. Counting perfect matchings in Dirac hypergraphs. <i>Combinatorica</i>. 2026;46. doi:<a href=\"https://doi.org/10.1007/s00493-025-00194-8\">10.1007/s00493-025-00194-8</a>","chicago":"Kwan, Matthew Alan, Roodabeh Safavi Hemami, and Yiting Wang. “Counting Perfect Matchings in Dirac Hypergraphs.” <i>Combinatorica</i>. Springer Nature, 2026. <a href=\"https://doi.org/10.1007/s00493-025-00194-8\">https://doi.org/10.1007/s00493-025-00194-8</a>.","short":"M.A. Kwan, R. Safavi Hemami, Y. Wang, Combinatorica 46 (2026).","ista":"Kwan MA, Safavi Hemami R, Wang Y. 2026. Counting perfect matchings in Dirac hypergraphs. Combinatorica. 46, 5.","mla":"Kwan, Matthew Alan, et al. “Counting Perfect Matchings in Dirac Hypergraphs.” <i>Combinatorica</i>, vol. 46, 5, Springer Nature, 2026, doi:<a href=\"https://doi.org/10.1007/s00493-025-00194-8\">10.1007/s00493-025-00194-8</a>.","apa":"Kwan, M. A., Safavi Hemami, R., &#38; Wang, Y. (2026). Counting perfect matchings in Dirac hypergraphs. <i>Combinatorica</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00493-025-00194-8\">https://doi.org/10.1007/s00493-025-00194-8</a>","ieee":"M. A. Kwan, R. Safavi Hemami, and Y. Wang, “Counting perfect matchings in Dirac hypergraphs,” <i>Combinatorica</i>, vol. 46. Springer Nature, 2026."},"type":"journal_article","doi":"10.1007/s00493-025-00194-8","day":"01","publisher":"Springer Nature","publication":"Combinatorica","publication_identifier":{"issn":["0209-9683"],"eissn":["1439-6912"]},"intvolume":"        46","quality_controlled":"1","language":[{"iso":"eng"}],"external_id":{"arxiv":["2408.09589"]},"corr_author":"1","date_updated":"2026-02-16T09:55:17Z","OA_place":"publisher","has_accepted_license":"1","article_number":"5","PlanS_conform":"1","department":[{"_id":"MaKw"},{"_id":"MoHe"}],"date_created":"2026-02-08T23:02:49Z","file_date_updated":"2026-02-16T09:52:38Z","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"}},{"type":"journal_article","page":"52-65","doi":"10.1007/s00283-024-10358-x","publisher":"Springer Nature","day":"01","volume":47,"citation":{"short":"F.R. Brunck, M.A. Kwan, Mathematical Intelligencer 47 (2025) 52–65.","ieee":"F. R. Brunck and M. A. Kwan, “Books, Hallways, and social butterflies: A note on sliding block puzzles,” <i>Mathematical Intelligencer</i>, vol. 47. Springer Nature, pp. 52–65, 2025.","apa":"Brunck, F. R., &#38; Kwan, M. A. (2025). Books, Hallways, and social butterflies: A note on sliding block puzzles. <i>Mathematical Intelligencer</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00283-024-10358-x\">https://doi.org/10.1007/s00283-024-10358-x</a>","ista":"Brunck FR, Kwan MA. 2025. Books, Hallways, and social butterflies: A note on sliding block puzzles. Mathematical Intelligencer. 47, 52–65.","mla":"Brunck, Florestan R., and Matthew Alan Kwan. “Books, Hallways, and Social Butterflies: A Note on Sliding Block Puzzles.” <i>Mathematical Intelligencer</i>, vol. 47, Springer Nature, 2025, pp. 52–65, doi:<a href=\"https://doi.org/10.1007/s00283-024-10358-x\">10.1007/s00283-024-10358-x</a>.","ama":"Brunck FR, Kwan MA. Books, Hallways, and social butterflies: A note on sliding block puzzles. <i>Mathematical Intelligencer</i>. 2025;47:52-65. doi:<a href=\"https://doi.org/10.1007/s00283-024-10358-x\">10.1007/s00283-024-10358-x</a>","chicago":"Brunck, Florestan R, and Matthew Alan Kwan. “Books, Hallways, and Social Butterflies: A Note on Sliding Block Puzzles.” <i>Mathematical Intelligencer</i>. Springer Nature, 2025. <a href=\"https://doi.org/10.1007/s00283-024-10358-x\">https://doi.org/10.1007/s00283-024-10358-x</a>."},"publication":"Mathematical Intelligencer","external_id":{"arxiv":["2303.09459"],"isi":["001318056000001"]},"date_updated":"2025-05-19T14:00:09Z","has_accepted_license":"1","OA_place":"publisher","publication_identifier":{"issn":["0343-6993"]},"intvolume":"        47","language":[{"iso":"eng"}],"quality_controlled":"1","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"department":[{"_id":"UlWa"},{"_id":"MaKw"}],"date_created":"2024-09-29T22:01:38Z","file_date_updated":"2025-04-08T11:17:45Z","title":"Books, Hallways, and social butterflies: A note on sliding block puzzles","oa_version":"Published Version","year":"2025","_id":"18157","month":"03","article_processing_charge":"Yes (via OA deal)","acknowledgement":"Open access funding provided by Copenhagen University.","arxiv":1,"ddc":["510"],"OA_type":"hybrid","status":"public","scopus_import":"1","abstract":[{"lang":"eng","text":"Interest in sliding block puzzles dates back to the 15-puzzle, seemingly invented by Noyes Chapman in 1874 (see [23] for an account of the fascinating history of the puzzle). The game consists of fifteen movable square blocks numbered \r\n and arranged within a \r\n square box, leaving one empty space (see Figure 1). The task at hand is to start from a given configuration of the numbered blocks and reach the desired target configuration, where the only allowed move is to slide a numbered block into an adjacent empty space. This task seemed to be unpredictably either very easy to accomplish, or completely impossible, and the puzzle turned into a worldwide sensation in the spring of 1880. A particularly challenging instance, known as the 13-15-14 puzzle, consisted of initial and target configurations that differed by a single swap (historically this swap involved the blocks labeled 14 and 15). The craze of this puzzle was such that it consistently made newspaper headlines in 1880, with an article in the New York Times lamenting that it was “threatening our free institutions” [23, p. 9]. Various prizes were offered for anyone who could solve this challenge, beginning with a $25 set of teeth and culminating with Sam Loyd’s famous $1,000 cash prize."}],"date_published":"2025-03-01T00:00:00Z","oa":1,"file":[{"access_level":"open_access","creator":"dernst","date_created":"2025-04-08T11:17:45Z","content_type":"application/pdf","file_size":1760643,"relation":"main_file","file_id":"19530","checksum":"c932ebe45c460d4a73f5b2dcca643db1","success":1,"date_updated":"2025-04-08T11:17:45Z","file_name":"2025_MathIntelligencer_Brunck.pdf"}],"isi":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"last_name":"Brunck","first_name":"Florestan R","full_name":"Brunck, Florestan R","id":"6ab6e556-f394-11eb-9cf6-9dfb78f00d8d"},{"orcid":"0000-0002-4003-7567","last_name":"Kwan","full_name":"Kwan, Matthew Alan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","first_name":"Matthew Alan"}],"publication_status":"published","article_type":"original"},{"month":"01","article_processing_charge":"Yes (in subscription journal)","title":"On the chromatic number of powers of subdivisions of graphs","oa_version":"Published Version","year":"2025","_id":"18478","oa":1,"file":[{"content_type":"application/pdf","creator":"dernst","date_created":"2025-01-13T09:25:59Z","access_level":"open_access","file_id":"18836","relation":"main_file","file_size":441060,"success":1,"checksum":"bd20a13e56b3ea01daf5e7aca5247c60","file_name":"2025_DiscreteApplMath_Anastos.pdf","date_updated":"2025-01-13T09:25:59Z"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","isi":1,"author":[{"id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb","full_name":"Anastos, Michael","first_name":"Michael","last_name":"Anastos"},{"first_name":"Simona","full_name":"Boyadzhiyska, Simona","last_name":"Boyadzhiyska"},{"last_name":"Rathke","first_name":"Silas","full_name":"Rathke, Silas"},{"full_name":"Rué, Juanjo","first_name":"Juanjo","last_name":"Rué"}],"project":[{"grant_number":"101034413","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","name":"IST-BRIDGE: International postdoctoral program","call_identifier":"H2020"}],"publication_status":"published","article_type":"original","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).","arxiv":1,"ddc":["510"],"OA_type":"hybrid","status":"public","date_published":"2025-01-15T00:00:00Z","abstract":[{"lang":"eng","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."}],"scopus_import":"1","publication":"Discrete Applied Mathematics","ec_funded":1,"type":"journal_article","page":"506-511","day":"15","doi":"10.1016/j.dam.2024.10.002","publisher":"Elsevier","volume":360,"citation":{"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>.","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>","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.","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>","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>.","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.","short":"M. Anastos, S. Boyadzhiyska, S. Rathke, J. Rué, Discrete Applied Mathematics 360 (2025) 506–511."},"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"department":[{"_id":"MaKw"}],"date_created":"2024-10-27T23:01:44Z","file_date_updated":"2025-01-13T09:25:59Z","external_id":{"arxiv":["2404.05542"],"isi":["001343647000001"]},"corr_author":"1","date_updated":"2025-04-14T07:54:56Z","has_accepted_license":"1","OA_place":"publisher","publication_identifier":{"issn":["0166-218X"]},"intvolume":"       360","quality_controlled":"1","language":[{"iso":"eng"}]},{"title":"A note on finding large transversals efficiently","oa_version":"Preprint","issue":"9","_id":"19798","year":"2025","month":"09","article_processing_charge":"No","arxiv":1,"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.","OA_type":"green","status":"public","scopus_import":"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."}],"date_published":"2025-09-01T00:00:00Z","oa":1,"isi":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"last_name":"Anastos","full_name":"Anastos, Michael","id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb","first_name":"Michael"},{"first_name":"Patrick","full_name":"Morris, Patrick","last_name":"Morris"}],"publication_status":"published","article_type":"original","project":[{"name":"Combinatorial Optimisation Problems on Sparse Random Graphs","_id":"8f906bd2-16d5-11f0-9cad-e07be8aa9ac9","grant_number":"ESP3863424"},{"name":"IST-BRIDGE: International postdoctoral program","call_identifier":"H2020","grant_number":"101034413","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c"}],"type":"journal_article","ec_funded":1,"doi":"10.1002/jcd.21990","day":"01","publisher":"Wiley","page":"338-342","volume":33,"citation":{"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>.","short":"M. Anastos, P. Morris, Journal of Combinatorial Designs 33 (2025) 338–342.","ista":"Anastos M, Morris P. 2025. A note on finding large transversals efficiently. Journal of Combinatorial Designs. 33(9), 338–342.","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>","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>.","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."},"main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2412.05891","open_access":"1"}],"publication":"Journal of Combinatorial Designs","external_id":{"arxiv":["2412.05891"],"isi":["001495472300001"]},"OA_place":"repository","date_updated":"2025-12-30T08:37:37Z","publication_identifier":{"issn":["1063-8539"],"eissn":["1520-6610"]},"quality_controlled":"1","language":[{"iso":"eng"}],"intvolume":"        33","department":[{"_id":"MaKw"}],"date_created":"2025-06-08T22:01:23Z"},{"intvolume":"         8","language":[{"iso":"eng"}],"quality_controlled":"1","publication_identifier":{"eissn":["2644-9463"]},"date_updated":"2025-06-23T12:01:36Z","has_accepted_license":"1","OA_place":"publisher","external_id":{"arxiv":["2211.16086 "]},"corr_author":"1","file_date_updated":"2025-06-23T11:59:22Z","date_created":"2025-06-22T22:02:07Z","department":[{"_id":"MaKw"}],"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"citation":{"ieee":"L. Lichev and B. Schapira, “Color-avoiding percolation on the Erdős–Rényi random graph,” <i>Annales Henri Lebesgue</i>, vol. 8. École normale supérieure de Rennes, pp. 35–65, 2025.","ista":"Lichev L, Schapira B. 2025. Color-avoiding percolation on the Erdős–Rényi random graph. Annales Henri Lebesgue. 8, 35–65.","apa":"Lichev, L., &#38; Schapira, B. (2025). Color-avoiding percolation on the Erdős–Rényi random graph. <i>Annales Henri Lebesgue</i>. École normale supérieure de Rennes. <a href=\"https://doi.org/10.5802/ahl.228\">https://doi.org/10.5802/ahl.228</a>","mla":"Lichev, Lyuben, and Bruno Schapira. “Color-Avoiding Percolation on the Erdős–Rényi Random Graph.” <i>Annales Henri Lebesgue</i>, vol. 8, École normale supérieure de Rennes, 2025, pp. 35–65, doi:<a href=\"https://doi.org/10.5802/ahl.228\">10.5802/ahl.228</a>.","short":"L. Lichev, B. Schapira, Annales Henri Lebesgue 8 (2025) 35–65.","chicago":"Lichev, Lyuben, and Bruno Schapira. “Color-Avoiding Percolation on the Erdős–Rényi Random Graph.” <i>Annales Henri Lebesgue</i>. École normale supérieure de Rennes, 2025. <a href=\"https://doi.org/10.5802/ahl.228\">https://doi.org/10.5802/ahl.228</a>.","ama":"Lichev L, Schapira B. Color-avoiding percolation on the Erdős–Rényi random graph. <i>Annales Henri Lebesgue</i>. 2025;8:35-65. doi:<a href=\"https://doi.org/10.5802/ahl.228\">10.5802/ahl.228</a>"},"DOAJ_listed":"1","volume":8,"page":"35-65","day":"01","doi":"10.5802/ahl.228","publisher":"École normale supérieure de Rennes","type":"journal_article","publication":"Annales Henri Lebesgue","abstract":[{"text":"We consider a recently introduced model of color-avoiding percolation (abbreviated CA-percolation) defined as follows. Every edge in a graph G is colored in some of k>=2 colors. Two vertices u and v in G are said to be CA-connected if u and v may be connected using any subset of k-1 colors. CA-connectivity defines an equivalence relation on the vertex set of G whose classes are called CA-components.\r\nWe study the component structure of a randomly colored Erdős–Rényi random graph of constant average degree. We distinguish three regimes for the size of the largest component: a supercritical regime, a so-called intermediate regime, and a subcritical regime, in which the largest CA-component has respectively linear, logarithmic, and bounded size. Interestingly, in the subcritical regime, the bound is deterministic and given by the number of colors.","lang":"eng"}],"date_published":"2025-06-01T00:00:00Z","scopus_import":"1","status":"public","OA_type":"gold","acknowledgement":"We thank Dieter Mitsche for enlightening discussions, Balázs Ráth for a number of comments\r\nand corrections on a first version of this paper, and an anonymous referee for several useful remarks.","arxiv":1,"ddc":["510"],"article_type":"original","publication_status":"published","author":[{"first_name":"Lyuben","id":"9aa8388e-d003-11ee-8458-c4c1d7447977","full_name":"Lichev, Lyuben","last_name":"Lichev"},{"last_name":"Schapira","full_name":"Schapira, Bruno","first_name":"Bruno"}],"file":[{"content_type":"application/pdf","creator":"dernst","date_created":"2025-06-23T11:59:22Z","access_level":"open_access","file_id":"19875","relation":"main_file","file_size":746588,"success":1,"checksum":"cca22d171b7affa010d17f5e793b0045","file_name":"2025_AnnalesHenriLebesgue_Lichev.pdf","date_updated":"2025-06-23T11:59:22Z"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"year":"2025","_id":"19859","oa_version":"Published Version","title":"Color-avoiding percolation on the Erdős–Rényi random graph","article_processing_charge":"Yes","month":"06"},{"publication":"European Journal of Combinatorics","day":"01","doi":"10.1016/j.ejc.2025.104138","publisher":"Elsevier","type":"journal_article","citation":{"chicago":"Dvořák, Zdeněk, Benjamin Moore, Michaela Seifrtová, and Robert Šámal. “Precoloring Extension in Planar Near-Eulerian-Triangulations.” <i>European Journal of Combinatorics</i>. Elsevier, 2025. <a href=\"https://doi.org/10.1016/j.ejc.2025.104138\">https://doi.org/10.1016/j.ejc.2025.104138</a>.","ama":"Dvořák Z, Moore B, Seifrtová M, Šámal R. Precoloring extension in planar near-Eulerian-triangulations. <i>European Journal of Combinatorics</i>. 2025;127. doi:<a href=\"https://doi.org/10.1016/j.ejc.2025.104138\">10.1016/j.ejc.2025.104138</a>","ista":"Dvořák Z, Moore B, Seifrtová M, Šámal R. 2025. Precoloring extension in planar near-Eulerian-triangulations. European Journal of Combinatorics. 127, 104138.","mla":"Dvořák, Zdeněk, et al. “Precoloring Extension in Planar Near-Eulerian-Triangulations.” <i>European Journal of Combinatorics</i>, vol. 127, 104138, Elsevier, 2025, doi:<a href=\"https://doi.org/10.1016/j.ejc.2025.104138\">10.1016/j.ejc.2025.104138</a>.","apa":"Dvořák, Z., Moore, B., Seifrtová, M., &#38; Šámal, R. (2025). Precoloring extension in planar near-Eulerian-triangulations. <i>European Journal of Combinatorics</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.ejc.2025.104138\">https://doi.org/10.1016/j.ejc.2025.104138</a>","ieee":"Z. Dvořák, B. Moore, M. Seifrtová, and R. Šámal, “Precoloring extension in planar near-Eulerian-triangulations,” <i>European Journal of Combinatorics</i>, vol. 127. Elsevier, 2025.","short":"Z. Dvořák, B. Moore, M. Seifrtová, R. Šámal, European Journal of Combinatorics 127 (2025)."},"volume":127,"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"date_created":"2025-06-23T13:54:46Z","file_date_updated":"2025-06-24T06:33:30Z","article_number":"104138","department":[{"_id":"MaKw"}],"date_updated":"2025-09-30T13:42:59Z","OA_place":"publisher","has_accepted_license":"1","external_id":{"arxiv":["2312.13061"],"isi":["001443061400001"]},"corr_author":"1","intvolume":"       127","quality_controlled":"1","language":[{"iso":"eng"}],"publication_identifier":{"issn":["0195-6698"]},"month":"06","article_processing_charge":"Yes (via OA deal)","title":"Precoloring extension in planar near-Eulerian-triangulations","year":"2025","_id":"19879","oa_version":"Published Version","file":[{"file_name":"2025_EuropJournCombinatorics_Dvorak.pdf","date_updated":"2025-06-24T06:33:30Z","checksum":"8b3585df45b25091fba9bee9854b7d01","success":1,"relation":"main_file","file_size":564203,"file_id":"19887","date_created":"2025-06-24T06:33:30Z","creator":"dernst","access_level":"open_access","content_type":"application/pdf"}],"isi":1,"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","oa":1,"article_type":"original","publication_status":"published","author":[{"last_name":"Dvořák","full_name":"Dvořák, Zdeněk","first_name":"Zdeněk"},{"last_name":"Moore","first_name":"Benjamin","id":"6dc1a1be-bf1c-11ed-8d2b-d044840f49d6","full_name":"Moore, Benjamin"},{"first_name":"Michaela","full_name":"Seifrtová, Michaela","last_name":"Seifrtová"},{"last_name":"Šámal","first_name":"Robert","full_name":"Šámal, Robert"}],"OA_type":"hybrid","acknowledgement":"Supported by project 22-17398S (Flows and cycles in graphs on surfaces) of Czech Science Foundation. An extended abstract appeared in Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB’23)","arxiv":1,"ddc":["510"],"date_published":"2025-06-01T00:00:00Z","abstract":[{"lang":"eng","text":"We consider the 4-precoloring extension problem in planar near-Eulerian- triangulations, i.e., plane graphs where all faces except possibly for the outer one have length three, all vertices not incident with the outer face have even degree, and exactly the vertices incident with the outer face are precolored. We give a necessary topological condition for the precoloring to extend, and give a complete characterization when the outer face has length at most five and when all vertices of the outer face have odd degree and are colored using only three colors."}],"scopus_import":"1","status":"public"},{"title":"Smoothed analysis for graph isomorphism","year":"2025","_id":"20007","oa_version":"Published Version","month":"06","article_processing_charge":"Yes (via OA deal)","OA_type":"hybrid","conference":{"start_date":"2025-06-23","name":"STOC: Symposium on Theory of Computing","end_date":"2025-06-27","location":"Prague, Czechia"},"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.","ddc":["000"],"arxiv":1,"date_published":"2025-06-15T00:00:00Z","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."}],"scopus_import":"1","status":"public","file":[{"success":1,"checksum":"cf0ab9cb9c6abda188de13dc3f9a4c9b","date_updated":"2025-07-14T06:13:10Z","file_name":"2025_STOC_Anastos.pdf","content_type":"application/pdf","access_level":"open_access","date_created":"2025-07-14T06:13:10Z","creator":"dernst","file_id":"20012","file_size":706445,"relation":"main_file"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"project":[{"name":"Randomness and structure in combinatorics","_id":"bd95085b-d553-11ed-ba76-e55d3349be45","grant_number":"101076777"},{"call_identifier":"H2020","name":"IST-BRIDGE: International postdoctoral program","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","grant_number":"101034413"},{"name":"Combinatorial Optimisation Problems on Sparse Random Graphs","_id":"8f906bd2-16d5-11f0-9cad-e07be8aa9ac9","grant_number":"ESP3863424"}],"publication_status":"published","author":[{"last_name":"Anastos","first_name":"Michael","id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb","full_name":"Anastos, Michael"},{"first_name":"Matthew Alan","full_name":"Kwan, Matthew Alan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","last_name":"Kwan","orcid":"0000-0002-4003-7567"},{"id":"6dc1a1be-bf1c-11ed-8d2b-d044840f49d6","full_name":"Moore, Benjamin","first_name":"Benjamin","last_name":"Moore"}],"page":"2098-2106","day":"15","publisher":"Association for Computing Machinery","doi":"10.1145/3717823.3718173","ec_funded":1,"type":"conference","citation":{"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.","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>.","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.","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>.","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>"},"publication":"Proceedings of the 57th Annual ACM Symposium on Theory of Computing","date_updated":"2025-07-14T06:33:50Z","has_accepted_license":"1","OA_place":"publisher","external_id":{"arxiv":["2410.06095"]},"corr_author":"1","quality_controlled":"1","language":[{"iso":"eng"}],"publication_identifier":{"issn":["0737-8017"],"isbn":["9798400715105"]},"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"date_created":"2025-07-13T22:01:23Z","file_date_updated":"2025-07-14T06:13:10Z","department":[{"_id":"MaKw"}]},{"OA_type":"hybrid","acknowledgement":"This work was completed while Benjamin Moore was a postdoc at Charles University, supported by project 22-17398S (Flows and cycles in graphs on surfaces) of Czech Science Foundation, Czechia.","arxiv":1,"ddc":["500"],"date_published":"2025-12-01T00:00:00Z","scopus_import":"1","abstract":[{"text":"The pseudoforest version of the Strong Nine Dragon Tree Conjecture states that if a graph G has maximum average degree mad(G) = 2 maxH⊆G e(H)/v(H) at most 2(k + d/d+k+1), then it has a decomposition into k + 1 pseudoforests where in one pseudoforest F the components of F have at most d edges. This was proven in 2020 in Grout and Moore (2020). We strengthen this\r\ntheorem by showing that we can find such a decomposition where additionally F is acyclic, the diameter of the components of F is at most 2ℓ + 2, where ℓ =⌊d−1/k+1⌋, and at most 2ℓ + 1 if\r\nd ≡ 1 mod (k + 1). Furthermore, for any component K of F and any z ∈ N, we have diam(K) ≤ 2z if e(K) ≥ d − z(k − 1) + 1. We also show that both diameter bounds are best possible as an\r\nextension for both the Strong Nine Dragon Tree Conjecture for pseudoforests and its original conjecture for forests. In fact, they are still optimal even if we only enforce F to have any constant maximum degree, instead of enforcing every component of F to have at most d edges.","lang":"eng"}],"status":"public","file":[{"creator":"dernst","date_created":"2025-12-30T10:18:56Z","access_level":"open_access","content_type":"application/pdf","file_size":737845,"relation":"main_file","file_id":"20913","checksum":"b1536e9256c4510a0e21452032e43a26","success":1,"file_name":"2025_EuropJournCombinatorics_Mies.pdf","date_updated":"2025-12-30T10:18:56Z"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","isi":1,"oa":1,"article_type":"original","publication_status":"published","author":[{"first_name":"Sebastian","full_name":"Mies, Sebastian","last_name":"Mies"},{"full_name":"Moore, Benjamin","id":"6dc1a1be-bf1c-11ed-8d2b-d044840f49d6","first_name":"Benjamin","last_name":"Moore"},{"first_name":"Evelyne","full_name":"Smith-Roberge, Evelyne","last_name":"Smith-Roberge"}],"title":"Beyond the pseudoforest strong Nine Dragon Tree theorem","year":"2025","issue":"12","_id":"20320","oa_version":"Published Version","month":"12","article_processing_charge":"Yes (via OA deal)","date_updated":"2025-12-30T10:19:10Z","OA_place":"publisher","has_accepted_license":"1","external_id":{"isi":["001529769300002"],"arxiv":["2310.00931"]},"corr_author":"1","intvolume":"       130","quality_controlled":"1","language":[{"iso":"eng"}],"publication_identifier":{"issn":["0195-6698"]},"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"date_created":"2025-09-10T05:36:50Z","file_date_updated":"2025-12-30T10:18:56Z","article_number":"104214","department":[{"_id":"MaKw"}],"PlanS_conform":"1","publisher":"Elsevier","doi":"10.1016/j.ejc.2025.104214","day":"01","type":"journal_article","citation":{"ieee":"S. Mies, B. Moore, and E. Smith-Roberge, “Beyond the pseudoforest strong Nine Dragon Tree theorem,” <i>European Journal of Combinatorics</i>, vol. 130, no. 12. Elsevier, 2025.","apa":"Mies, S., Moore, B., &#38; Smith-Roberge, E. (2025). Beyond the pseudoforest strong Nine Dragon Tree theorem. <i>European Journal of Combinatorics</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.ejc.2025.104214\">https://doi.org/10.1016/j.ejc.2025.104214</a>","mla":"Mies, Sebastian, et al. “Beyond the Pseudoforest Strong Nine Dragon Tree Theorem.” <i>European Journal of Combinatorics</i>, vol. 130, no. 12, 104214, Elsevier, 2025, doi:<a href=\"https://doi.org/10.1016/j.ejc.2025.104214\">10.1016/j.ejc.2025.104214</a>.","ista":"Mies S, Moore B, Smith-Roberge E. 2025. Beyond the pseudoforest strong Nine Dragon Tree theorem. European Journal of Combinatorics. 130(12), 104214.","short":"S. Mies, B. Moore, E. Smith-Roberge, European Journal of Combinatorics 130 (2025).","chicago":"Mies, Sebastian, Benjamin Moore, and Evelyne Smith-Roberge. “Beyond the Pseudoforest Strong Nine Dragon Tree Theorem.” <i>European Journal of Combinatorics</i>. Elsevier, 2025. <a href=\"https://doi.org/10.1016/j.ejc.2025.104214\">https://doi.org/10.1016/j.ejc.2025.104214</a>.","ama":"Mies S, Moore B, Smith-Roberge E. Beyond the pseudoforest strong Nine Dragon Tree theorem. <i>European Journal of Combinatorics</i>. 2025;130(12). doi:<a href=\"https://doi.org/10.1016/j.ejc.2025.104214\">10.1016/j.ejc.2025.104214</a>"},"volume":130,"publication":"European Journal of Combinatorics"},{"publication":"International Mathematics Research Notices","volume":2025,"citation":{"chicago":"Jain, Vishesh, Matthew Alan Kwan, Dhruv Mubayi, and Tuan Tran. “The Edge-Statistics Conjecture for Hypergraphs.” <i>International Mathematics Research Notices</i>. Oxford University Press, 2025. <a href=\"https://doi.org/10.1093/imrn/rnaf273\">https://doi.org/10.1093/imrn/rnaf273</a>.","ama":"Jain V, Kwan MA, Mubayi D, Tran T. The edge-statistics conjecture for hypergraphs. <i>International Mathematics Research Notices</i>. 2025;2025(18). doi:<a href=\"https://doi.org/10.1093/imrn/rnaf273\">10.1093/imrn/rnaf273</a>","ieee":"V. Jain, M. A. Kwan, D. Mubayi, and T. Tran, “The edge-statistics conjecture for hypergraphs,” <i>International Mathematics Research Notices</i>, vol. 2025, no. 18. Oxford University Press, 2025.","ista":"Jain V, Kwan MA, Mubayi D, Tran T. 2025. The edge-statistics conjecture for hypergraphs. International Mathematics Research Notices. 2025(18), rnaf273.","mla":"Jain, Vishesh, et al. “The Edge-Statistics Conjecture for Hypergraphs.” <i>International Mathematics Research Notices</i>, vol. 2025, no. 18, rnaf273, Oxford University Press, 2025, doi:<a href=\"https://doi.org/10.1093/imrn/rnaf273\">10.1093/imrn/rnaf273</a>.","apa":"Jain, V., Kwan, M. A., Mubayi, D., &#38; Tran, T. (2025). The edge-statistics conjecture for hypergraphs. <i>International Mathematics Research Notices</i>. Oxford University Press. <a href=\"https://doi.org/10.1093/imrn/rnaf273\">https://doi.org/10.1093/imrn/rnaf273</a>","short":"V. Jain, M.A. Kwan, D. Mubayi, T. Tran, International Mathematics Research Notices 2025 (2025)."},"type":"journal_article","day":"11","doi":"10.1093/imrn/rnaf273","publisher":"Oxford University Press","article_number":"rnaf273","PlanS_conform":"1","department":[{"_id":"MaKw"}],"date_created":"2025-10-20T11:08:57Z","file_date_updated":"2025-10-21T07:36:56Z","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"publication_identifier":{"eissn":["1687-0247"],"issn":["1073-7928"]},"intvolume":"      2025","quality_controlled":"1","language":[{"iso":"eng"}],"external_id":{"isi":["001575137400001"],"arxiv":["2505.03954"]},"corr_author":"1","date_updated":"2025-12-01T13:00:35Z","OA_place":"publisher","has_accepted_license":"1","article_processing_charge":"Yes (via OA deal)","month":"09","oa_version":"Published Version","year":"2025","issue":"18","_id":"20504","title":"The edge-statistics conjecture for hypergraphs","author":[{"full_name":"Jain, Vishesh","first_name":"Vishesh","last_name":"Jain"},{"orcid":"0000-0002-4003-7567","last_name":"Kwan","first_name":"Matthew Alan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","full_name":"Kwan, Matthew Alan"},{"last_name":"Mubayi","first_name":"Dhruv","full_name":"Mubayi, Dhruv"},{"last_name":"Tran","first_name":"Tuan","full_name":"Tran, Tuan"}],"project":[{"_id":"bd95085b-d553-11ed-ba76-e55d3349be45","grant_number":"101076777","name":"Randomness and structure in combinatorics"}],"article_type":"original","publication_status":"published","oa":1,"file":[{"checksum":"016aa4df9453dc180ae7504ac77bf72f","success":1,"date_updated":"2025-10-21T07:36:56Z","file_name":"2025_IMRN_Jain.pdf","access_level":"open_access","date_created":"2025-10-21T07:36:56Z","creator":"dernst","content_type":"application/pdf","file_size":774323,"relation":"main_file","file_id":"20511"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","isi":1,"status":"public","abstract":[{"text":"Let r, k,  be integers such that 0 ≤  ≤ (k/r). Given a large r-uniform hypergraph G, we consider the\r\nfraction of k-vertex subsets that span exactly  edges. If  is 0 or (k/r), this fraction can be exactly 1 (by taking G to be empty or complete), but for all other values of , one might suspect that this fraction is always significantly smaller than 1.\r\nIn this paper we prove an essentially optimal result along these lines: if  is not 0 or (k/r), then this\r\nfraction is at most (1/e) + ε, assuming k is sufficiently large in terms of r and ε > 0, and G is sufficiently large in terms of k. Previously, this was only known for a very limited range of values of r, k,  (due to Kwan–Sudakov–Tran, Fox–Sauermann, and Martinsson–Mousset–Noever–Trujic). Our result answers a question of Alon–Hefetz–Krivelevich–Tyomkyn, who suggested this as a hypergraph generalization of their edge-statistics conjecture. We also prove a much stronger bound when  is far from 0 and (k/r).","lang":"eng"}],"date_published":"2025-09-11T00:00:00Z","scopus_import":"1","acknowledgement":"This work was supported by NSF CAREER award DMS-2237646 [to V.J.], ERC Starting Grant “RANDSTRUCT” [no. 101076777 to M.K.], NSF grant DMS-2153576 [to D.M.], and the National Key Research and Development Program of China [2023YFA101020 to T.T.].\r\nWe would like to thank Lisa Sauermann for her helpful comments. We would also like to thank Alex Grebennikov for identifying an oversight in the application of Theorem 7.1 (in a previous version of this paper).","arxiv":1,"ddc":["510"],"OA_type":"hybrid"},{"month":"03","article_processing_charge":"Yes (in subscription journal)","title":"On heroes in digraphs with forbidden induced forests","year":"2025","_id":"18753","oa_version":"Published Version","file":[{"access_level":"open_access","date_created":"2025-04-16T09:16:25Z","creator":"dernst","content_type":"application/pdf","relation":"main_file","file_size":1110657,"file_id":"19577","checksum":"2c75f78f40ebb93d16fe3765bda2905a","success":1,"date_updated":"2025-04-16T09:16:25Z","file_name":"2025_EuropJournCombinatorics_Carbonero.pdf"}],"isi":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"project":[{"_id":"bd95085b-d553-11ed-ba76-e55d3349be45","grant_number":"101076777","name":"Randomness and structure in combinatorics"}],"article_type":"original","publication_status":"published","author":[{"last_name":"Carbonero","full_name":"Carbonero, Alvaro","first_name":"Alvaro"},{"first_name":"Hidde","full_name":"Koerts, Hidde","last_name":"Koerts"},{"first_name":"Benjamin","full_name":"Moore, Benjamin","id":"6dc1a1be-bf1c-11ed-8d2b-d044840f49d6","last_name":"Moore"},{"first_name":"Sophie","full_name":"Spirkl, Sophie","last_name":"Spirkl"}],"OA_type":"hybrid","acknowledgement":"We thank the anonymous referees for their careful proofreading which helped improve the presentation of this paper. We also thank one of the anonymous referees for pointing out our construction implies Theorem 1.7!\r\nBenjamin Moore finished this project while a postdoctoral researcher at Charles University, and was supported by project 22-17398S (Flows and cycles in graphs on surfaces) of the Czech Science Foundation. Benjamin Moore is currently funded by RANDSTRUCT No. 101076777, and appreciates the gracious support. We acknowledge the support of the Natural Sciences and Engineering Research Council of Canada (NSERC), [funding reference number RGPIN-2020-03912]. Cette recherche a été financée par le Conseil de recherches en sciences naturelles et en génie du Canada (CRSNG), [numéro de référence RGPIN-2020-03912]. This project was funded in part by the Government of Ontario .","arxiv":1,"ddc":["510"],"abstract":[{"text":"We continue a line of research which studies which hereditary families of digraphs have bounded dichromatic number. For a class of digraphs  C, a hero in  C  is any digraph  H\r\n  such that  H -free digraphs in  C  have bounded dichromatic number. We show that if  F\r\n  is an oriented star of degree at least five, the only heroes for the class of  F -free digraphs are transitive tournaments. For oriented stars  F  of degree exactly four, we show the only heroes in  F -free digraphs are transitive tournaments, or possibly special joins of transitive tournaments. Aboulker et al. characterized the set of heroes of  {H,K1+P2→} -free digraphs almost completely, and we show the same characterization for the class of  {H,rK1+P3→} -free digraphs. Lastly, we show that if we forbid two \"valid\" orientations of brooms, then every transitive tournament is a hero for this class of digraphs.","lang":"eng"}],"scopus_import":"1","date_published":"2025-03-01T00:00:00Z","status":"public","publication":"European Journal of Combinatorics","day":"01","doi":"10.1016/j.ejc.2024.104104","publisher":"Elsevier","type":"journal_article","citation":{"chicago":"Carbonero, Alvaro, Hidde Koerts, Benjamin Moore, and Sophie Spirkl. “On Heroes in Digraphs with Forbidden Induced Forests.” <i>European Journal of Combinatorics</i>. Elsevier, 2025. <a href=\"https://doi.org/10.1016/j.ejc.2024.104104\">https://doi.org/10.1016/j.ejc.2024.104104</a>.","ama":"Carbonero A, Koerts H, Moore B, Spirkl S. On heroes in digraphs with forbidden induced forests. <i>European Journal of Combinatorics</i>. 2025;125. doi:<a href=\"https://doi.org/10.1016/j.ejc.2024.104104\">10.1016/j.ejc.2024.104104</a>","ieee":"A. Carbonero, H. Koerts, B. Moore, and S. Spirkl, “On heroes in digraphs with forbidden induced forests,” <i>European Journal of Combinatorics</i>, vol. 125. Elsevier, 2025.","ista":"Carbonero A, Koerts H, Moore B, Spirkl S. 2025. On heroes in digraphs with forbidden induced forests. European Journal of Combinatorics. 125, 104104.","apa":"Carbonero, A., Koerts, H., Moore, B., &#38; Spirkl, S. (2025). On heroes in digraphs with forbidden induced forests. <i>European Journal of Combinatorics</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.ejc.2024.104104\">https://doi.org/10.1016/j.ejc.2024.104104</a>","mla":"Carbonero, Alvaro, et al. “On Heroes in Digraphs with Forbidden Induced Forests.” <i>European Journal of Combinatorics</i>, vol. 125, 104104, Elsevier, 2025, doi:<a href=\"https://doi.org/10.1016/j.ejc.2024.104104\">10.1016/j.ejc.2024.104104</a>.","short":"A. Carbonero, H. Koerts, B. Moore, S. Spirkl, European Journal of Combinatorics 125 (2025)."},"volume":125,"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"date_created":"2025-01-05T23:01:55Z","file_date_updated":"2025-04-16T09:16:25Z","article_number":"104104","department":[{"_id":"MaKw"}],"date_updated":"2025-05-19T14:06:00Z","OA_place":"publisher","has_accepted_license":"1","external_id":{"arxiv":["2306.04710"],"isi":["001400113700001"]},"corr_author":"1","intvolume":"       125","language":[{"iso":"eng"}],"quality_controlled":"1","publication_identifier":{"issn":["0195-6698"]}},{"publication":"Discrete Mathematics","publisher":"Elsevier","day":"01","doi":"10.1016/j.disc.2024.114377","type":"journal_article","citation":{"short":"P.P. Cortés, P. Kumar, B. Moore, P. Ossona de Mendez, D.A. Quiroz, Discrete Mathematics 348 (2025).","ieee":"P. P. Cortés, P. Kumar, B. Moore, P. Ossona de Mendez, and D. A. Quiroz, “Subchromatic numbers of powers of graphs with excluded minors,” <i>Discrete Mathematics</i>, vol. 348, no. 4. Elsevier, 2025.","ista":"Cortés PP, Kumar P, Moore B, Ossona de Mendez P, Quiroz DA. 2025. Subchromatic numbers of powers of graphs with excluded minors. Discrete Mathematics. 348(4), 114377.","apa":"Cortés, P. P., Kumar, P., Moore, B., Ossona de Mendez, P., &#38; Quiroz, D. A. (2025). Subchromatic numbers of powers of graphs with excluded minors. <i>Discrete Mathematics</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.disc.2024.114377\">https://doi.org/10.1016/j.disc.2024.114377</a>","mla":"Cortés, Pedro P., et al. “Subchromatic Numbers of Powers of Graphs with Excluded Minors.” <i>Discrete Mathematics</i>, vol. 348, no. 4, 114377, Elsevier, 2025, doi:<a href=\"https://doi.org/10.1016/j.disc.2024.114377\">10.1016/j.disc.2024.114377</a>.","ama":"Cortés PP, Kumar P, Moore B, Ossona de Mendez P, Quiroz DA. Subchromatic numbers of powers of graphs with excluded minors. <i>Discrete Mathematics</i>. 2025;348(4). doi:<a href=\"https://doi.org/10.1016/j.disc.2024.114377\">10.1016/j.disc.2024.114377</a>","chicago":"Cortés, Pedro P., Pankaj Kumar, Benjamin Moore, Patrice Ossona de Mendez, and Daniel A. Quiroz. “Subchromatic Numbers of Powers of Graphs with Excluded Minors.” <i>Discrete Mathematics</i>. Elsevier, 2025. <a href=\"https://doi.org/10.1016/j.disc.2024.114377\">https://doi.org/10.1016/j.disc.2024.114377</a>."},"volume":348,"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"file_date_updated":"2025-05-05T12:56:12Z","date_created":"2025-02-05T06:51:08Z","department":[{"_id":"MaKw"}],"article_number":"114377","has_accepted_license":"1","OA_place":"publisher","date_updated":"2025-09-30T10:25:15Z","corr_author":"1","external_id":{"arxiv":["2306.02195"],"isi":["001401656900001"]},"language":[{"iso":"eng"}],"quality_controlled":"1","intvolume":"       348","publication_identifier":{"issn":["0012-365X"]},"month":"04","article_processing_charge":"Yes (via OA deal)","title":"Subchromatic numbers of powers of graphs with excluded minors","issue":"4","_id":"19002","year":"2025","oa_version":"Published Version","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","isi":1,"file":[{"checksum":"6723cbb02b6aea0d05f37d167da00c03","success":1,"file_name":"2025_DiscreteMath_Cortes.pdf","date_updated":"2025-05-05T12:56:12Z","creator":"dernst","date_created":"2025-05-05T12:56:12Z","access_level":"open_access","content_type":"application/pdf","relation":"main_file","file_size":850988,"file_id":"19657"}],"oa":1,"article_type":"original","publication_status":"published","author":[{"last_name":"Cortés","full_name":"Cortés, Pedro P.","first_name":"Pedro P."},{"full_name":"Kumar, Pankaj","first_name":"Pankaj","last_name":"Kumar"},{"first_name":"Benjamin","full_name":"Moore, Benjamin","id":"6dc1a1be-bf1c-11ed-8d2b-d044840f49d6","last_name":"Moore"},{"last_name":"Ossona de Mendez","full_name":"Ossona de Mendez, Patrice","first_name":"Patrice"},{"last_name":"Quiroz","full_name":"Quiroz, Daniel A.","first_name":"Daniel A."}],"OA_type":"hybrid","arxiv":1,"ddc":["510"],"acknowledgement":"We thank an anonymous referee for pointing out an error in an earlier version of Theorem 3.1. We also thank an anonymous referee for pointing out numerous typos in an earlier version of the paper.","date_published":"2025-04-01T00:00:00Z","abstract":[{"text":"A k-subcolouring of a graph G is a function f : V (G) → {0,...,k − 1} such that the set of\r\nvertices coloured i induce a disjoint union of cliques. The subchromatic number, χsub(G),\r\nis the minimum k such that G admits a k-subcolouring. Nešetril, ˇ Ossona de Mendez,\r\nPilipczuk, and Zhu (2020), recently raised the problem of finding tight upper bounds for\r\nχsub(G2) when G is planar. We show that χsub(G2) ≤ 43 when G is planar, improving\r\ntheir bound of 135. We give even better bounds when the planar graph G has larger girth.\r\nMoreover, we show that χsub(G3) ≤ 95, improving the previous bound of 364. For these\r\nwe adapt some recent techniques of Almulhim and Kierstead (2022), while also extending\r\nthe decompositions of triangulated planar graphs of Van den Heuvel, Ossona de Mendez,\r\nQuiroz, Rabinovich and Siebertz (2017), to planar graphs of arbitrary girth. Note that these\r\ndecompositions are the precursors of the graph product structure theorem of planar graphs.\r\nWe give improved bounds for χsub(Gp) for all p ≥ 2, whenever G has bounded treewidth,\r\nbounded simple treewidth, bounded genus, or excludes a clique or biclique as a minor.\r\nFor this we introduce a family of parameters which form a gradation between the strong\r\nand the weak colouring numbers. We give upper bounds for these parameters for graphs\r\ncoming from such classes.\r\nFinally, we give a 2-approximation algorithm for the subchromatic number of graphs\r\nhaving a layering in which each layer has bounded cliquewidth and this layering is\r\ncomputable in polynomial time (like the class of all dth powers of planar graphs, for fixed\r\nd). This algorithm works even if the power p and the graph G is unknown.","lang":"eng"}],"scopus_import":"1","status":"public"},{"external_id":{"arxiv":["2403.04474"],"isi":["001416788600001"]},"date_updated":"2025-09-30T10:28:07Z","OA_place":"publisher","has_accepted_license":"1","publication_identifier":{"eissn":["1496-4279"],"issn":["0008-414X"]},"language":[{"iso":"eng"}],"quality_controlled":"1","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"department":[{"_id":"MaKw"}],"date_created":"2025-02-10T08:39:46Z","type":"journal_article","page":"1-43","doi":"10.4153/s0008414x25000021","publisher":"Cambridge University Press","day":"06","citation":{"ieee":"S. Glock, J. Kim, L. Lichev, O. Pikhurko, and S. Sun, “On the (k + 2, k)-problem of Brown, Erdős, and Sós for k = 5,6,7,” <i>Canadian Journal of Mathematics</i>. Cambridge University Press, pp. 1–43, 2025.","apa":"Glock, S., Kim, J., Lichev, L., Pikhurko, O., &#38; Sun, S. (2025). On the (k + 2, k)-problem of Brown, Erdős, and Sós for k = 5,6,7. <i>Canadian Journal of Mathematics</i>. Cambridge University Press. <a href=\"https://doi.org/10.4153/s0008414x25000021\">https://doi.org/10.4153/s0008414x25000021</a>","ista":"Glock S, Kim J, Lichev L, Pikhurko O, Sun S. 2025. On the (k + 2, k)-problem of Brown, Erdős, and Sós for k = 5,6,7. Canadian Journal of Mathematics., 1–43.","mla":"Glock, Stefan, et al. “On the (k + 2, k)-Problem of Brown, Erdős, and Sós for k = 5,6,7.” <i>Canadian Journal of Mathematics</i>, Cambridge University Press, 2025, pp. 1–43, doi:<a href=\"https://doi.org/10.4153/s0008414x25000021\">10.4153/s0008414x25000021</a>.","short":"S. Glock, J. Kim, L. Lichev, O. Pikhurko, S. Sun, Canadian Journal of Mathematics (2025) 1–43.","chicago":"Glock, Stefan, Jaehoon Kim, Lyuben Lichev, Oleg Pikhurko, and Shumin Sun. “On the (k + 2, k)-Problem of Brown, Erdős, and Sós for k = 5,6,7.” <i>Canadian Journal of Mathematics</i>. Cambridge University Press, 2025. <a href=\"https://doi.org/10.4153/s0008414x25000021\">https://doi.org/10.4153/s0008414x25000021</a>.","ama":"Glock S, Kim J, Lichev L, Pikhurko O, Sun S. On the (k + 2, k)-problem of Brown, Erdős, and Sós for k = 5,6,7. <i>Canadian Journal of Mathematics</i>. 2025:1-43. doi:<a href=\"https://doi.org/10.4153/s0008414x25000021\">10.4153/s0008414x25000021</a>"},"main_file_link":[{"open_access":"1","url":"https://doi.org/10.4153/s0008414x25000021"}],"publication":"Canadian Journal of Mathematics","arxiv":1,"ddc":["500"],"OA_type":"hybrid","status":"public","date_published":"2025-01-06T00:00:00Z","abstract":[{"text":"Let f(r)(n;s,k) denote the maximum number of edges in an n-vertex r-uniform hypergraph containing no subgraph with k edges and at most s vertices. Brown, Erdős and Sós [New directions in the theory of graphs (Proc. Third Ann Arbor Conf., Univ. Michigan 1971), pp. 53--63, Academic Press 1973] conjectured that the limit limn→∞n−2f(3)(n;k+2,k) exists for all k. The value of the limit was previously determined for k=2 in the original paper of Brown, Erdős and Sós, for k=3 by Glock [Bull. Lond. Math. Soc. 51 (2019) 230--236] and for k=4 by Glock, Joos, Kim, Kühn, Lichev and Pikhurko [arXiv:2209.14177, accepted by Proc. Amer. Math. Soc.] while Delcourt and Postle [arXiv:2210.01105, accepted by Proc. Amer. Math. Soc.] proved the conjecture (without determining the limiting value).\r\nIn this paper, we determine the value of the limit in the Brown-Erdős-Sós Problem for k∈{5,6,7}. More generally, we obtain the value of limn→∞n−2f(r)(n;rk−2k+2,k) for all r≥3 and k∈{5,6,7}. In addition, by combining these new values with recent results of Bennett, Cushman and Dudek [arXiv:2309.00182] we obtain new asymptotic values for several generalised Ramsey numbers.","lang":"eng"}],"scopus_import":"1","oa":1,"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","isi":1,"author":[{"last_name":"Glock","first_name":"Stefan","full_name":"Glock, Stefan"},{"first_name":"Jaehoon","full_name":"Kim, Jaehoon","last_name":"Kim"},{"last_name":"Lichev","first_name":"Lyuben","id":"9aa8388e-d003-11ee-8458-c4c1d7447977","full_name":"Lichev, Lyuben"},{"first_name":"Oleg","full_name":"Pikhurko, Oleg","last_name":"Pikhurko"},{"last_name":"Sun","full_name":"Sun, Shumin","first_name":"Shumin"}],"article_type":"original","publication_status":"epub_ahead","title":"On the (k + 2, k)-problem of Brown, Erdős, and Sós for k = 5,6,7","oa_version":"Published Version","year":"2025","_id":"19017","month":"01","article_processing_charge":"No"},{"publication":"European Journal of Combinatorics","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2204.07376"}],"citation":{"ama":"Burova S, Lichev L. The semi-random tree process. <i>European Journal of Combinatorics</i>. 2025;126. doi:<a href=\"https://doi.org/10.1016/j.ejc.2025.104120\">10.1016/j.ejc.2025.104120</a>","chicago":"Burova, Sofiya, and Lyuben Lichev. “The Semi-Random Tree Process.” <i>European Journal of Combinatorics</i>. Elsevier, 2025. <a href=\"https://doi.org/10.1016/j.ejc.2025.104120\">https://doi.org/10.1016/j.ejc.2025.104120</a>.","short":"S. Burova, L. Lichev, European Journal of Combinatorics 126 (2025).","mla":"Burova, Sofiya, and Lyuben Lichev. “The Semi-Random Tree Process.” <i>European Journal of Combinatorics</i>, vol. 126, 104120, Elsevier, 2025, doi:<a href=\"https://doi.org/10.1016/j.ejc.2025.104120\">10.1016/j.ejc.2025.104120</a>.","ista":"Burova S, Lichev L. 2025. The semi-random tree process. European Journal of Combinatorics. 126, 104120.","apa":"Burova, S., &#38; Lichev, L. (2025). The semi-random tree process. <i>European Journal of Combinatorics</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.ejc.2025.104120\">https://doi.org/10.1016/j.ejc.2025.104120</a>","ieee":"S. Burova and L. Lichev, “The semi-random tree process,” <i>European Journal of Combinatorics</i>, vol. 126. Elsevier, 2025."},"volume":126,"day":"01","publisher":"Elsevier","doi":"10.1016/j.ejc.2025.104120","type":"journal_article","date_created":"2025-02-10T09:00:53Z","department":[{"_id":"MaKw"}],"article_number":"104120","quality_controlled":"1","language":[{"iso":"eng"}],"intvolume":"       126","publication_identifier":{"issn":["0195-6698"]},"OA_place":"repository","date_updated":"2025-09-30T10:28:42Z","external_id":{"arxiv":["2204.07376 "],"isi":["001420659400001"]},"article_processing_charge":"No","month":"05","_id":"19018","year":"2025","oa_version":"Preprint","title":"The semi-random tree process","article_type":"original","publication_status":"published","author":[{"full_name":"Burova, Sofiya","first_name":"Sofiya","last_name":"Burova"},{"first_name":"Lyuben","full_name":"Lichev, Lyuben","id":"9aa8388e-d003-11ee-8458-c4c1d7447977","last_name":"Lichev"}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","isi":1,"oa":1,"date_published":"2025-05-01T00:00:00Z","abstract":[{"text":"The online semi-random graph process is a one-player game which starts with the empty graph on n vertices. At every round, a player (called Builder) is presented with a vertex v chosen uniformly at random and independently from previous rounds, and constructs an edge of their choice that is incident to v. Inspired by recent advances on the semi-random graph process, we define a family of generalized online semi-random models.\r\nWe analyse a particular instance that shares similar features with the original semi-random graph process and determine the hitting times of the classical graph properties minimum degree k,k-connectivity, containment of a perfect matching, a Hamiltonian cycle and an \r\nH-factor for a fixed graph H possessing an additional tree-like property. Along the way, we derive a few consequences of the famous Aldous-Broder algorithm that may be of independent interest.","lang":"eng"}],"scopus_import":"1","status":"public","OA_type":"green","arxiv":1,"acknowledgement":"We are grateful to Dieter Mitsche for related discussions and to several anonymous referees for multiple useful comments."},{"month":"03","article_processing_charge":"No","title":"Size‐Ramsey numbers of graphs with maximum degree three","oa_version":"Published Version","year":"2025","issue":"3","_id":"19418","oa":1,"file":[{"content_type":"application/pdf","access_level":"open_access","creator":"dernst","date_created":"2025-03-20T09:46:20Z","file_id":"19427","file_size":625974,"relation":"main_file","success":1,"checksum":"d8e0a03286a44c4f672709e3c829206e","date_updated":"2025-03-20T09:46:20Z","file_name":"2025_JournLondonMath_Draganic.pdf"}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","isi":1,"author":[{"full_name":"Draganić, Nemanja","first_name":"Nemanja","last_name":"Draganić"},{"first_name":"Kalina H","full_name":"Petrova, Kalina H","id":"554ff4e4-f325-11ee-b0c4-a10dbd523381","last_name":"Petrova"}],"project":[{"_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","grant_number":"101034413","name":"IST-BRIDGE: International postdoctoral program","call_identifier":"H2020"}],"article_type":"original","publication_status":"published","acknowledgement":"We would like to thank Rajko Nenadov and Miloš Trujić for helpful comments and discussions, as well as the anonymous referees for their very useful feedback, which improved the paper considerably. This research was supported by SNSF Project 217926. Part of this research was conducted while Nemanja Draganić was at ETH Zürich, Switzerland, and partially supported by SNSF Grant 200021_196965. This project has received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement Number: 101034413. Part of this research was conducted while Kalina Petrova was at the Department of Computer Science, ETH Zürich, Switzerland, supported by SNSF Grant CRSII5 173721.","ddc":["510"],"arxiv":1,"OA_type":"hybrid","status":"public","abstract":[{"lang":"eng","text":"The size-Ramsey number r^(H) of a graph H is the smallest number of edges a (host) graph G can have, such that for any red/blue colouring of G, there is a monochromatic copy of H in G. Recently, Conlon, Nenadov and Trujić showed that if H is a graph on n vertices and maximum degree three, then r^(H)=O(n8/5), improving upon the upper bound of n5/3+o(1) by Kohayakawa, Rödl, Schacht and Szemerédi. In this paper we show that r^(H)≤n3/2+o(1). While the previously used host graphs were vanilla binomial random graphs, we prove our result using a novel host graph construction. Our bound hits a natural barrier of the existing methods."}],"scopus_import":"1","date_published":"2025-03-01T00:00:00Z","publication":"Journal of the London Mathematical Society","ec_funded":1,"type":"journal_article","doi":"10.1112/jlms.70116","publisher":"Wiley","day":"01","volume":111,"citation":{"chicago":"Draganić, Nemanja, and Kalina H Petrova. “Size‐Ramsey Numbers of Graphs with Maximum Degree Three.” <i>Journal of the London Mathematical Society</i>. Wiley, 2025. <a href=\"https://doi.org/10.1112/jlms.70116\">https://doi.org/10.1112/jlms.70116</a>.","ama":"Draganić N, Petrova KH. Size‐Ramsey numbers of graphs with maximum degree three. <i>Journal of the London Mathematical Society</i>. 2025;111(3). doi:<a href=\"https://doi.org/10.1112/jlms.70116\">10.1112/jlms.70116</a>","ieee":"N. Draganić and K. H. Petrova, “Size‐Ramsey numbers of graphs with maximum degree three,” <i>Journal of the London Mathematical Society</i>, vol. 111, no. 3. Wiley, 2025.","mla":"Draganić, Nemanja, and Kalina H. Petrova. “Size‐Ramsey Numbers of Graphs with Maximum Degree Three.” <i>Journal of the London Mathematical Society</i>, vol. 111, no. 3, e70116, Wiley, 2025, doi:<a href=\"https://doi.org/10.1112/jlms.70116\">10.1112/jlms.70116</a>.","apa":"Draganić, N., &#38; Petrova, K. H. (2025). Size‐Ramsey numbers of graphs with maximum degree three. <i>Journal of the London Mathematical Society</i>. Wiley. <a href=\"https://doi.org/10.1112/jlms.70116\">https://doi.org/10.1112/jlms.70116</a>","ista":"Draganić N, Petrova KH. 2025. Size‐Ramsey numbers of graphs with maximum degree three. Journal of the London Mathematical Society. 111(3), e70116.","short":"N. Draganić, K.H. Petrova, Journal of the London Mathematical Society 111 (2025)."},"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"article_number":"e70116","department":[{"_id":"MaKw"}],"date_created":"2025-03-19T09:03:37Z","file_date_updated":"2025-03-20T09:46:20Z","external_id":{"arxiv":["2207.05048"],"isi":["001450645400019"]},"date_updated":"2025-09-30T11:05:07Z","OA_place":"publisher","has_accepted_license":"1","publication_identifier":{"issn":["0024-6107"],"eissn":["1469-7750"]},"intvolume":"       111","quality_controlled":"1","language":[{"iso":"eng"}]},{"month":"03","article_processing_charge":"Yes","title":"Extremal, enumerative and probabilistic results on ordered hypergraph matchings","oa_version":"Published Version","year":"2025","_id":"19433","oa":1,"file":[{"content_type":"application/pdf","creator":"dernst","date_created":"2025-04-03T11:24:35Z","access_level":"open_access","file_id":"19468","file_size":630297,"relation":"main_file","success":1,"checksum":"f396270ad78c1ed67095c8e5a66fca26","file_name":"2025_ForumMathSigma_Anastos.pdf","date_updated":"2025-04-03T11:24:35Z"}],"isi":1,"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","author":[{"last_name":"Anastos","first_name":"Michael","full_name":"Anastos, Michael","id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb"},{"full_name":"Jin, Zhihan","first_name":"Zhihan","last_name":"Jin"},{"orcid":"0000-0002-4003-7567","last_name":"Kwan","first_name":"Matthew Alan","full_name":"Kwan, Matthew Alan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3"},{"first_name":"Benny","full_name":"Sudakov, Benny","last_name":"Sudakov"}],"project":[{"call_identifier":"H2020","name":"IST-BRIDGE: International postdoctoral program","grant_number":"101034413","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c"},{"_id":"bd95085b-d553-11ed-ba76-e55d3349be45","grant_number":"101076777","name":"Randomness and structure in combinatorics"}],"article_type":"original","publication_status":"published","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.","arxiv":1,"ddc":["510"],"OA_type":"gold","status":"public","date_published":"2025-03-14T00:00:00Z","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."}],"scopus_import":"1","publication":"Forum of Mathematics, Sigma","ec_funded":1,"type":"journal_article","day":"14","publisher":"Cambridge University Press","doi":"10.1017/fms.2024.144","volume":13,"citation":{"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>","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>.","short":"M. Anastos, Z. Jin, M.A. Kwan, B. Sudakov, Forum of Mathematics, Sigma 13 (2025).","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>","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>.","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.","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."},"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"article_number":"e55","department":[{"_id":"MaKw"}],"date_created":"2025-03-20T12:59:14Z","file_date_updated":"2025-04-03T11:24:35Z","external_id":{"isi":["001444429200001"],"arxiv":["2308.12268"]},"corr_author":"1","date_updated":"2025-09-30T11:18:57Z","has_accepted_license":"1","OA_place":"publisher","publication_identifier":{"issn":["2050-5094"]},"intvolume":"        13","quality_controlled":"1","language":[{"iso":"eng"}]},{"title":"The completion numbers of hamiltonicity and pancyclicity in random graphs","_id":"19440","issue":"2","year":"2025","oa_version":"Published Version","month":"03","article_processing_charge":"Yes (in subscription journal)","OA_type":"hybrid","arxiv":1,"ddc":["510"],"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.","date_published":"2025-03-01T00:00:00Z","abstract":[{"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.","lang":"eng"}],"scopus_import":"1","status":"public","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","isi":1,"file":[{"file_id":"19459","relation":"main_file","file_size":549236,"content_type":"application/pdf","access_level":"open_access","creator":"dernst","date_created":"2025-03-25T11:46:27Z","date_updated":"2025-03-25T11:46:27Z","file_name":"2025_RandomStruc_Alon.pdf","success":1,"checksum":"6067747e805fa356d560dc45f2a89918"}],"oa":1,"publication_status":"published","article_type":"original","project":[{"name":"IST-BRIDGE: International postdoctoral program","call_identifier":"H2020","grant_number":"101034413","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c"}],"author":[{"first_name":"Yahav","full_name":"Alon, Yahav","last_name":"Alon"},{"last_name":"Anastos","full_name":"Anastos, Michael","id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb","first_name":"Michael"}],"doi":"10.1002/rsa.21286","publisher":"Wiley","day":"01","type":"journal_article","ec_funded":1,"citation":{"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>","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>.","short":"Y. Alon, M. Anastos, Random Structures and Algorithms 66 (2025).","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.","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>","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."},"volume":66,"publication":"Random Structures and Algorithms","OA_place":"publisher","has_accepted_license":"1","date_updated":"2025-09-30T11:15:41Z","external_id":{"isi":["001420226800001"],"arxiv":["2304.03710"]},"language":[{"iso":"eng"}],"quality_controlled":"1","intvolume":"        66","publication_identifier":{"eissn":["1098-2418"],"issn":["1042-9832"]},"tmp":{"short":"CC BY-NC (4.0)","name":"Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)","image":"/images/cc_by_nc.png","legal_code_url":"https://creativecommons.org/licenses/by-nc/4.0/legalcode"},"date_created":"2025-03-23T23:01:26Z","file_date_updated":"2025-03-25T11:46:27Z","department":[{"_id":"MaKw"}],"article_number":"e21286"},{"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"department":[{"_id":"MaKw"}],"date_created":"2025-04-06T22:01:32Z","file_date_updated":"2025-08-05T12:54:06Z","external_id":{"isi":["001449245700001"],"arxiv":["2310.08449"]},"date_updated":"2025-09-30T11:26:00Z","has_accepted_license":"1","OA_place":"publisher","publication_identifier":{"issn":["0963-5483"],"eissn":["1469-2163"]},"intvolume":"        34","language":[{"iso":"eng"}],"quality_controlled":"1","publication":"Combinatorics Probability and Computing","type":"journal_article","ec_funded":1,"page":"559-564","day":"01","doi":"10.1017/S0963548325000045","publisher":"Cambridge University Press","volume":34,"citation":{"ama":"Christoph M, Petrova KH, Steiner R. A note on digraph splitting. <i>Combinatorics Probability and Computing</i>. 2025;34(4):559-564. doi:<a href=\"https://doi.org/10.1017/S0963548325000045\">10.1017/S0963548325000045</a>","chicago":"Christoph, Micha, Kalina H Petrova, and Raphael Steiner. “A Note on Digraph Splitting.” <i>Combinatorics Probability and Computing</i>. Cambridge University Press, 2025. <a href=\"https://doi.org/10.1017/S0963548325000045\">https://doi.org/10.1017/S0963548325000045</a>.","short":"M. Christoph, K.H. Petrova, R. Steiner, Combinatorics Probability and Computing 34 (2025) 559–564.","ieee":"M. Christoph, K. H. Petrova, and R. Steiner, “A note on digraph splitting,” <i>Combinatorics Probability and Computing</i>, vol. 34, no. 4. Cambridge University Press, pp. 559–564, 2025.","apa":"Christoph, M., Petrova, K. H., &#38; Steiner, R. (2025). A note on digraph splitting. <i>Combinatorics Probability and Computing</i>. Cambridge University Press. <a href=\"https://doi.org/10.1017/S0963548325000045\">https://doi.org/10.1017/S0963548325000045</a>","mla":"Christoph, Micha, et al. “A Note on Digraph Splitting.” <i>Combinatorics Probability and Computing</i>, vol. 34, no. 4, Cambridge University Press, 2025, pp. 559–64, doi:<a href=\"https://doi.org/10.1017/S0963548325000045\">10.1017/S0963548325000045</a>.","ista":"Christoph M, Petrova KH, Steiner R. 2025. A note on digraph splitting. Combinatorics Probability and Computing. 34(4), 559–564."},"oa":1,"file":[{"content_type":"application/pdf","access_level":"open_access","date_created":"2025-08-05T12:54:06Z","creator":"dernst","file_id":"20135","relation":"main_file","file_size":188818,"success":1,"checksum":"98491e59b4f0d05d69f608bbd5706f1a","date_updated":"2025-08-05T12:54:06Z","file_name":"2025_CombProbComputing_Christoph.pdf"}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","isi":1,"author":[{"last_name":"Christoph","full_name":"Christoph, Micha","first_name":"Micha"},{"last_name":"Petrova","first_name":"Kalina H","id":"554ff4e4-f325-11ee-b0c4-a10dbd523381","full_name":"Petrova, Kalina H"},{"last_name":"Steiner","full_name":"Steiner, Raphael","first_name":"Raphael"}],"project":[{"_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","grant_number":"101034413","name":"IST-BRIDGE: International postdoctoral program","call_identifier":"H2020"}],"publication_status":"published","article_type":"original","acknowledgement":"Funded by SNSF Ambizione grant No. 216071. 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. Funded by SNSF grant CRSII5, 173721.","ddc":["510"],"arxiv":1,"OA_type":"hybrid","status":"public","scopus_import":"1","abstract":[{"text":"A tantalizing open problem, posed independently by Stiebitz in 1995 and by Alon in 1996 and again in 2006, asks whether for every pair of integers  s,t≥1 there exists a finite number  F(s,t)\r\nsuch that the vertex set of every digraph of minimum out-degree at least  F(s,t) can be partitioned into non-empty parts  A  and  B  such that the subdigraphs induced on  A\r\n  and  B  have minimum out-degree at least  s  and  t , respectively.\r\nIn this short note, we prove that if  F(2,2)  exists, then all the numbers  F(s,t)  with  s,t≥1\r\n  exist and satisfy  F(s,t)=Θ(s+t) . In consequence, the problem of Alon and Stiebitz reduces to the case  s=t=2 . Moreover, the numbers  F(s,t)  with  s,t≥2  either all exist and grow linearly, or all of them do not exist.","lang":"eng"}],"date_published":"2025-07-01T00:00:00Z","month":"07","article_processing_charge":"Yes (in subscription journal)","title":"A note on digraph splitting","oa_version":"Published Version","year":"2025","issue":"4","_id":"19503"},{"publication":"Journal of the London Mathematical Society","type":"journal_article","publisher":"Wiley","doi":"10.1112/jlms.70101","day":"01","volume":111,"citation":{"ama":"Glasgow M, Kwan MA, Sah A, Sawhney M. A central limit theorem for the matching number of a sparse random graph. <i>Journal of the London Mathematical Society</i>. 2025;111(4). doi:<a href=\"https://doi.org/10.1112/jlms.70101\">10.1112/jlms.70101</a>","chicago":"Glasgow, Margalit, Matthew Alan Kwan, Ashwin Sah, and Mehtaab Sawhney. “A Central Limit Theorem for the Matching Number of a Sparse Random Graph.” <i>Journal of the London Mathematical Society</i>. Wiley, 2025. <a href=\"https://doi.org/10.1112/jlms.70101\">https://doi.org/10.1112/jlms.70101</a>.","short":"M. Glasgow, M.A. Kwan, A. Sah, M. Sawhney, Journal of the London Mathematical Society 111 (2025).","apa":"Glasgow, M., Kwan, M. A., Sah, A., &#38; Sawhney, M. (2025). A central limit theorem for the matching number of a sparse random graph. <i>Journal of the London Mathematical Society</i>. Wiley. <a href=\"https://doi.org/10.1112/jlms.70101\">https://doi.org/10.1112/jlms.70101</a>","mla":"Glasgow, Margalit, et al. “A Central Limit Theorem for the Matching Number of a Sparse Random Graph.” <i>Journal of the London Mathematical Society</i>, vol. 111, no. 4, e70101, Wiley, 2025, doi:<a href=\"https://doi.org/10.1112/jlms.70101\">10.1112/jlms.70101</a>.","ista":"Glasgow M, Kwan MA, Sah A, Sawhney M. 2025. A central limit theorem for the matching number of a sparse random graph. Journal of the London Mathematical Society. 111(4), e70101.","ieee":"M. Glasgow, M. A. Kwan, A. Sah, and M. Sawhney, “A central limit theorem for the matching number of a sparse random graph,” <i>Journal of the London Mathematical Society</i>, vol. 111, no. 4. Wiley, 2025."},"tmp":{"short":"CC BY-NC (4.0)","name":"Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)","image":"/images/cc_by_nc.png","legal_code_url":"https://creativecommons.org/licenses/by-nc/4.0/legalcode"},"article_number":"e70101","department":[{"_id":"MaKw"}],"file_date_updated":"2025-04-15T13:18:43Z","date_created":"2025-04-13T22:01:19Z","external_id":{"arxiv":["2402.05851"],"isi":["001473087200024"]},"corr_author":"1","date_updated":"2025-09-30T11:35:55Z","has_accepted_license":"1","OA_place":"publisher","publication_identifier":{"eissn":["1469-7750"],"issn":["0024-6107"]},"intvolume":"       111","language":[{"iso":"eng"}],"quality_controlled":"1","month":"04","article_processing_charge":"Yes (via OA deal)","title":"A central limit theorem for the matching number of a sparse random graph","oa_version":"Published Version","year":"2025","_id":"19554","issue":"4","oa":1,"file":[{"content_type":"application/pdf","creator":"dernst","date_created":"2025-04-15T13:18:43Z","access_level":"open_access","file_id":"19564","file_size":392208,"relation":"main_file","success":1,"checksum":"69ce9feaf64e776b99f3afd1041b1b11","file_name":"2025_JourLondMathSoc_Glasgow.pdf","date_updated":"2025-04-15T13:18:43Z"}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","isi":1,"author":[{"full_name":"Glasgow, Margalit","first_name":"Margalit","last_name":"Glasgow"},{"orcid":"0000-0002-4003-7567","last_name":"Kwan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","full_name":"Kwan, Matthew Alan","first_name":"Matthew Alan"},{"full_name":"Sah, Ashwin","first_name":"Ashwin","last_name":"Sah"},{"full_name":"Sawhney, Mehtaab","first_name":"Mehtaab","last_name":"Sawhney"}],"project":[{"name":"Randomness and structure in combinatorics","_id":"bd95085b-d553-11ed-ba76-e55d3349be45","grant_number":"101076777"}],"publication_status":"published","article_type":"original","acknowledgement":"We would like to thank Christina Goldschmidt and Eleonora Kreačić for insightful discussions and clarifications about their work in the thesis [26]. Matthew Kwan was supported by ERC Starting Grant ‘RANDSTRUCT’ No. 101076777. Ashwin Sah and Mehtaab Sawhney were supported by NSF Graduate Research Fellowship Program DGE-2141064. Ashwin Sah was supported by the PD Soros Fellowship.\r\nOpen access funding provided by Institute of Science and Technology Austria/KEMÖ.","ddc":["510"],"arxiv":1,"OA_type":"hybrid","status":"public","scopus_import":"1","date_published":"2025-04-01T00:00:00Z","abstract":[{"lang":"eng","text":"In 1981, Karp and Sipser proved a law of large numbers for the matching number of a sparse Erdős–Rényi random graph, in an influential paper pioneering the so-called differential equation method for analysis of random graph processes. Strengthening this classical result, and answering a question of Aronson, Frieze and Pittel, we prove a central limit theorem in the same setting: the fluctuations in the matching number of a sparse random graph are asymptotically Gaussian. Our new contribution is to prove this central limit theorem in the subcritical and critical regimes, according to a celebrated algorithmic phase transition first observed by Karp and Sipser. Indeed, in the supercritical regime, a central limit theorem has recently been proved in the PhD thesis of Kreačić, using a stochastic generalisation of the differential equation method (comparing the so-called Karp–Sipser process to a system of stochastic differential equations). Our proof builds on these methods, and introduces new techniques to handle certain degeneracies present in the subcritical and critical cases. Curiously, our new techniques lead to a non-constructive result: we are able to characterise the fluctuations of the matching number around its mean, despite these fluctuations being much smaller than the error terms in our best estimates of the mean. We also prove a central limit theorem for the rank of the adjacency matrix of a sparse random graph."}]}]