--- OA_place: publisher OA_type: hybrid PlanS_conform: '1' _id: '21159' abstract: - lang: eng 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." 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). article_number: '5' article_processing_charge: Yes (via OA deal) article_type: original arxiv: 1 author: - first_name: Matthew Alan full_name: Kwan, Matthew Alan id: 5fca0887-a1db-11eb-95d1-ca9d5e0453b3 last_name: Kwan orcid: 0000-0002-4003-7567 - first_name: Roodabeh full_name: Safavi Hemami, Roodabeh id: 72ed2640-8972-11ed-ae7b-f9c81ec75154 last_name: Safavi Hemami - first_name: Yiting full_name: Wang, Yiting id: 1917d194-076e-11ed-97cd-837255f88785 last_name: Wang orcid: 0000-0002-2856-767X citation: ama: Kwan MA, Safavi Hemami R, Wang Y. Counting perfect matchings in Dirac hypergraphs. Combinatorica. 2026;46. doi:10.1007/s00493-025-00194-8 apa: Kwan, M. A., Safavi Hemami, R., & Wang, Y. (2026). Counting perfect matchings in Dirac hypergraphs. Combinatorica. Springer Nature. https://doi.org/10.1007/s00493-025-00194-8 chicago: Kwan, Matthew Alan, Roodabeh Safavi Hemami, and Yiting Wang. “Counting Perfect Matchings in Dirac Hypergraphs.” Combinatorica. Springer Nature, 2026. https://doi.org/10.1007/s00493-025-00194-8. ieee: M. A. Kwan, R. Safavi Hemami, and Y. Wang, “Counting perfect matchings in Dirac hypergraphs,” Combinatorica, vol. 46. Springer Nature, 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.” Combinatorica, vol. 46, 5, Springer Nature, 2026, doi:10.1007/s00493-025-00194-8. short: M.A. Kwan, R. Safavi Hemami, Y. Wang, Combinatorica 46 (2026). corr_author: '1' date_created: 2026-02-08T23:02:49Z date_published: 2026-02-01T00:00:00Z date_updated: 2026-02-16T09:55:17Z day: '01' ddc: - '510' department: - _id: MaKw - _id: MoHe doi: 10.1007/s00493-025-00194-8 external_id: arxiv: - '2408.09589' file: - access_level: open_access checksum: 47b0031d90b0e6b9a843f422a1486089 content_type: application/pdf creator: dernst date_created: 2026-02-16T09:52:38Z date_updated: 2026-02-16T09:52:38Z file_id: '21228' file_name: 2026_Combinatorica_Kwan.pdf file_size: 539646 relation: main_file success: 1 file_date_updated: 2026-02-16T09:52:38Z fulldoi: https://doi.org/10.1007/s00493-025-00194-8 has_accepted_license: '1' intvolume: ' 46' language: - iso: eng month: '02' oa: 1 oa_version: Published Version publication: Combinatorica publication_identifier: eissn: - 1439-6912 issn: - 0209-9683 publication_status: published publisher: Springer Nature quality_controlled: '1' scopus_import: '1' status: public title: Counting perfect matchings in Dirac hypergraphs tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 46 year: '2026' ... --- DOAJ_listed: '1' OA_place: publisher OA_type: gold _id: '21884' abstract: - lang: eng text: "We show that a randomly perturbed digraph, where we start with a dense digraph Dα and add a small number of random edges to it, will typically contain a fixed orientation of a bounded-degree spanning tree. This answers a question posed by Araujo, Balogh, Krueger, Piga and Treglown and generalizes the corresponding result for randomly perturbed graphs by Krivelevich, Kwan and Sudakov. More specifically, we prove that there exists a constant c=c(α,Δ) such that if \r\nT is an oriented tree with maximum degree Δ and Dα is an n-vertex digraph with minimum semidegree αn, then the graph obtained by adding cn uniformly random edges to Dα will contain T with high probability." acknowledgement: "We thank the anonymous referees for many helpful comments on an earlier version of this\r\narticle. Kalina Petrova was supported by grant no. CRSII5 173721 of the Swiss National\r\nScience Foundation, and by the European Union’s Horizon 2020 research and innovation\r\nprogramme under the Marie Sk lodowska-Curie grant agreement No. 101034413" article_number: P2.24 article_processing_charge: Yes article_type: original arxiv: 1 author: - first_name: Patryk full_name: Morawski, Patryk last_name: Morawski - first_name: Kalina H full_name: Petrova, Kalina H id: 554ff4e4-f325-11ee-b0c4-a10dbd523381 last_name: Petrova citation: ama: Morawski P, Petrova KH. Randomly perturbed digraphs also have bounded-degree spanning trees. Electronic Journal of Combinatorics. 2026;33(2). doi:10.37236/13316 apa: Morawski, P., & Petrova, K. H. (2026). Randomly perturbed digraphs also have bounded-degree spanning trees. Electronic Journal of Combinatorics. Electronic Journal of Combinatorics. https://doi.org/10.37236/13316 chicago: Morawski, Patryk, and Kalina H Petrova. “Randomly Perturbed Digraphs Also Have Bounded-Degree Spanning Trees.” Electronic Journal of Combinatorics. Electronic Journal of Combinatorics, 2026. https://doi.org/10.37236/13316. ieee: P. Morawski and K. H. Petrova, “Randomly perturbed digraphs also have bounded-degree spanning trees,” Electronic Journal of Combinatorics, vol. 33, no. 2. Electronic Journal of Combinatorics, 2026. ista: Morawski P, Petrova KH. 2026. Randomly perturbed digraphs also have bounded-degree spanning trees. Electronic Journal of Combinatorics. 33(2), P2.24. mla: Morawski, Patryk, and Kalina H. Petrova. “Randomly Perturbed Digraphs Also Have Bounded-Degree Spanning Trees.” Electronic Journal of Combinatorics, vol. 33, no. 2, P2.24, Electronic Journal of Combinatorics, 2026, doi:10.37236/13316. short: P. Morawski, K.H. Petrova, Electronic Journal of Combinatorics 33 (2026). corr_author: '1' date_created: 2026-05-17T22:02:11Z date_published: 2026-05-08T00:00:00Z date_updated: 2026-05-18T08:50:18Z day: '08' ddc: - '510' department: - _id: MaKw doi: 10.37236/13316 ec_funded: 1 external_id: arxiv: - '2306.14648' file: - access_level: open_access checksum: 9e8402cb2e8870ba7ded9ae7b308201a content_type: application/pdf creator: dernst date_created: 2026-05-18T08:46:26Z date_updated: 2026-05-18T08:46:26Z file_id: '21893' file_name: 2026_ElectrJournCombinatorics_Morawski.pdf file_size: 399969 relation: main_file success: 1 file_date_updated: 2026-05-18T08:46:26Z fulldoi: https://doi.org/10.37236/13316 has_accepted_license: '1' intvolume: ' 33' issue: '2' language: - iso: eng license: https://creativecommons.org/licenses/by-nd/4.0/ month: '05' oa: 1 oa_version: Published Version project: - _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c call_identifier: H2020 grant_number: '101034413' name: 'IST-BRIDGE: International postdoctoral program' publication: Electronic Journal of Combinatorics publication_identifier: eissn: - 1077-8926 publication_status: published publisher: Electronic Journal of Combinatorics quality_controlled: '1' scopus_import: '1' status: public title: Randomly perturbed digraphs also have bounded-degree spanning trees tmp: image: /image/cc_by_nd.png legal_code_url: https://creativecommons.org/licenses/by-nd/4.0/legalcode name: Creative Commons Attribution-NoDerivatives 4.0 International (CC BY-ND 4.0) short: CC BY-ND (4.0) type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 33 year: '2026' ... --- OA_place: publisher OA_type: hybrid PlanS_conform: '1' _id: '20422' 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. article_processing_charge: Yes (via OA deal) article_type: original arxiv: 1 author: - first_name: Micha full_name: Christoph, Micha last_name: Christoph - first_name: Rajko full_name: Nenadov, Rajko last_name: Nenadov - first_name: Kalina H full_name: Petrova, Kalina H id: 554ff4e4-f325-11ee-b0c4-a10dbd523381 last_name: Petrova citation: ama: Christoph M, Nenadov R, Petrova KH. The Hamilton space of pseudorandom graphs. Journal of Combinatorial Theory Series B. 2026;176:254-267. doi:10.1016/j.jctb.2025.09.002 apa: Christoph, M., Nenadov, R., & Petrova, K. H. (2026). The Hamilton space of pseudorandom graphs. Journal of Combinatorial Theory Series B. Elsevier. https://doi.org/10.1016/j.jctb.2025.09.002 chicago: Christoph, Micha, Rajko Nenadov, and Kalina H Petrova. “The Hamilton Space of Pseudorandom Graphs.” Journal of Combinatorial Theory Series B. Elsevier, 2026. https://doi.org/10.1016/j.jctb.2025.09.002. ieee: M. Christoph, R. Nenadov, and K. H. Petrova, “The Hamilton space of pseudorandom graphs,” Journal of Combinatorial Theory Series B, 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. mla: Christoph, Micha, et al. “The Hamilton Space of Pseudorandom Graphs.” Journal of Combinatorial Theory Series B, vol. 176, Elsevier, 2026, pp. 254–67, doi:10.1016/j.jctb.2025.09.002. short: M. Christoph, R. Nenadov, K.H. Petrova, Journal of Combinatorial Theory Series B 176 (2026) 254–267. corr_author: '1' date_created: 2025-10-05T22:01:34Z date_published: 2026-01-01T00:00:00Z date_updated: 2026-01-05T13:29:52Z day: '01' ddc: - '510' department: - _id: MaKw doi: 10.1016/j.jctb.2025.09.002 ec_funded: 1 external_id: arxiv: - '2402.01447' isi: - '001585783400001' file: - access_level: open_access checksum: 60676af4af4b3243ba187e7d65440d99 content_type: application/pdf creator: dernst date_created: 2026-01-05T13:29:34Z date_updated: 2026-01-05T13:29:34Z file_id: '20953' file_name: 2026_JourCombTheoryB_Christoph.pdf file_size: 688924 relation: main_file success: 1 file_date_updated: 2026-01-05T13:29:34Z fulldoi: https://doi.org/10.1016/j.jctb.2025.09.002 has_accepted_license: '1' intvolume: ' 176' isi: 1 language: - iso: eng month: '01' oa: 1 oa_version: Published Version page: 254-267 project: - _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c call_identifier: H2020 grant_number: '101034413' name: 'IST-BRIDGE: International postdoctoral program' publication: Journal of Combinatorial Theory Series B publication_identifier: eissn: - 1096-0902 issn: - 0095-8956 publication_status: published publisher: Elsevier quality_controlled: '1' scopus_import: '1' status: public title: The Hamilton space of pseudorandom graphs tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 176 year: '2026' ... --- OA_place: publisher OA_type: hybrid PlanS_conform: '1' _id: '20482' 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.' 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." article_number: '104235' article_processing_charge: Yes (via OA deal) article_type: original arxiv: 1 author: - first_name: Simona full_name: Boyadzhiyska, Simona last_name: Boyadzhiyska - first_name: Shagnik full_name: Das, Shagnik last_name: Das - first_name: Thomas full_name: Lesgourgues, Thomas last_name: Lesgourgues - first_name: Kalina H full_name: Petrova, Kalina H id: 554ff4e4-f325-11ee-b0c4-a10dbd523381 last_name: Petrova citation: ama: Boyadzhiyska S, Das S, Lesgourgues T, Petrova KH. Odd-Ramsey numbers of complete bipartite graphs. European Journal of Combinatorics. 2026;131. doi:10.1016/j.ejc.2025.104235 apa: Boyadzhiyska, S., Das, S., Lesgourgues, T., & Petrova, K. H. (2026). Odd-Ramsey numbers of complete bipartite graphs. European Journal of Combinatorics. Elsevier. https://doi.org/10.1016/j.ejc.2025.104235 chicago: Boyadzhiyska, Simona, Shagnik Das, Thomas Lesgourgues, and Kalina H Petrova. “Odd-Ramsey Numbers of Complete Bipartite Graphs.” European Journal of Combinatorics. Elsevier, 2026. https://doi.org/10.1016/j.ejc.2025.104235. ieee: S. Boyadzhiyska, S. Das, T. Lesgourgues, and K. H. Petrova, “Odd-Ramsey numbers of complete bipartite graphs,” European Journal of Combinatorics, vol. 131. Elsevier, 2026. ista: Boyadzhiyska S, Das S, Lesgourgues T, Petrova KH. 2026. Odd-Ramsey numbers of complete bipartite graphs. European Journal of Combinatorics. 131, 104235. mla: Boyadzhiyska, Simona, et al. “Odd-Ramsey Numbers of Complete Bipartite Graphs.” European Journal of Combinatorics, vol. 131, 104235, Elsevier, 2026, doi:10.1016/j.ejc.2025.104235. short: S. Boyadzhiyska, S. Das, T. Lesgourgues, K.H. Petrova, European Journal of Combinatorics 131 (2026). corr_author: '1' date_created: 2025-10-16T13:14:34Z date_published: 2026-01-01T00:00:00Z date_updated: 2026-01-05T13:34:48Z day: '01' ddc: - '500' department: - _id: MaKw doi: 10.1016/j.ejc.2025.104235 ec_funded: 1 external_id: arxiv: - '2410.05887' isi: - '001573380700001' file: - access_level: open_access checksum: 52883daa217398396cbf9b8ad9ddae92 content_type: application/pdf creator: dernst date_created: 2026-01-05T13:34:40Z date_updated: 2026-01-05T13:34:40Z file_id: '20954' file_name: 2026_EuropJourCombinatorics_Boyadzhiyska.pdf file_size: 563029 relation: main_file success: 1 file_date_updated: 2026-01-05T13:34:40Z fulldoi: https://doi.org/10.1016/j.ejc.2025.104235 has_accepted_license: '1' intvolume: ' 131' isi: 1 language: - iso: eng month: '01' oa: 1 oa_version: Published Version project: - _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c call_identifier: H2020 grant_number: '101034413' name: 'IST-BRIDGE: International postdoctoral program' publication: European Journal of Combinatorics publication_identifier: issn: - 0195-6698 publication_status: published publisher: Elsevier quality_controlled: '1' scopus_import: '1' status: public title: Odd-Ramsey numbers of complete bipartite graphs tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 131 year: '2026' ... --- OA_place: publisher OA_type: hybrid PlanS_conform: '1' _id: '22147' abstract: - lang: eng text: "Let 1 ≤ k ≤ n and M be a random n × n matrix with independent uniformly random {±1}-entries. We\r\nshow that there exists an absolute constant c > 0 such that\r\nP[rank(M) ≤ n − k] ≤ exp(−cnk).\r\nThis confirms a well-known prediction in the area, extending a result of Rudelson (who previously\r\nproved this same result under the restriction k ≤ √n, via different methods)." acknowledgement: "Z.H. was supported by SNSF grant 200021-228014. M.K. was supported by ERC Starting Grant “RANDSTRUCT” No. 101076777. L.S. was supported by the Deutsche Forschungsgemeinschaft (DFG, German\r\nResearch Foundation)—CRC 1720–539309657. This research was conducted during the period M.S. served\r\nas a Clay Research Fellow. This work began when the authors were visiting Mathematisches Forschungsinstitut Oberwolfach, which\r\nprovided ideal working conditions. M.S. thanks Vishesh Jain for initial discussions regarding the problem.\r\nWe also thank the anonymous referee for helpful comments." article_number: rnag126 article_processing_charge: Yes (via OA deal) article_type: original arxiv: 1 author: - first_name: Zach full_name: Hunter, Zach last_name: Hunter - first_name: Matthew Alan full_name: Kwan, Matthew Alan id: 5fca0887-a1db-11eb-95d1-ca9d5e0453b3 last_name: Kwan orcid: 0000-0002-4003-7567 - first_name: Lisa full_name: Sauermann, Lisa last_name: Sauermann - first_name: Mehtaab full_name: Sawhney, Mehtaab last_name: Sawhney citation: ama: Hunter Z, Kwan MA, Sauermann L, Sawhney M. On random matrices with large corank. International Mathematics Research Notices. 2026;2026(12). doi:10.1093/imrn/rnag126 apa: Hunter, Z., Kwan, M. A., Sauermann, L., & Sawhney, M. (2026). On random matrices with large corank. International Mathematics Research Notices. Oxford University Press. https://doi.org/10.1093/imrn/rnag126 chicago: Hunter, Zach, Matthew Alan Kwan, Lisa Sauermann, and Mehtaab Sawhney. “On Random Matrices with Large Corank.” International Mathematics Research Notices. Oxford University Press, 2026. https://doi.org/10.1093/imrn/rnag126. ieee: Z. Hunter, M. A. Kwan, L. Sauermann, and M. Sawhney, “On random matrices with large corank,” International Mathematics Research Notices, vol. 2026, no. 12. Oxford University Press, 2026. ista: Hunter Z, Kwan MA, Sauermann L, Sawhney M. 2026. On random matrices with large corank. International Mathematics Research Notices. 2026(12), rnag126. mla: Hunter, Zach, et al. “On Random Matrices with Large Corank.” International Mathematics Research Notices, vol. 2026, no. 12, rnag126, Oxford University Press, 2026, doi:10.1093/imrn/rnag126. short: Z. Hunter, M.A. Kwan, L. Sauermann, M. Sawhney, International Mathematics Research Notices 2026 (2026). corr_author: '1' das_tickbox: '0' date_created: 2026-06-28T22:01:35Z date_published: 2026-06-01T00:00:00Z date_updated: 2026-06-29T09:19:14Z day: '01' ddc: - '500' department: - _id: MaKw doi: 10.1093/imrn/rnag126 external_id: arxiv: - '2510.12933' file: - access_level: open_access checksum: 396b47d0532d7ea509f8cd30f11392a8 content_type: application/pdf creator: dernst date_created: 2026-06-29T09:15:15Z date_updated: 2026-06-29T09:15:15Z file_id: '22151' file_name: 2026_IMRN_Hunter.pdf file_size: 524993 relation: main_file success: 1 file_date_updated: 2026-06-29T09:15:15Z fulldoi: https://doi.org/10.1093/imrn/rnag126 has_accepted_license: '1' intvolume: ' 2026' issue: '12' language: - iso: eng month: '06' oa: 1 oa_version: Published Version project: - _id: bd95085b-d553-11ed-ba76-e55d3349be45 grant_number: '101076777' name: Randomness and structure in combinatorics publication: International Mathematics Research Notices publication_identifier: eissn: - 1687-0247 issn: - 1073-7928 publication_status: published publisher: Oxford University Press quality_controlled: '1' researchdata_availability: no scopus_import: '1' status: public supplementarymaterial: no title: On random matrices with large corank tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 2026 year: '2026' ... --- OA_place: publisher OA_type: hybrid PlanS_conform: '1' _id: '22752' abstract: - lang: eng text: "In this note we outline a new and simple approach to proving central limit theorems for various ‘global’ graph parameters that have robust ‘local’ approximations, using the Efron–Stein inequality, which relies on a combinatorial analysis of the stability of these approximations under resampling an edge. As an application, we give short proofs of a central limit theorem for the order of the giant component and of the \U0001D458\r\n-core for sparse random graphs." acknowledgement: This research was funded in whole or in part by the Austrian Science Fund (FWF) [10.55776/P36131 (Joshua Erde), 10.55776/I6502 (Mihyun Kang), 10.55776/ESP3863424 (Michael Anastos)] and by the Swiss National Science Foundation (SNSF) [P500-2_235474] (Vincent Pfenninger). For open access purposes, the authors have applied a CC BY public copyright license to any author accepted manuscript version arising from this submission. The authors thank the reviewers for helpful comments on the paper, and for bringing the particular form of Theorem 2.2 to our attention. article_number: e70464 article_processing_charge: Yes (in subscription journal) article_type: original arxiv: 1 author: - first_name: Michael full_name: Anastos, Michael id: 0b2a4358-bb35-11ec-b7b9-e3279b593dbb last_name: Anastos - first_name: Joshua full_name: Erde, Joshua last_name: Erde - first_name: Mihyun full_name: Kang, Mihyun last_name: Kang - first_name: Vincent full_name: Pfenninger, Vincent last_name: Pfenninger citation: ama: Anastos M, Erde J, Kang M, Pfenninger V. A short proof of a central limit theorem for the order of the giant component and k-core. Bulletin of the London Mathematical Society. 2026;58(8). doi:10.1112/blms.70464 apa: Anastos, M., Erde, J., Kang, M., & Pfenninger, V. (2026). A short proof of a central limit theorem for the order of the giant component and k-core. Bulletin of the London Mathematical Society. Wiley. https://doi.org/10.1112/blms.70464 chicago: Anastos, Michael, Joshua Erde, Mihyun Kang, and Vincent Pfenninger. “A Short Proof of a Central Limit Theorem for the Order of the Giant Component and K-Core.” Bulletin of the London Mathematical Society. Wiley, 2026. https://doi.org/10.1112/blms.70464. ieee: M. Anastos, J. Erde, M. Kang, and V. Pfenninger, “A short proof of a central limit theorem for the order of the giant component and k-core,” Bulletin of the London Mathematical Society, vol. 58, no. 8. Wiley, 2026. ista: Anastos M, Erde J, Kang M, Pfenninger V. 2026. A short proof of a central limit theorem for the order of the giant component and k-core. Bulletin of the London Mathematical Society. 58(8), e70464. mla: Anastos, Michael, et al. “A Short Proof of a Central Limit Theorem for the Order of the Giant Component and K-Core.” Bulletin of the London Mathematical Society, vol. 58, no. 8, e70464, Wiley, 2026, doi:10.1112/blms.70464. short: M. Anastos, J. Erde, M. Kang, V. Pfenninger, Bulletin of the London Mathematical Society 58 (2026). das_tickbox: '0' date_created: 2026-08-23T22:01:47Z date_published: 2026-08-01T00:00:00Z date_updated: 2026-09-07T13:56:17Z day: '01' ddc: - '510' department: - _id: MaKw doi: 10.1112/blms.70464 external_id: arxiv: - '2506.11651' file: - access_level: open_access checksum: b4b21f05c3fc62fde243a5ddd46cef49 content_type: application/pdf creator: dernst date_created: 2026-09-07T13:53:26Z date_updated: 2026-09-07T13:53:26Z file_id: '22845' file_name: 2026_BulletinLondonMathSoc_Anastos.pdf file_size: 248641 relation: main_file success: 1 file_date_updated: 2026-09-07T13:53:26Z fulldoi: https://doi.org/10.1112/blms.70464 has_accepted_license: '1' intvolume: ' 58' issue: '8' language: - iso: eng mathsc: - 05C80 - 60F05 month: '08' oa: 1 oa_version: Published Version project: - _id: 8f906bd2-16d5-11f0-9cad-e07be8aa9ac9 grant_number: ESP3863424 name: Combinatorial Optimisation Problems on Sparse Random Graphs publication: Bulletin of the London Mathematical Society publication_identifier: eissn: - 1469-2120 issn: - 0024-6093 publication_status: published publisher: Wiley quality_controlled: '1' researchdata_availability: no scopus_import: '1' status: public supplementarymaterial: no title: A short proof of a central limit theorem for the order of the giant component and k-core tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 58 year: '2026' ... --- OA_place: publisher OA_type: hybrid PlanS_conform: '1' _id: '22813' abstract: - lang: eng text: "Consider a bipartite quantum system, where Alice and Bob jointly possess\r\na pure state |ψ\x02. Using local quantum operations on their respective subsystems, and\r\nunlimited classical communication, Alice and Bob may be able to transform |ψ\x02 into\r\nanother state |φ\x02. Famously, Nielsen’s theorem [28] provides a necessary and sufficient\r\nalgebraic criterion for such a transformation to be possible (namely, the entanglement\r\nspectrum of |φ\x02 should majorise the entanglement spectrum of |ψ\x02). In the paper where\r\nNielsen proved this theorem, he conjectured that in the limit of large dimensionality, for\r\nalmost all pairs of states |ψ\x02, |φ\x02 (according to the natural unitary invariant measure) such\r\na transformation is not possible. That is to say, typical pairs of quantum states |ψ\x02, |φ\x02\r\nare entangled in fundamentally different ways, that cannot be converted to each other via\r\nlocal operations and classical communication.ViaNielsen’s theorem, this conjecture can\r\nbe equivalently stated as a conjecture about majorisation of spectra of random matrices\r\nfrom the so-called trace-normalised complex Wishart–Laguerre ensemble. Concretely,\r\nlet X and Y be independent n × m random matrices whose entries are i.i.d. standard\r\ncomplex Gaussians; then Nielsen’s conjecture says that the probability that the spectrum\r\nof XX†/ tr(XX†) majorises the spectrum of YY†/ tr(YY†) tends to zero as both n and\r\nm grow large. We prove this conjecture, and we also confirm some related predictions\r\nof Cunden et al. [12]." acknowledgement: Open access funding provided by Institute of Science and Technology (IST Austria). Vishesh Jain was partially supported by NSF CAREER award DMS-2237646. Matthew Kwan was supported by ERC Starting Grant “RANDSTRUCT” No. 101076777. Marcus Michelen was supported in part by NSF grants DMS-2137623 and DMS-2246624. article_number: '214' article_processing_charge: Yes (via OA deal) article_type: original arxiv: 1 author: - first_name: Vishesh full_name: Jain, Vishesh last_name: Jain - first_name: Matthew Alan full_name: Kwan, Matthew Alan id: 5fca0887-a1db-11eb-95d1-ca9d5e0453b3 last_name: Kwan orcid: 0000-0002-4003-7567 - first_name: Marcus full_name: Michelen, Marcus last_name: Michelen citation: ama: Jain V, Kwan MA, Michelen M. Entangled states are typically incomparable. Communications in Mathematical Physics. 2026;407(10). doi:10.1007/s00220-026-05711-4 apa: Jain, V., Kwan, M. A., & Michelen, M. (2026). Entangled states are typically incomparable. Communications in Mathematical Physics. Springer. https://doi.org/10.1007/s00220-026-05711-4 chicago: Jain, Vishesh, Matthew Alan Kwan, and Marcus Michelen. “Entangled States Are Typically Incomparable.” Communications in Mathematical Physics. Springer, 2026. https://doi.org/10.1007/s00220-026-05711-4. ieee: V. Jain, M. A. Kwan, and M. Michelen, “Entangled states are typically incomparable,” Communications in Mathematical Physics, vol. 407, no. 10. Springer, 2026. ista: Jain V, Kwan MA, Michelen M. 2026. Entangled states are typically incomparable. Communications in Mathematical Physics. 407(10), 214. mla: Jain, Vishesh, et al. “Entangled States Are Typically Incomparable.” Communications in Mathematical Physics, vol. 407, no. 10, 214, Springer, 2026, doi:10.1007/s00220-026-05711-4. short: V. Jain, M.A. Kwan, M. Michelen, Communications in Mathematical Physics 407 (2026). corr_author: '1' das_tickbox: '1' dataavailabilitystatement: No datasets were used in this research. date_created: 2026-09-06T22:01:56Z date_published: 2026-08-28T00:00:00Z date_updated: 2026-09-09T12:35:24Z day: '28' ddc: - '500' department: - _id: MaKw doi: 10.1007/s00220-026-05711-4 external_id: arxiv: - '2406.03335' pmid: - '42668663' file: - access_level: open_access checksum: 61c226b6314a88db25e864e4218d5de3 content_type: application/pdf creator: dernst date_created: 2026-09-09T12:32:53Z date_updated: 2026-09-09T12:32:53Z file_id: '22888' file_name: 2026_CommMathPhysics_Jain.pdf file_size: 463477 relation: main_file success: 1 file_date_updated: 2026-09-09T12:32:53Z fulldoi: https://doi.org/10.1007/s00220-026-05711-4 has_accepted_license: '1' intvolume: ' 407' issue: '10' language: - iso: eng month: '08' oa: 1 oa_version: Published Version pmid: 1 project: - _id: bd95085b-d553-11ed-ba76-e55d3349be45 grant_number: '101076777' name: Randomness and structure in combinatorics publication: Communications in Mathematical Physics publication_identifier: eissn: - 1432-0916 issn: - 0010-3616 publication_status: published publisher: Springer quality_controlled: '1' researchdata_availability: no scopus_import: '1' status: public supplementarymaterial: no title: Entangled states are typically incomparable tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 407 year: '2026' ... --- OA_place: publisher OA_type: hybrid PlanS_conform: '1' _id: '23001' abstract: - lang: eng text: "A famous conjecture by Itai and Zehavi states that, for every \U0001D451\r\n-vertex-connected graph \U0001D43A\r\n and every vertex \U0001D45F\r\n in \U0001D43A\r\n, there are \U0001D451\r\n spanning trees of \U0001D43A\r\n such that, for every vertex \U0001D463\r\n in \U0001D43A ∖{\U0001D45F}\r\n, the paths between \U0001D45F\r\n and \U0001D463\r\n in different trees are internally vertex-disjoint. We show that with high probability the Itai–Zehavi conjecture holds asymptotically for the Erdős–Rényi random graph \U0001D43A⁡(\U0001D45B,\U0001D45D)\r\n when \U0001D45B⁢\U0001D45D =\U0001D714⁡(log⁡\U0001D45B)\r\n and for random regular graphs \U0001D43A⁡(\U0001D45B,\U0001D451)\r\n when \U0001D451 =\U0001D714⁡(log⁡\U0001D45B)\r\n. Moreover, we essentially confirm the conjecture up to a constant factor for sparser random regular graphs. This answers a question of Draganić and Krivelevich positively. Our proof makes use of recent developments on sprinkling techniques in random regular graphs." acknowledgement: "Hollom was supported by the Internal Graduate Studentship of Trinity College, Cambridge. Mond was supported by UK Research and Innovation grant MR/W007320/2. Wang was supported by the ERC Starting Grant “RANDSTRUCT” No. 101076777. Lichev was supported by the Austrian Science Fund (FWF) [10.55776/ESP624]. For open access purposes, the authors have applied a CC BY public copyright license to any author-accepted manuscript version arising from this submission. Open Access funding provided by Technische Universitat Wien.\r\n\r\nPart of this research was done during a visit of the fourth author to IST Austria. We thank IST Austria for its hospitality. We also thank the anonymous referees for their comments and suggestions. Open Access funding provided by Technische Universitat Wien. This work was supported by the European Research Council, UK Research and Innovation, the Austrian Science Fund, and Trinity College." article_number: e70095 article_processing_charge: Yes (via OA deal) article_type: original arxiv: 1 author: - first_name: Lawrence full_name: Hollom, Lawrence last_name: Hollom - first_name: Lyuben full_name: Lichev, Lyuben id: 9aa8388e-d003-11ee-8458-c4c1d7447977 last_name: Lichev - first_name: Adva full_name: Mond, Adva last_name: Mond - first_name: Julien full_name: Portier, Julien last_name: Portier - first_name: Yiting full_name: Wang, Yiting id: 1917d194-076e-11ed-97cd-837255f88785 last_name: Wang citation: ama: Hollom L, Lichev L, Mond A, Portier J, Wang Y. Approximate Itai–Zehavi conjecture for random graphs. Random Structures and Algorithms. 2026;69(2). doi:10.1002/rsa.70095 apa: Hollom, L., Lichev, L., Mond, A., Portier, J., & Wang, Y. (2026). Approximate Itai–Zehavi conjecture for random graphs. Random Structures and Algorithms. Wiley. https://doi.org/10.1002/rsa.70095 chicago: Hollom, Lawrence, Lyuben Lichev, Adva Mond, Julien Portier, and Yiting Wang. “Approximate Itai–Zehavi Conjecture for Random Graphs.” Random Structures and Algorithms. Wiley, 2026. https://doi.org/10.1002/rsa.70095. ieee: L. Hollom, L. Lichev, A. Mond, J. Portier, and Y. Wang, “Approximate Itai–Zehavi conjecture for random graphs,” Random Structures and Algorithms, vol. 69, no. 2. Wiley, 2026. ista: Hollom L, Lichev L, Mond A, Portier J, Wang Y. 2026. Approximate Itai–Zehavi conjecture for random graphs. Random Structures and Algorithms. 69(2), e70095. mla: Hollom, Lawrence, et al. “Approximate Itai–Zehavi Conjecture for Random Graphs.” Random Structures and Algorithms, vol. 69, no. 2, e70095, Wiley, 2026, doi:10.1002/rsa.70095. short: L. Hollom, L. Lichev, A. Mond, J. Portier, Y. Wang, Random Structures and Algorithms 69 (2026). das_tickbox: '0' date_created: 2026-09-27T22:01:52Z date_published: 2026-09-01T00:00:00Z date_updated: 2026-10-07T07:13:30Z day: '01' ddc: - '500' department: - _id: MaKw - _id: GradSch doi: 10.1002/rsa.70095 external_id: arxiv: - '2506.23970' file: - access_level: open_access checksum: 9a786460a47542f24576e947987e558a content_type: application/pdf creator: dernst date_created: 2026-10-07T07:10:43Z date_updated: 2026-10-07T07:10:43Z file_id: '23068' file_name: 2026_RandomStructAlgorithms_Hollom.pdf file_size: 457581 relation: main_file success: 1 file_date_updated: 2026-10-07T07:10:43Z fulldoi: https://doi.org/10.1002/rsa.70095 has_accepted_license: '1' intvolume: ' 69' issue: '2' language: - iso: eng month: '09' oa: 1 oa_version: Published Version project: - _id: bd95085b-d553-11ed-ba76-e55d3349be45 grant_number: '101076777' name: Randomness and structure in combinatorics publication: Random Structures and Algorithms publication_identifier: eissn: - 1098-2418 issn: - 1042-9832 publication_status: published publisher: Wiley quality_controlled: '1' researchdata_availability: no scopus_import: '1' status: public supplementarymaterial: yes title: Approximate Itai–Zehavi conjecture for random graphs tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 69 year: '2026' ... --- OA_place: publisher OA_type: hybrid PlanS_conform: '1' _id: '23123' abstract: - lang: eng text: "How many points can be placed in an \U0001D45B × \U0001D45B grid sothat every (affine) line contains at most \U0001D458 points? Weprove that for \U0001D45B ⩾ \U0001D458 ⩾ 1037 the maximum number ofpoints is exactly \U0001D458\U0001D45B. Our proof builds on the recent workof Kovács, Nagy and Szabó (who proved an analogousresult when \U0001D458 is at least about √\U0001D45B log \U0001D45B), incorporat-ing ideas of Jain and Pham. Using the same approach,we also obtain new bounds for higher-dimensionalextensions of this problem" acknowledgement: We would like to thank Huy Pham for insightful discussions about the proof approach, and wewould like to thank the anonymous referees for their careful reading and helpful comments. Bothauthors are supported by ERC Starting Grant “RANDSTRUCT” No. 101076777.Open Access funding provided by Institute of Science and Technology Austria. article_number: e70510 article_processing_charge: Yes (via OA deal) article_type: original author: - first_name: Aleksandr full_name: Grebennikov, Aleksandr id: 776468ec-50b0-11ef-861e-96ad19e894f3 last_name: Grebennikov - first_name: Matthew Alan full_name: Kwan, Matthew Alan id: 5fca0887-a1db-11eb-95d1-ca9d5e0453b3 last_name: Kwan orcid: 0000-0002-4003-7567 citation: ama: Grebennikov A, Kwan MA. No‐(k+1)‐in‐line problem for large constant k. Bulletin of the London Mathematical Society. 2026;58(10). doi:10.1112/blms.70510 apa: Grebennikov, A., & Kwan, M. A. (2026). No‐(k+1)‐in‐line problem for large constant k. Bulletin of the London Mathematical Society. Wiley. https://doi.org/10.1112/blms.70510 chicago: Grebennikov, Aleksandr, and Matthew Alan Kwan. “No‐(K+1)‐in‐line Problem for Large Constant K.” Bulletin of the London Mathematical Society. Wiley, 2026. https://doi.org/10.1112/blms.70510. ieee: A. Grebennikov and M. A. Kwan, “No‐(k+1)‐in‐line problem for large constant k,” Bulletin of the London Mathematical Society, vol. 58, no. 10. Wiley, 2026. ista: Grebennikov A, Kwan MA. 2026. No‐(k+1)‐in‐line problem for large constant k. Bulletin of the London Mathematical Society. 58(10), e70510. mla: Grebennikov, Aleksandr, and Matthew Alan Kwan. “No‐(K+1)‐in‐line Problem for Large Constant K.” Bulletin of the London Mathematical Society, vol. 58, no. 10, e70510, Wiley, 2026, doi:10.1112/blms.70510. short: A. Grebennikov, M.A. Kwan, Bulletin of the London Mathematical Society 58 (2026). corr_author: '1' das_tickbox: '0' date_created: 2026-10-12T13:57:47Z date_published: 2026-10-01T00:00:00Z date_updated: 2026-10-14T08:41:00Z day: '01' ddc: - '510' department: - _id: MaKw - _id: GradSch doi: 10.1112/blms.70510 file: - access_level: open_access checksum: cce830e3fc66174803b91103f5b88a29 content_type: application/pdf creator: dernst date_created: 2026-10-14T08:37:16Z date_updated: 2026-10-14T08:37:16Z file_id: '23139' file_name: 2026_BulletinLondonMathSoc_Grebennikov.pdf file_size: 284851 relation: main_file success: 1 file_date_updated: 2026-10-14T08:37:16Z fulldoi: https://doi.org/10.1112/blms.70510 has_accepted_license: '1' intvolume: ' 58' issue: '10' language: - iso: eng mathsc: - 05D40 - 52C10 - 52C35 month: '10' oa: 1 oa_version: Published Version project: - _id: bd95085b-d553-11ed-ba76-e55d3349be45 grant_number: '101076777' name: Randomness and structure in combinatorics publication: Bulletin of the London Mathematical Society publication_identifier: eissn: - 1469-2120 issn: - 0024-6093 publication_status: published publisher: Wiley quality_controlled: '1' researchdata_availability: no scopus_import: '1' status: public supplementarymaterial: no title: No‐(k+1)‐in‐line problem for large constant k tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 58 year: '2026' ... --- OA_place: publisher OA_type: hybrid PlanS_conform: '1' _id: '23155' abstract: - lang: eng text: "In this work we establish several monotonicity and decomposition results in the framework of random regular graphs. Among other results, we\r\nshow that, for a wide range of parameters d1 ≤ d2, there exists a coupling of\r\nG(n,d1) and G(n,d2) satisfying that G(n,d1) ⊆ G(n,d2) with high probability, confirming a conjecture of Gao, Isaev and McKay in a new regime.\r\nOur contributions include new tools for analysing contiguity and total variation distance between random regular graph models, a novel procedure for\r\ngenerating unions of random edge-disjoint perfect matchings, and refined estimates of Gao’s bounds on the number of perfect matchings in random regular graphs. In addition, we make progress towards another conjecture of Isaev,\r\nMcKay, Southwell and Zhukovskii." acknowledgement: "We are grateful to Béla Bollobás, to Matthew Kwan and to Fabio\r\nToninelli for their helpful comments and suggestions, and to Nicholas Wormald for useful\r\nremarks on a preliminary version of this work and pointing us towards the reference [29].\r\nThe authors would also like to thank several anonymous referees for many useful suggestions,\r\nincluding pointing out that Lemma 2.10 already appeared in [11].\r\nPart of this research was done during a visit of the fourth author to IST Austria. We thank\r\nIST Austria for its hospitality.\r\nFor open access purposes, the authors have applied a CC BY public copyright license to\r\nany author accepted manuscript version arising from this submission. L. Hollom was supported by the Internal Graduate Studentship of Trinity College, Cambridge.\r\nL. Lichev was supported by the Austrian Science Fund (FWF) grant No. 10.55776/ESP624.\r\nA. Mond was supported by UK Research and Innovation grant MR/W007320/2. Wang was\r\nsupported by the ERC Starting Grant “RANDSTRUCT” No. 101076777." article_processing_charge: Yes (in subscription journal) article_type: original arxiv: 1 author: - first_name: Lawrence full_name: Hollom, Lawrence last_name: Hollom - first_name: Lyuben full_name: Lichev, Lyuben id: 9aa8388e-d003-11ee-8458-c4c1d7447977 last_name: Lichev - first_name: Adva full_name: Mond, Adva last_name: Mond - first_name: Julien full_name: Portier, Julien last_name: Portier - first_name: Yiting full_name: Wang, Yiting id: 1917d194-076e-11ed-97cd-837255f88785 last_name: Wang citation: ama: Hollom L, Lichev L, Mond A, Portier J, Wang Y. Monotonicity and decompositions of random regular graphs. Annals of Applied Probability. 2026;36(5):4716-4738. doi:10.1214/26-AAP2345 apa: Hollom, L., Lichev, L., Mond, A., Portier, J., & Wang, Y. (2026). Monotonicity and decompositions of random regular graphs. Annals of Applied Probability. Institute of Mathematical Statistics. https://doi.org/10.1214/26-AAP2345 chicago: Hollom, Lawrence, Lyuben Lichev, Adva Mond, Julien Portier, and Yiting Wang. “Monotonicity and Decompositions of Random Regular Graphs.” Annals of Applied Probability. Institute of Mathematical Statistics, 2026. https://doi.org/10.1214/26-AAP2345. ieee: L. Hollom, L. Lichev, A. Mond, J. Portier, and Y. Wang, “Monotonicity and decompositions of random regular graphs,” Annals of Applied Probability, vol. 36, no. 5. Institute of Mathematical Statistics, pp. 4716–4738, 2026. ista: Hollom L, Lichev L, Mond A, Portier J, Wang Y. 2026. Monotonicity and decompositions of random regular graphs. Annals of Applied Probability. 36(5), 4716–4738. mla: Hollom, Lawrence, et al. “Monotonicity and Decompositions of Random Regular Graphs.” Annals of Applied Probability, vol. 36, no. 5, Institute of Mathematical Statistics, 2026, pp. 4716–38, doi:10.1214/26-AAP2345. short: L. Hollom, L. Lichev, A. Mond, J. Portier, Y. Wang, Annals of Applied Probability 36 (2026) 4716–4738. das_tickbox: '0' date_created: 2026-10-18T22:01:52Z date_published: 2026-10-01T00:00:00Z date_updated: 2026-10-19T07:39:17Z day: '01' ddc: - '500' department: - _id: MaKw - _id: GradSch doi: 10.1214/26-AAP2345 external_id: arxiv: - '2505.22875' file: - access_level: open_access checksum: 46101e61d29cf40f0a204801d15a848f content_type: application/pdf creator: dernst date_created: 2026-10-19T07:33:58Z date_updated: 2026-10-19T07:33:58Z file_id: '23165' file_name: 2026_AnnalsAppliedProbability_Hollom.pdf file_size: 320593 relation: main_file success: 1 file_date_updated: 2026-10-19T07:33:58Z fulldoi: https://doi.org/10.1214/26-AAP2345 has_accepted_license: '1' intvolume: ' 36' issue: '5' keyword: - Random regular graphs - coupling - contiguity - total variation distance - decomposition language: - iso: eng mathsc: - 05C80 month: '10' oa: 1 oa_version: Published Version page: 4716-4738 project: - _id: bd95085b-d553-11ed-ba76-e55d3349be45 grant_number: '101076777' name: Randomness and structure in combinatorics - _id: e19fef4c-1f3d-11f0-ac04-b8b1af6886d8 grant_number: E624 name: THRESHOLDS IN SEMI-RANDOM PROCESSES AND GRAPH EMBEDDINGS publication: Annals of Applied Probability publication_identifier: eissn: - 2168-8737 issn: - 1050-5164 publication_status: published publisher: Institute of Mathematical Statistics quality_controlled: '1' researchdata_availability: no scopus_import: '1' status: public supplementarymaterial: no title: Monotonicity and decompositions of random regular graphs tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 36 year: '2026' ... --- OA_place: repository OA_type: green _id: '23158' abstract: - lang: eng text: For a tree T and a function f:E(T)→Sd, the imbalance of a subtree T′⊆T is given by |∑e∈E(T′)f(e)|. The d-dimensional discrepancy of the tree T is the minimum, over all functions f as above, of the maximum imbalance of a subtree of T. We prove tight asymptotic bounds for the discrepancy of a tree T, confirming a conjecture of Krishna, Michaeli, Sarantis, Wang and Wang. We also settle a related conjecture on oriented discrepancy of subtrees by the same authors. acknowledgement: The authors would like to thank both Béla Bollobás and the anonymous reviewer for their careful readings of the manuscript and for their valuable comments. The first author was funded by Trinity College, Cambridge. The second author was funded in whole or in part by the Austrian Science Fund (FWF) 10.55776/ESP624. The third author was supported by UK Research and Innovation grant MR/W007320/2. The fourth author was funded by EPSRC (Engineering and Physical Sciences Research Council) and by the Cambridge Commonwealth, European and International Trust. article_processing_charge: No article_type: original arxiv: 1 author: - first_name: Lawrence full_name: Hollom, Lawrence last_name: Hollom - first_name: Lyuben full_name: Lichev, Lyuben id: 9aa8388e-d003-11ee-8458-c4c1d7447977 last_name: Lichev - first_name: Adva full_name: Mond, Adva last_name: Mond - first_name: Julien full_name: Portier, Julien last_name: Portier citation: ama: Hollom L, Lichev L, Mond A, Portier J. A note on high-dimensional discrepancy of subtrees. Discrete and Computational Geometry. 2026. doi:10.1007/s00454-025-00790-x apa: Hollom, L., Lichev, L., Mond, A., & Portier, J. (2026). A note on high-dimensional discrepancy of subtrees. Discrete and Computational Geometry. Springer. https://doi.org/10.1007/s00454-025-00790-x chicago: Hollom, Lawrence, Lyuben Lichev, Adva Mond, and Julien Portier. “A Note on High-Dimensional Discrepancy of Subtrees.” Discrete and Computational Geometry. Springer, 2026. https://doi.org/10.1007/s00454-025-00790-x. ieee: L. Hollom, L. Lichev, A. Mond, and J. Portier, “A note on high-dimensional discrepancy of subtrees,” Discrete and Computational Geometry. Springer, 2026. ista: Hollom L, Lichev L, Mond A, Portier J. 2026. A note on high-dimensional discrepancy of subtrees. Discrete and Computational Geometry. mla: Hollom, Lawrence, et al. “A Note on High-Dimensional Discrepancy of Subtrees.” Discrete and Computational Geometry, Springer, 2026, doi:10.1007/s00454-025-00790-x. short: L. Hollom, L. Lichev, A. Mond, J. Portier, Discrete and Computational Geometry (2026). das_tickbox: '1' dataavailabilitystatement: Data sharing not applicable to this article as no datasets were generated or analysed during the current study. date_created: 2026-10-18T22:01:53Z date_published: 2026-10-09T00:00:00Z date_updated: 2026-10-19T08:20:42Z day: '09' department: - _id: MaKw doi: 10.1007/s00454-025-00790-x external_id: arxiv: - '2412.04170' fulldoi: https://doi.org/10.1007/s00454-025-00790-x keyword: - Trees - High-dimensional discrepancy - Oriented discrepancy language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.48550/arXiv.2412.04170 mathsc: - 05C05 - 05C35 - 11K38 month: '10' oa: 1 oa_version: Preprint project: - _id: e19fef4c-1f3d-11f0-ac04-b8b1af6886d8 grant_number: E624 name: THRESHOLDS IN SEMI-RANDOM PROCESSES AND GRAPH EMBEDDINGS publication: Discrete and Computational Geometry publication_identifier: eissn: - 1432-0444 issn: - 0179-5376 publication_status: epub_ahead publisher: Springer quality_controlled: '1' researchdata_availability: no scopus_import: '1' status: public supplementarymaterial: no title: A note on high-dimensional discrepancy of subtrees type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2026' ... --- OA_place: repository OA_type: green _id: '21211' abstract: - lang: eng text: "We show that, for any graph F and η > 0, there exists a d0 = d0(F, η) such that every nvertex d-regular graph with d ≥ d0 has a collection of vertex-disjoint F-subdivisions covering\r\nat least (1 − η)n vertices. This verifies a conjecture of Verstraëte from 2002 and improves a\r\nrecent result of Letzter, Methuku and Sudakov which additionally required d to be at least\r\npolylogarithmic in n.\r\n" acknowledgement: Supported by the European Research Council (ERC) under the European Union Horizon 2020 research and innovation programme (grant agreement No. 947978). 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. article_number: '2508.00480' article_processing_charge: No arxiv: 1 author: - first_name: Richard full_name: Montgomery, Richard last_name: Montgomery - first_name: Kalina H full_name: Petrova, Kalina H id: 554ff4e4-f325-11ee-b0c4-a10dbd523381 last_name: Petrova - first_name: Arjun full_name: Ranganathan, Arjun last_name: Ranganathan - first_name: Jane full_name: Tan, Jane last_name: Tan citation: ama: Montgomery R, Petrova KH, Ranganathan A, Tan J. Packing subdivisions into regular graphs. arXiv. doi:10.48550/arXiv.2508.00480 apa: Montgomery, R., Petrova, K. H., Ranganathan, A., & Tan, J. (n.d.). Packing subdivisions into regular graphs. arXiv. https://doi.org/10.48550/arXiv.2508.00480 chicago: Montgomery, Richard, Kalina H Petrova, Arjun Ranganathan, and Jane Tan. “Packing Subdivisions into Regular Graphs.” ArXiv, n.d. https://doi.org/10.48550/arXiv.2508.00480. ieee: R. Montgomery, K. H. Petrova, A. Ranganathan, and J. Tan, “Packing subdivisions into regular graphs,” arXiv. . ista: Montgomery R, Petrova KH, Ranganathan A, Tan J. Packing subdivisions into regular graphs. arXiv, 2508.00480. mla: Montgomery, Richard, et al. “Packing Subdivisions into Regular Graphs.” ArXiv, 2508.00480, doi:10.48550/arXiv.2508.00480. short: R. Montgomery, K.H. Petrova, A. Ranganathan, J. Tan, ArXiv (n.d.). date_created: 2026-02-10T11:32:41Z date_published: 2025-08-01T00:00:00Z date_updated: 2026-02-10T11:39:16Z day: '01' department: - _id: MaKw doi: 10.48550/arXiv.2508.00480 ec_funded: 1 external_id: arxiv: - '2508.00480' fulldoi: https://doi.org/10.48550/arXiv.2508.00480 language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.48550/arXiv.2508.00480 month: '08' oa: 1 oa_version: Preprint project: - _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c call_identifier: H2020 grant_number: '101034413' name: 'IST-BRIDGE: International postdoctoral program' publication: arXiv publication_status: submitted status: public title: Packing subdivisions into regular graphs type: preprint user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2025' ... --- OA_place: publisher OA_type: hybrid PlanS_conform: '1' _id: '21706' abstract: - lang: eng text: "Consider a quadratic polynomial Q(ξ1, . . . , ξn) of independent Rademacher random variables ξ1, . . . , ξn. To what extent can Q(ξ1, . . . , ξn) concentrate on a single value? This quadratic version of the classical Littlewood–Offord problem was popularised by Costello, Tao and Vu in their study of symmetric random matrices. In this paper, we obtain an essentially optimal bound for this problem, as conjectured by Nguyen and Vu. Specifically, if Q(ξ1, . . . , ξn) ‘robustly depends on at least m of the ξi’ in the sense that there is no way to pin down the value of Q(ξ1, . . . , ξn) by fixing values for fewer than m of the variables ξi, then we have Pr[Q(ξ1, . . . , ξn) = 0] ≤ O(1/√m). This also implies a similar result in the case where ξ1, . . . , ξn have arbitrary distributions. Our proof combines a number of ideas that may be of independent interest, including an inductive decoupling scheme that reduces quadratic anticoncentration problems\r\nto high-dimensional linear anticoncentration problems. Also, one application of our main result is the resolution of a conjecture of Alon, Hefetz, Krivelevich and Tyomkyn related to graph inducibility. " acknowledgement: We would like to thank the anonymous referee for a number of helpful comments and suggestions. Matthew Kwan was supported by ERC Starting Grant “RANDSTRUCT” No. 101076777. Lisa Sauermann was supported in part by NSF Award DMS-2100157 and a Sloan Research Fellowship, and in part by the DFG Heisenberg Program. article_processing_charge: Yes (via OA deal) article_type: original arxiv: 1 author: - first_name: Matthew Alan full_name: Kwan, Matthew Alan id: 5fca0887-a1db-11eb-95d1-ca9d5e0453b3 last_name: Kwan orcid: 0000-0002-4003-7567 - first_name: Lisa full_name: Sauermann, Lisa last_name: Sauermann citation: ama: Kwan MA, Sauermann L. Resolution of the quadratic Littlewood–Offord problem. Compositio Mathematica. 2025;161(12):3089-3139. doi:10.1112/S0010437X25102789 apa: Kwan, M. A., & Sauermann, L. (2025). Resolution of the quadratic Littlewood–Offord problem. Compositio Mathematica. Cambridge University Press. https://doi.org/10.1112/S0010437X25102789 chicago: Kwan, Matthew Alan, and Lisa Sauermann. “Resolution of the Quadratic Littlewood–Offord Problem.” Compositio Mathematica. Cambridge University Press, 2025. https://doi.org/10.1112/S0010437X25102789. ieee: M. A. Kwan and L. Sauermann, “Resolution of the quadratic Littlewood–Offord problem,” Compositio Mathematica, vol. 161, no. 12. Cambridge University Press, pp. 3089–3139, 2025. ista: Kwan MA, Sauermann L. 2025. Resolution of the quadratic Littlewood–Offord problem. Compositio Mathematica. 161(12), 3089–3139. mla: Kwan, Matthew Alan, and Lisa Sauermann. “Resolution of the Quadratic Littlewood–Offord Problem.” Compositio Mathematica, vol. 161, no. 12, Cambridge University Press, 2025, pp. 3089–139, doi:10.1112/S0010437X25102789. short: M.A. Kwan, L. Sauermann, Compositio Mathematica 161 (2025) 3089–3139. corr_author: '1' date_created: 2026-04-12T22:01:48Z date_published: 2025-12-01T00:00:00Z date_updated: 2026-05-04T09:42:57Z day: '01' ddc: - '510' department: - _id: MaKw doi: 10.1112/S0010437X25102789 external_id: arxiv: - '2312.13826' file: - access_level: open_access checksum: bd3415bb435da9d0b39f6f9a18c61abb content_type: application/pdf creator: dernst date_created: 2026-05-04T09:41:25Z date_updated: 2026-05-04T09:41:25Z file_id: '21787' file_name: 2025_CompositioMath_Kwan.pdf file_size: 858727 relation: main_file success: 1 file_date_updated: 2026-05-04T09:41:25Z fulldoi: https://doi.org/10.1112/S0010437X25102789 has_accepted_license: '1' intvolume: ' 161' issue: '12' language: - iso: eng month: '12' oa: 1 oa_version: Published Version page: 3089-3139 project: - _id: bd95085b-d553-11ed-ba76-e55d3349be45 grant_number: '101076777' name: Randomness and structure in combinatorics publication: Compositio Mathematica publication_identifier: eissn: - 1570-5846 issn: - 0010-437X publication_status: published publisher: Cambridge University Press quality_controlled: '1' scopus_import: '1' status: public title: Resolution of the quadratic Littlewood–Offord problem tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 161 year: '2025' ... --- OA_place: publisher OA_type: hybrid _id: '18478' 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. 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)." article_processing_charge: Yes (in subscription journal) article_type: original arxiv: 1 author: - first_name: Michael full_name: Anastos, Michael id: 0b2a4358-bb35-11ec-b7b9-e3279b593dbb last_name: Anastos - first_name: Simona full_name: Boyadzhiyska, Simona last_name: Boyadzhiyska - first_name: Silas full_name: Rathke, Silas last_name: Rathke - first_name: Juanjo full_name: Rué, Juanjo last_name: Rué citation: ama: Anastos M, Boyadzhiyska S, Rathke S, Rué J. On the chromatic number of powers of subdivisions of graphs. Discrete Applied Mathematics. 2025;360:506-511. doi:10.1016/j.dam.2024.10.002 apa: Anastos, M., Boyadzhiyska, S., Rathke, S., & Rué, J. (2025). On the chromatic number of powers of subdivisions of graphs. Discrete Applied Mathematics. Elsevier. https://doi.org/10.1016/j.dam.2024.10.002 chicago: Anastos, Michael, Simona Boyadzhiyska, Silas Rathke, and Juanjo Rué. “On the Chromatic Number of Powers of Subdivisions of Graphs.” Discrete Applied Mathematics. Elsevier, 2025. https://doi.org/10.1016/j.dam.2024.10.002. ieee: M. Anastos, S. Boyadzhiyska, S. Rathke, and J. Rué, “On the chromatic number of powers of subdivisions of graphs,” Discrete Applied Mathematics, vol. 360. Elsevier, pp. 506–511, 2025. 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. mla: Anastos, Michael, et al. “On the Chromatic Number of Powers of Subdivisions of Graphs.” Discrete Applied Mathematics, vol. 360, Elsevier, 2025, pp. 506–11, doi:10.1016/j.dam.2024.10.002. short: M. Anastos, S. Boyadzhiyska, S. Rathke, J. Rué, Discrete Applied Mathematics 360 (2025) 506–511. corr_author: '1' date_created: 2024-10-27T23:01:44Z date_published: 2025-01-15T00:00:00Z date_updated: 2025-04-14T07:54:56Z day: '15' ddc: - '510' department: - _id: MaKw doi: 10.1016/j.dam.2024.10.002 ec_funded: 1 external_id: arxiv: - '2404.05542' isi: - '001343647000001' file: - access_level: open_access checksum: bd20a13e56b3ea01daf5e7aca5247c60 content_type: application/pdf creator: dernst date_created: 2025-01-13T09:25:59Z date_updated: 2025-01-13T09:25:59Z file_id: '18836' file_name: 2025_DiscreteApplMath_Anastos.pdf file_size: 441060 relation: main_file success: 1 file_date_updated: 2025-01-13T09:25:59Z fulldoi: https://doi.org/10.1016/j.dam.2024.10.002 has_accepted_license: '1' intvolume: ' 360' isi: 1 language: - iso: eng month: '01' oa: 1 oa_version: Published Version page: 506-511 project: - _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c call_identifier: H2020 grant_number: '101034413' name: 'IST-BRIDGE: International postdoctoral program' publication: Discrete Applied Mathematics publication_identifier: issn: - 0166-218X publication_status: published publisher: Elsevier quality_controlled: '1' scopus_import: '1' status: public title: On the chromatic number of powers of subdivisions of graphs tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 360 year: '2025' ... --- OA_place: publisher OA_type: hybrid _id: '19002' abstract: - lang: eng 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." 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. article_number: '114377' article_processing_charge: Yes (via OA deal) article_type: original arxiv: 1 author: - first_name: Pedro P. full_name: Cortés, Pedro P. last_name: Cortés - first_name: Pankaj full_name: Kumar, Pankaj last_name: Kumar - first_name: Benjamin full_name: Moore, Benjamin id: 6dc1a1be-bf1c-11ed-8d2b-d044840f49d6 last_name: Moore - first_name: Patrice full_name: Ossona de Mendez, Patrice last_name: Ossona de Mendez - first_name: Daniel A. full_name: Quiroz, Daniel A. last_name: Quiroz citation: ama: Cortés PP, Kumar P, Moore B, Ossona de Mendez P, Quiroz DA. Subchromatic numbers of powers of graphs with excluded minors. Discrete Mathematics. 2025;348(4). doi:10.1016/j.disc.2024.114377 apa: Cortés, P. P., Kumar, P., Moore, B., Ossona de Mendez, P., & Quiroz, D. A. (2025). Subchromatic numbers of powers of graphs with excluded minors. Discrete Mathematics. Elsevier. https://doi.org/10.1016/j.disc.2024.114377 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.” Discrete Mathematics. Elsevier, 2025. https://doi.org/10.1016/j.disc.2024.114377. 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,” Discrete Mathematics, 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. mla: Cortés, Pedro P., et al. “Subchromatic Numbers of Powers of Graphs with Excluded Minors.” Discrete Mathematics, vol. 348, no. 4, 114377, Elsevier, 2025, doi:10.1016/j.disc.2024.114377. short: P.P. Cortés, P. Kumar, B. Moore, P. Ossona de Mendez, D.A. Quiroz, Discrete Mathematics 348 (2025). corr_author: '1' date_created: 2025-02-05T06:51:08Z date_published: 2025-04-01T00:00:00Z date_updated: 2025-09-30T10:25:15Z day: '01' ddc: - '510' department: - _id: MaKw doi: 10.1016/j.disc.2024.114377 external_id: arxiv: - '2306.02195' isi: - '001401656900001' file: - access_level: open_access checksum: 6723cbb02b6aea0d05f37d167da00c03 content_type: application/pdf creator: dernst date_created: 2025-05-05T12:56:12Z date_updated: 2025-05-05T12:56:12Z file_id: '19657' file_name: 2025_DiscreteMath_Cortes.pdf file_size: 850988 relation: main_file success: 1 file_date_updated: 2025-05-05T12:56:12Z fulldoi: https://doi.org/10.1016/j.disc.2024.114377 has_accepted_license: '1' intvolume: ' 348' isi: 1 issue: '4' language: - iso: eng month: '04' oa: 1 oa_version: Published Version publication: Discrete Mathematics publication_identifier: issn: - 0012-365X publication_status: published publisher: Elsevier quality_controlled: '1' scopus_import: '1' status: public title: Subchromatic numbers of powers of graphs with excluded minors tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: journal_article user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345 volume: 348 year: '2025' ... --- OA_place: publisher OA_type: hybrid _id: '19017' abstract: - lang: eng 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." article_processing_charge: No article_type: original arxiv: 1 author: - first_name: Stefan full_name: Glock, Stefan last_name: Glock - first_name: Jaehoon full_name: Kim, Jaehoon last_name: Kim - first_name: Lyuben full_name: Lichev, Lyuben id: 9aa8388e-d003-11ee-8458-c4c1d7447977 last_name: Lichev - first_name: Oleg full_name: Pikhurko, Oleg last_name: Pikhurko - first_name: Shumin full_name: Sun, Shumin last_name: Sun citation: 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. Canadian Journal of Mathematics. 2025:1-43. doi:10.4153/s0008414x25000021 apa: 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. Cambridge University Press. https://doi.org/10.4153/s0008414x25000021 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.” Canadian Journal of Mathematics. Cambridge University Press, 2025. https://doi.org/10.4153/s0008414x25000021. 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,” Canadian Journal of Mathematics. Cambridge University Press, pp. 1–43, 2025. 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.” Canadian Journal of Mathematics, Cambridge University Press, 2025, pp. 1–43, doi:10.4153/s0008414x25000021. short: S. Glock, J. Kim, L. Lichev, O. Pikhurko, S. Sun, Canadian Journal of Mathematics (2025) 1–43. date_created: 2025-02-10T08:39:46Z date_published: 2025-01-06T00:00:00Z date_updated: 2025-09-30T10:28:07Z day: '06' ddc: - '500' department: - _id: MaKw doi: 10.4153/s0008414x25000021 external_id: arxiv: - '2403.04474' isi: - '001416788600001' fulldoi: https://doi.org/10.4153/s0008414x25000021 has_accepted_license: '1' isi: 1 language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.4153/s0008414x25000021 month: '01' oa: 1 oa_version: Published Version page: 1-43 publication: Canadian Journal of Mathematics publication_identifier: eissn: - 1496-4279 issn: - 0008-414X publication_status: epub_ahead publisher: Cambridge University Press quality_controlled: '1' scopus_import: '1' status: public title: On the (k + 2, k)-problem of Brown, Erdős, and Sós for k = 5,6,7 tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: journal_article user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345 year: '2025' ... --- OA_place: repository OA_type: green _id: '19018' abstract: - lang: eng 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." acknowledgement: We are grateful to Dieter Mitsche for related discussions and to several anonymous referees for multiple useful comments. article_number: '104120' article_processing_charge: No article_type: original arxiv: 1 author: - first_name: Sofiya full_name: Burova, Sofiya last_name: Burova - first_name: Lyuben full_name: Lichev, Lyuben id: 9aa8388e-d003-11ee-8458-c4c1d7447977 last_name: Lichev citation: ama: Burova S, Lichev L. The semi-random tree process. European Journal of Combinatorics. 2025;126. doi:10.1016/j.ejc.2025.104120 apa: Burova, S., & Lichev, L. (2025). The semi-random tree process. European Journal of Combinatorics. Elsevier. https://doi.org/10.1016/j.ejc.2025.104120 chicago: Burova, Sofiya, and Lyuben Lichev. “The Semi-Random Tree Process.” European Journal of Combinatorics. Elsevier, 2025. https://doi.org/10.1016/j.ejc.2025.104120. ieee: S. Burova and L. Lichev, “The semi-random tree process,” European Journal of Combinatorics, vol. 126. Elsevier, 2025. ista: Burova S, Lichev L. 2025. The semi-random tree process. European Journal of Combinatorics. 126, 104120. mla: Burova, Sofiya, and Lyuben Lichev. “The Semi-Random Tree Process.” European Journal of Combinatorics, vol. 126, 104120, Elsevier, 2025, doi:10.1016/j.ejc.2025.104120. short: S. Burova, L. Lichev, European Journal of Combinatorics 126 (2025). date_created: 2025-02-10T09:00:53Z date_published: 2025-05-01T00:00:00Z date_updated: 2025-09-30T10:28:42Z day: '01' department: - _id: MaKw doi: 10.1016/j.ejc.2025.104120 external_id: arxiv: - '2204.07376 ' isi: - '001420659400001' fulldoi: https://doi.org/10.1016/j.ejc.2025.104120 intvolume: ' 126' isi: 1 language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.48550/arXiv.2204.07376 month: '05' oa: 1 oa_version: Preprint publication: European Journal of Combinatorics publication_identifier: issn: - 0195-6698 publication_status: published publisher: Elsevier quality_controlled: '1' scopus_import: '1' status: public title: The semi-random tree process type: journal_article user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345 volume: 126 year: '2025' ... --- OA_place: publisher OA_type: hybrid _id: '19418' 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. 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.' article_number: e70116 article_processing_charge: No article_type: original arxiv: 1 author: - first_name: Nemanja full_name: Draganić, Nemanja last_name: Draganić - first_name: Kalina H full_name: Petrova, Kalina H id: 554ff4e4-f325-11ee-b0c4-a10dbd523381 last_name: Petrova citation: ama: Draganić N, Petrova KH. Size‐Ramsey numbers of graphs with maximum degree three. Journal of the London Mathematical Society. 2025;111(3). doi:10.1112/jlms.70116 apa: Draganić, N., & Petrova, K. H. (2025). Size‐Ramsey numbers of graphs with maximum degree three. Journal of the London Mathematical Society. Wiley. https://doi.org/10.1112/jlms.70116 chicago: Draganić, Nemanja, and Kalina H Petrova. “Size‐Ramsey Numbers of Graphs with Maximum Degree Three.” Journal of the London Mathematical Society. Wiley, 2025. https://doi.org/10.1112/jlms.70116. ieee: N. Draganić and K. H. Petrova, “Size‐Ramsey numbers of graphs with maximum degree three,” Journal of the London Mathematical Society, vol. 111, no. 3. Wiley, 2025. ista: Draganić N, Petrova KH. 2025. Size‐Ramsey numbers of graphs with maximum degree three. Journal of the London Mathematical Society. 111(3), e70116. mla: Draganić, Nemanja, and Kalina H. Petrova. “Size‐Ramsey Numbers of Graphs with Maximum Degree Three.” Journal of the London Mathematical Society, vol. 111, no. 3, e70116, Wiley, 2025, doi:10.1112/jlms.70116. short: N. Draganić, K.H. Petrova, Journal of the London Mathematical Society 111 (2025). date_created: 2025-03-19T09:03:37Z date_published: 2025-03-01T00:00:00Z date_updated: 2025-09-30T11:05:07Z day: '01' ddc: - '510' department: - _id: MaKw doi: 10.1112/jlms.70116 ec_funded: 1 external_id: arxiv: - '2207.05048' isi: - '001450645400019' file: - access_level: open_access checksum: d8e0a03286a44c4f672709e3c829206e content_type: application/pdf creator: dernst date_created: 2025-03-20T09:46:20Z date_updated: 2025-03-20T09:46:20Z file_id: '19427' file_name: 2025_JournLondonMath_Draganic.pdf file_size: 625974 relation: main_file success: 1 file_date_updated: 2025-03-20T09:46:20Z fulldoi: https://doi.org/10.1112/jlms.70116 has_accepted_license: '1' intvolume: ' 111' isi: 1 issue: '3' language: - iso: eng month: '03' oa: 1 oa_version: Published Version project: - _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c call_identifier: H2020 grant_number: '101034413' name: 'IST-BRIDGE: International postdoctoral program' publication: Journal of the London Mathematical Society publication_identifier: eissn: - 1469-7750 issn: - 0024-6107 publication_status: published publisher: Wiley quality_controlled: '1' scopus_import: '1' status: public title: Size‐Ramsey numbers of graphs with maximum degree three tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: journal_article user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345 volume: 111 year: '2025' ... --- OA_place: publisher OA_type: gold _id: '19433' 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. 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. article_number: e55 article_processing_charge: Yes article_type: original arxiv: 1 author: - first_name: Michael full_name: Anastos, Michael id: 0b2a4358-bb35-11ec-b7b9-e3279b593dbb last_name: Anastos - first_name: Zhihan full_name: Jin, Zhihan last_name: Jin - first_name: Matthew Alan full_name: Kwan, Matthew Alan id: 5fca0887-a1db-11eb-95d1-ca9d5e0453b3 last_name: Kwan orcid: 0000-0002-4003-7567 - first_name: Benny full_name: Sudakov, Benny last_name: Sudakov citation: ama: Anastos M, Jin Z, Kwan MA, Sudakov B. Extremal, enumerative and probabilistic results on ordered hypergraph matchings. Forum of Mathematics, Sigma. 2025;13. doi:10.1017/fms.2024.144 apa: Anastos, M., Jin, Z., Kwan, M. A., & Sudakov, B. (2025). Extremal, enumerative and probabilistic results on ordered hypergraph matchings. Forum of Mathematics, Sigma. Cambridge University Press. https://doi.org/10.1017/fms.2024.144 chicago: Anastos, Michael, Zhihan Jin, Matthew Alan Kwan, and Benny Sudakov. “Extremal, Enumerative and Probabilistic Results on Ordered Hypergraph Matchings.” Forum of Mathematics, Sigma. Cambridge University Press, 2025. https://doi.org/10.1017/fms.2024.144. ieee: M. Anastos, Z. Jin, M. A. Kwan, and B. Sudakov, “Extremal, enumerative and probabilistic results on ordered hypergraph matchings,” Forum of Mathematics, Sigma, vol. 13. Cambridge University Press, 2025. ista: Anastos M, Jin Z, Kwan MA, Sudakov B. 2025. Extremal, enumerative and probabilistic results on ordered hypergraph matchings. Forum of Mathematics, Sigma. 13, e55. mla: Anastos, Michael, et al. “Extremal, Enumerative and Probabilistic Results on Ordered Hypergraph Matchings.” Forum of Mathematics, Sigma, vol. 13, e55, Cambridge University Press, 2025, doi:10.1017/fms.2024.144. short: M. Anastos, Z. Jin, M.A. Kwan, B. Sudakov, Forum of Mathematics, Sigma 13 (2025). corr_author: '1' date_created: 2025-03-20T12:59:14Z date_published: 2025-03-14T00:00:00Z date_updated: 2025-09-30T11:18:57Z day: '14' ddc: - '510' department: - _id: MaKw doi: 10.1017/fms.2024.144 ec_funded: 1 external_id: arxiv: - '2308.12268' isi: - '001444429200001' file: - access_level: open_access checksum: f396270ad78c1ed67095c8e5a66fca26 content_type: application/pdf creator: dernst date_created: 2025-04-03T11:24:35Z date_updated: 2025-04-03T11:24:35Z file_id: '19468' file_name: 2025_ForumMathSigma_Anastos.pdf file_size: 630297 relation: main_file success: 1 file_date_updated: 2025-04-03T11:24:35Z fulldoi: https://doi.org/10.1017/fms.2024.144 has_accepted_license: '1' intvolume: ' 13' isi: 1 language: - iso: eng month: '03' oa: 1 oa_version: Published Version project: - _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c call_identifier: H2020 grant_number: '101034413' name: 'IST-BRIDGE: International postdoctoral program' - _id: bd95085b-d553-11ed-ba76-e55d3349be45 grant_number: '101076777' name: Randomness and structure in combinatorics publication: Forum of Mathematics, Sigma publication_identifier: issn: - 2050-5094 publication_status: published publisher: Cambridge University Press quality_controlled: '1' scopus_import: '1' status: public title: Extremal, enumerative and probabilistic results on ordered hypergraph matchings tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: journal_article user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345 volume: 13 year: '2025' ... --- OA_place: publisher OA_type: hybrid _id: '19440' abstract: - lang: eng text: Let μ(G) denote the minimum number of edges whose addition to G results in a Hamiltonian graph, and let μ^(G) denote the minimum number of edges whose addition to G results in a pancyclic graph. We study the distributions of μ(G),μ^(G) in the context of binomial random graphs. Letting d=d(n):=n⋅p, we prove that there exists a function f:R+→[0,1] of order f(d)=12de−d+e−d+O(d6e−3d) such that, if G∼G(n,p) with 20≤d(n)≤0.4logn, then with high probability μ(G)=(1+o(1))⋅f(d)⋅n. Let ni(G) denote the number of degree i vertices in G. A trivial lower bound on μ(G) is given by the expression n0(G)+⌈12n1(G)⌉. In the denser regime of random graphs, we show that if np−13logn−2loglogn→∞ and G∼G(n,p) then, with high probability, μ(G)=n0(G)+⌈12n1(G)⌉. For completion to pancyclicity, we show that if G∼G(n,p) and np≥20 then, with high probability, μ^(G)=μ(G). Finally, we present a polynomial time algorithm such that, if G∼G(n,p) and np≥20, then, with high probability, the algorithm returns a set of edges of size μ(G) whose addition to G results in a pancyclic (and therefore also Hamiltonian) graph. 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. article_number: e21286 article_processing_charge: Yes (in subscription journal) article_type: original arxiv: 1 author: - first_name: Yahav full_name: Alon, Yahav last_name: Alon - first_name: Michael full_name: Anastos, Michael id: 0b2a4358-bb35-11ec-b7b9-e3279b593dbb last_name: Anastos citation: ama: Alon Y, Anastos M. The completion numbers of hamiltonicity and pancyclicity in random graphs. Random Structures and Algorithms. 2025;66(2). doi:10.1002/rsa.21286 apa: Alon, Y., & Anastos, M. (2025). The completion numbers of hamiltonicity and pancyclicity in random graphs. Random Structures and Algorithms. Wiley. https://doi.org/10.1002/rsa.21286 chicago: Alon, Yahav, and Michael Anastos. “The Completion Numbers of Hamiltonicity and Pancyclicity in Random Graphs.” Random Structures and Algorithms. Wiley, 2025. https://doi.org/10.1002/rsa.21286. ieee: Y. Alon and M. Anastos, “The completion numbers of hamiltonicity and pancyclicity in random graphs,” Random Structures and Algorithms, vol. 66, no. 2. Wiley, 2025. ista: Alon Y, Anastos M. 2025. The completion numbers of hamiltonicity and pancyclicity in random graphs. Random Structures and Algorithms. 66(2), e21286. mla: Alon, Yahav, and Michael Anastos. “The Completion Numbers of Hamiltonicity and Pancyclicity in Random Graphs.” Random Structures and Algorithms, vol. 66, no. 2, e21286, Wiley, 2025, doi:10.1002/rsa.21286. short: Y. Alon, M. Anastos, Random Structures and Algorithms 66 (2025). date_created: 2025-03-23T23:01:26Z date_published: 2025-03-01T00:00:00Z date_updated: 2025-09-30T11:15:41Z day: '01' ddc: - '510' department: - _id: MaKw doi: 10.1002/rsa.21286 ec_funded: 1 external_id: arxiv: - '2304.03710' isi: - '001420226800001' file: - access_level: open_access checksum: 6067747e805fa356d560dc45f2a89918 content_type: application/pdf creator: dernst date_created: 2025-03-25T11:46:27Z date_updated: 2025-03-25T11:46:27Z file_id: '19459' file_name: 2025_RandomStruc_Alon.pdf file_size: 549236 relation: main_file success: 1 file_date_updated: 2025-03-25T11:46:27Z fulldoi: https://doi.org/10.1002/rsa.21286 has_accepted_license: '1' intvolume: ' 66' isi: 1 issue: '2' language: - iso: eng license: https://creativecommons.org/licenses/by-nc/4.0/ month: '03' oa: 1 oa_version: Published Version project: - _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c call_identifier: H2020 grant_number: '101034413' name: 'IST-BRIDGE: International postdoctoral program' publication: Random Structures and Algorithms publication_identifier: eissn: - 1098-2418 issn: - 1042-9832 publication_status: published publisher: Wiley quality_controlled: '1' scopus_import: '1' status: public title: The completion numbers of hamiltonicity and pancyclicity in random graphs tmp: image: /images/cc_by_nc.png legal_code_url: https://creativecommons.org/licenses/by-nc/4.0/legalcode name: Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0) short: CC BY-NC (4.0) type: journal_article user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345 volume: 66 year: '2025' ...