[{"date_published":"2024-03-19T00:00:00Z","citation":{"ista":"Campbell R, Hörsch F, Moore B. 2024. Decompositions into two linear forests of bounded lengths. Discrete Mathematics. 347(6), 113962.","apa":"Campbell, R., Hörsch, F., & Moore, B. (2024). Decompositions into two linear forests of bounded lengths. Discrete Mathematics. Elsevier. https://doi.org/10.1016/j.disc.2024.113962","ieee":"R. Campbell, F. Hörsch, and B. Moore, “Decompositions into two linear forests of bounded lengths,” Discrete Mathematics, vol. 347, no. 6. Elsevier, 2024.","ama":"Campbell R, Hörsch F, Moore B. Decompositions into two linear forests of bounded lengths. Discrete Mathematics. 2024;347(6). doi:10.1016/j.disc.2024.113962","chicago":"Campbell, Rutger, Florian Hörsch, and Benjamin Moore. “Decompositions into Two Linear Forests of Bounded Lengths.” Discrete Mathematics. Elsevier, 2024. https://doi.org/10.1016/j.disc.2024.113962.","mla":"Campbell, Rutger, et al. “Decompositions into Two Linear Forests of Bounded Lengths.” Discrete Mathematics, vol. 347, no. 6, 113962, Elsevier, 2024, doi:10.1016/j.disc.2024.113962.","short":"R. Campbell, F. Hörsch, B. Moore, Discrete Mathematics 347 (2024)."},"publication":"Discrete Mathematics","article_type":"original","article_processing_charge":"No","day":"19","scopus_import":"1","oa_version":"Preprint","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"15163","intvolume":" 347","status":"public","title":"Decompositions into two linear forests of bounded lengths","issue":"6","abstract":[{"text":"For some k∈Z≥0∪{∞}, we call a linear forest k-bounded if each of its components has at most k edges. We will say a (k,ℓ)-bounded linear forest decomposition of a graph G is a partition of E(G) into the edge sets of two linear forests Fk,Fℓ where Fk is k-bounded and Fℓ is ℓ-bounded. We show that the problem of deciding whether a given graph has such a decomposition is NP-complete if both k and ℓ are at least 2, NP-complete if k≥9 and ℓ=1, and is in P for (k,ℓ)=(2,1). Before this, the only known NP-complete cases were the (2,2) and (3,3) cases. Our hardness result answers a question of Bermond et al. from 1984. We also show that planar graphs of girth at least nine decompose into a linear forest and a matching, which in particular is stronger than 3-edge-colouring such graphs.","lang":"eng"}],"type":"journal_article","doi":"10.1016/j.disc.2024.113962","language":[{"iso":"eng"}],"oa":1,"main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2301.11615","open_access":"1"}],"external_id":{"arxiv":["2301.11615"]},"quality_controlled":"1","publication_identifier":{"issn":["0012-365X"]},"month":"03","author":[{"full_name":"Campbell, Rutger","last_name":"Campbell","first_name":"Rutger"},{"last_name":"Hörsch","first_name":"Florian","full_name":"Hörsch, Florian"},{"full_name":"Moore, Benjamin","id":"6dc1a1be-bf1c-11ed-8d2b-d044840f49d6","last_name":"Moore","first_name":"Benjamin"}],"volume":347,"date_updated":"2024-03-25T08:09:43Z","date_created":"2024-03-24T23:00:58Z","year":"2024","acknowledgement":"We wish to thank Dániel Marx and András Sebő for making us aware of the results in [8] and some clarifications on them.","department":[{"_id":"MaKw"}],"publisher":"Elsevier","publication_status":"epub_ahead","article_number":"113962"},{"article_number":"P2.21","file_date_updated":"2023-05-22T07:43:19Z","department":[{"_id":"MaKw"}],"publisher":"Electronic Journal of Combinatorics","publication_status":"published","year":"2023","acknowledgement":"We would like to thank the reviewers for their helpful comments and remarks.","volume":30,"date_updated":"2023-08-01T14:44:52Z","date_created":"2023-05-21T22:01:05Z","author":[{"id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb","first_name":"Michael","last_name":"Anastos","full_name":"Anastos, Michael"}],"publication_identifier":{"eissn":["1077-8926"]},"month":"05","isi":1,"quality_controlled":"1","external_id":{"arxiv":["2105.13828"],"isi":["000988285500001"]},"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"language":[{"iso":"eng"}],"doi":"10.37236/11471","type":"journal_article","issue":"2","abstract":[{"text":"Let Lc,n denote the size of the longest cycle in G(n, c/n),c >1 constant. We show that there exists a continuous function f(c) such that Lc,n/n→f(c) a.s. for c>20, thus extending a result of Frieze and the author to smaller values of c. Thereafter, for c>20, we determine the limit of the probability that G(n, c/n)contains cycles of every length between the length of its shortest and its longest cycles as n→∞.","lang":"eng"}],"intvolume":" 30","ddc":["510"],"title":"A note on long cycles in sparse random graphs","status":"public","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","_id":"13042","oa_version":"Published Version","file":[{"checksum":"6269ed3b3eded6536d3d9d6baad2d5b9","success":1,"date_updated":"2023-05-22T07:43:19Z","date_created":"2023-05-22T07:43:19Z","relation":"main_file","file_id":"13046","content_type":"application/pdf","file_size":448736,"creator":"dernst","access_level":"open_access","file_name":"2023_JourCombinatorics_Anastos.pdf"}],"scopus_import":"1","article_processing_charge":"No","has_accepted_license":"1","day":"05","article_type":"original","citation":{"mla":"Anastos, Michael. “A Note on Long Cycles in Sparse Random Graphs.” Electronic Journal of Combinatorics, vol. 30, no. 2, P2.21, Electronic Journal of Combinatorics, 2023, doi:10.37236/11471.","short":"M. Anastos, Electronic Journal of Combinatorics 30 (2023).","chicago":"Anastos, Michael. “A Note on Long Cycles in Sparse Random Graphs.” Electronic Journal of Combinatorics. Electronic Journal of Combinatorics, 2023. https://doi.org/10.37236/11471.","ama":"Anastos M. A note on long cycles in sparse random graphs. Electronic Journal of Combinatorics. 2023;30(2). doi:10.37236/11471","ista":"Anastos M. 2023. A note on long cycles in sparse random graphs. Electronic Journal of Combinatorics. 30(2), P2.21.","ieee":"M. Anastos, “A note on long cycles in sparse random graphs,” Electronic Journal of Combinatorics, vol. 30, no. 2. Electronic Journal of Combinatorics, 2023.","apa":"Anastos, M. (2023). A note on long cycles in sparse random graphs. Electronic Journal of Combinatorics. Electronic Journal of Combinatorics. https://doi.org/10.37236/11471"},"publication":"Electronic Journal of Combinatorics","date_published":"2023-05-05T00:00:00Z"},{"month":"07","publication_identifier":{"eissn":["1077-8926"]},"doi":"10.37236/11714","language":[{"iso":"eng"}],"tmp":{"short":"CC BY-ND (4.0)","image":"/image/cc_by_nd.png","name":"Creative Commons Attribution-NoDerivatives 4.0 International (CC BY-ND 4.0)","legal_code_url":"https://creativecommons.org/licenses/by-nd/4.0/legalcode"},"external_id":{"arxiv":["2212.03100"]},"oa":1,"quality_controlled":"1","project":[{"call_identifier":"H2020","name":"IST-BRIDGE: International postdoctoral program","grant_number":"101034413","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c"}],"file_date_updated":"2023-09-15T08:02:09Z","ec_funded":1,"license":"https://creativecommons.org/licenses/by-nd/4.0/","article_number":"P3.10","author":[{"last_name":"Anastos","first_name":"Michael","id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb","full_name":"Anastos, Michael"},{"full_name":"Fabian, David","first_name":"David","last_name":"Fabian"},{"full_name":"Müyesser, Alp","last_name":"Müyesser","first_name":"Alp"},{"full_name":"Szabó, Tibor","last_name":"Szabó","first_name":"Tibor"}],"date_updated":"2023-09-15T08:12:30Z","date_created":"2023-09-10T22:01:12Z","volume":30,"acknowledgement":"Anastos has received funding from the European Union’s Horizon 2020 research and in-novation programme under the Marie Sk lodowska-Curie grant agreement No 101034413.Fabian’s research is supported by the Deutsche Forschungsgemeinschaft (DFG, GermanResearch Foundation) Graduiertenkolleg “Facets of Complexity” (GRK 2434).","year":"2023","publication_status":"published","department":[{"_id":"MaKw"}],"publisher":"Electronic Journal of Combinatorics","day":"28","has_accepted_license":"1","article_processing_charge":"Yes","scopus_import":"1","date_published":"2023-07-28T00:00:00Z","publication":"Electronic Journal of Combinatorics","citation":{"ama":"Anastos M, Fabian D, Müyesser A, Szabó T. Splitting matchings and the Ryser-Brualdi-Stein conjecture for multisets. Electronic Journal of Combinatorics. 2023;30(3). doi:10.37236/11714","ieee":"M. Anastos, D. Fabian, A. Müyesser, and T. Szabó, “Splitting matchings and the Ryser-Brualdi-Stein conjecture for multisets,” Electronic Journal of Combinatorics, vol. 30, no. 3. Electronic Journal of Combinatorics, 2023.","apa":"Anastos, M., Fabian, D., Müyesser, A., & Szabó, T. (2023). Splitting matchings and the Ryser-Brualdi-Stein conjecture for multisets. Electronic Journal of Combinatorics. Electronic Journal of Combinatorics. https://doi.org/10.37236/11714","ista":"Anastos M, Fabian D, Müyesser A, Szabó T. 2023. Splitting matchings and the Ryser-Brualdi-Stein conjecture for multisets. Electronic Journal of Combinatorics. 30(3), P3.10.","short":"M. Anastos, D. Fabian, A. Müyesser, T. Szabó, Electronic Journal of Combinatorics 30 (2023).","mla":"Anastos, Michael, et al. “Splitting Matchings and the Ryser-Brualdi-Stein Conjecture for Multisets.” Electronic Journal of Combinatorics, vol. 30, no. 3, P3.10, Electronic Journal of Combinatorics, 2023, doi:10.37236/11714.","chicago":"Anastos, Michael, David Fabian, Alp Müyesser, and Tibor Szabó. “Splitting Matchings and the Ryser-Brualdi-Stein Conjecture for Multisets.” Electronic Journal of Combinatorics. Electronic Journal of Combinatorics, 2023. https://doi.org/10.37236/11714."},"article_type":"original","abstract":[{"lang":"eng","text":"We study multigraphs whose edge-sets are the union of three perfect matchings, M1, M2, and M3. Given such a graph G and any a1; a2; a3 2 N with a1 +a2 +a3 6 n - 2, we show there exists a matching M of G with jM \\ Mij = ai for each i 2 f1; 2; 3g. The bound n - 2 in the theorem is best possible in general. We conjecture however that if G is bipartite, the same result holds with n - 2 replaced by n - 1. We give a construction that shows such a result would be tight. We\r\nalso make a conjecture generalising the Ryser-Brualdi-Stein conjecture with colour\r\nmultiplicities."}],"issue":"3","type":"journal_article","file":[{"content_type":"application/pdf","file_size":247917,"creator":"dernst","file_name":"2023_elecJournCombinatorics_Anastos.pdf","access_level":"open_access","date_created":"2023-09-15T08:02:09Z","date_updated":"2023-09-15T08:02:09Z","checksum":"52c46c8cb329f9aaee9ade01525f317b","success":1,"relation":"main_file","file_id":"14338"}],"oa_version":"Published Version","_id":"14319","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"Splitting matchings and the Ryser-Brualdi-Stein conjecture for multisets","status":"public","ddc":["510"],"intvolume":" 30"},{"date_published":"2023-01-01T00:00:00Z","citation":{"chicago":"Anastos, Michael. “Fast Algorithms for Solving the Hamilton Cycle Problem with High Probability.” In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2023:2286–2323. Society for Industrial and Applied Mathematics, 2023. https://doi.org/10.1137/1.9781611977554.ch88.","mla":"Anastos, Michael. “Fast Algorithms for Solving the Hamilton Cycle Problem with High Probability.” Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, vol. 2023, Society for Industrial and Applied Mathematics, 2023, pp. 2286–323, doi:10.1137/1.9781611977554.ch88.","short":"M. Anastos, in:, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2023, pp. 2286–2323.","ista":"Anastos M. 2023. Fast algorithms for solving the Hamilton cycle problem with high probability. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms vol. 2023, 2286–2323.","ieee":"M. Anastos, “Fast algorithms for solving the Hamilton cycle problem with high probability,” in Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Florence, Italy, 2023, vol. 2023, pp. 2286–2323.","apa":"Anastos, M. (2023). Fast algorithms for solving the Hamilton cycle problem with high probability. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (Vol. 2023, pp. 2286–2323). Florence, Italy: Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611977554.ch88","ama":"Anastos M. Fast algorithms for solving the Hamilton cycle problem with high probability. In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. Vol 2023. Society for Industrial and Applied Mathematics; 2023:2286-2323. doi:10.1137/1.9781611977554.ch88"},"publication":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms","page":"2286-2323","article_processing_charge":"No","day":"01","scopus_import":"1","oa_version":"Preprint","_id":"14344","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","intvolume":" 2023","title":"Fast algorithms for solving the Hamilton cycle problem with high probability","status":"public","abstract":[{"text":"We study the Hamilton cycle problem with input a random graph G ~ G(n,p) in two different settings. In the first one, G is given to us in the form of randomly ordered adjacency lists while in the second one, we are given the adjacency matrix of G. In each of the two settings we derive a deterministic algorithm that w.h.p. either finds a Hamilton cycle or returns a certificate that such a cycle does not exist for p = p(n) ≥ 0. The running times of our algorithms are O(n) and respectively, each being best possible in its own setting.","lang":"eng"}],"type":"conference","doi":"10.1137/1.9781611977554.ch88","conference":{"start_date":"2023-01-22","location":"Florence, Italy","end_date":"2023-01-25","name":"SODA: Symposium on Discrete Algorithms"},"language":[{"iso":"eng"}],"external_id":{"arxiv":["2111.14759"]},"oa":1,"main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2111.14759"}],"quality_controlled":"1","publication_identifier":{"isbn":["9781611977554"]},"month":"01","author":[{"full_name":"Anastos, Michael","first_name":"Michael","last_name":"Anastos","id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb"}],"volume":2023,"date_updated":"2023-09-25T09:13:41Z","date_created":"2023-09-17T22:01:10Z","year":"2023","department":[{"_id":"MaKw"}],"publisher":"Society for Industrial and Applied Mathematics","publication_status":"published"},{"scopus_import":"1","has_accepted_license":"1","article_processing_charge":"Yes (in subscription journal)","day":"01","page":"1035-1055","article_type":"original","citation":{"ista":"Liebenau A, Mattos L, Mendonca dos Santos W, Skokan J. 2023. Asymmetric Ramsey properties of random graphs involving cliques and cycles. Random Structures and Algorithms. 62(4), 1035–1055.","apa":"Liebenau, A., Mattos, L., Mendonca dos Santos, W., & Skokan, J. (2023). Asymmetric Ramsey properties of random graphs involving cliques and cycles. Random Structures and Algorithms. Wiley. https://doi.org/10.1002/rsa.21106","ieee":"A. Liebenau, L. Mattos, W. Mendonca dos Santos, and J. Skokan, “Asymmetric Ramsey properties of random graphs involving cliques and cycles,” Random Structures and Algorithms, vol. 62, no. 4. Wiley, pp. 1035–1055, 2023.","ama":"Liebenau A, Mattos L, Mendonca dos Santos W, Skokan J. Asymmetric Ramsey properties of random graphs involving cliques and cycles. Random Structures and Algorithms. 2023;62(4):1035-1055. doi:10.1002/rsa.21106","chicago":"Liebenau, Anita, Letícia Mattos, Walner Mendonca dos Santos, and Jozef Skokan. “Asymmetric Ramsey Properties of Random Graphs Involving Cliques and Cycles.” Random Structures and Algorithms. Wiley, 2023. https://doi.org/10.1002/rsa.21106.","mla":"Liebenau, Anita, et al. “Asymmetric Ramsey Properties of Random Graphs Involving Cliques and Cycles.” Random Structures and Algorithms, vol. 62, no. 4, Wiley, 2023, pp. 1035–55, doi:10.1002/rsa.21106.","short":"A. Liebenau, L. Mattos, W. Mendonca dos Santos, J. Skokan, Random Structures and Algorithms 62 (2023) 1035–1055."},"publication":"Random Structures and Algorithms","date_published":"2023-07-01T00:00:00Z","type":"journal_article","issue":"4","abstract":[{"lang":"eng","text":"We say that (Formula presented.) if, in every edge coloring (Formula presented.), we can find either a 1-colored copy of (Formula presented.) or a 2-colored copy of (Formula presented.). The well-known states that the threshold for the property (Formula presented.) is equal to (Formula presented.), where (Formula presented.) is given by (Formula presented.) for any pair of graphs (Formula presented.) and (Formula presented.) with (Formula presented.). In this article, we show the 0-statement of the Kohayakawa–Kreuter conjecture for every pair of cycles and cliques. "}],"intvolume":" 62","title":"Asymmetric Ramsey properties of random graphs involving cliques and cycles","ddc":["510"],"status":"public","_id":"11706","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Published Version","file":[{"relation":"main_file","file_id":"14389","checksum":"3a5969d0c512aef01c30f3dc81c6d59b","success":1,"date_created":"2023-10-04T09:37:26Z","date_updated":"2023-10-04T09:37:26Z","access_level":"open_access","file_name":"2023_RandomStructureAlgorithms_Liebenau.pdf","file_size":1362334,"content_type":"application/pdf","creator":"dernst"}],"publication_identifier":{"issn":["1042-9832"],"eissn":["1098-2418"]},"month":"07","quality_controlled":"1","isi":1,"oa":1,"tmp":{"name":"Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)","legal_code_url":"https://creativecommons.org/licenses/by-nc/4.0/legalcode","image":"/images/cc_by_nc.png","short":"CC BY-NC (4.0)"},"external_id":{"isi":["000828530400001"]},"language":[{"iso":"eng"}],"doi":"10.1002/rsa.21106","license":"https://creativecommons.org/licenses/by-nc/4.0/","file_date_updated":"2023-10-04T09:37:26Z","publisher":"Wiley","department":[{"_id":"MaKw"}],"publication_status":"published","acknowledgement":"This work was started at the thematic program GRAPHS@IMPA (January–March 2018), in Rio de Janeiro. We thank IMPA and the organisers for the hospitality and for providing a pleasant research environment. We thank Rob Morris for helpful discussions, and the anonymous referees for their careful reading and many helpful suggestions. Open Access funding enabled and organized by Projekt DEAL.\r\nA. Liebenau was supported by an ARC DECRA Fellowship Grant DE170100789. L. Mattos was supported by CAPES and 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). W. Mendonça was supported by CAPES project 88882.332408/2010-01.","year":"2023","volume":62,"date_created":"2022-07-31T22:01:49Z","date_updated":"2023-10-04T09:38:45Z","author":[{"full_name":"Liebenau, Anita","first_name":"Anita","last_name":"Liebenau"},{"full_name":"Mattos, Letícia","last_name":"Mattos","first_name":"Letícia"},{"id":"12c6bd4d-2cd0-11ec-a0da-e28f42f65ebd","last_name":"Mendonca Dos Santos","first_name":"Walner","full_name":"Mendonca Dos Santos, Walner"},{"full_name":"Skokan, Jozef","last_name":"Skokan","first_name":"Jozef"}]},{"oa_version":"Preprint","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"14444","title":"Substructures in Latin squares","status":"public","intvolume":" 256","abstract":[{"text":"We prove several results about substructures in Latin squares. First, we explain how to adapt our recent work on high-girth Steiner triple systems to the setting of Latin squares, resolving a conjecture of Linial that there exist Latin squares with arbitrarily high girth. As a consequence, we see that the number of order- n Latin squares with no intercalate (i.e., no 2×2 Latin subsquare) is at least (e−9/4n−o(n))n2. Equivalently, P[N=0]≥e−n2/4−o(n2)=e−(1+o(1))EN\r\n , where N is the number of intercalates in a uniformly random order- n Latin square. \r\nIn fact, extending recent work of Kwan, Sah, and Sawhney, we resolve the general large-deviation problem for intercalates in random Latin squares, up to constant factors in the exponent: for any constant 0<δ≤1 we have P[N≤(1−δ)EN]=exp(−Θ(n2)) and for any constant δ>0 we have P[N≥(1+δ)EN]=exp(−Θ(n4/3logn)). \r\nFinally, as an application of some new general tools for studying substructures in random Latin squares, we show that in almost all order- n Latin squares, the number of cuboctahedra (i.e., the number of pairs of possibly degenerate 2×2 submatrices with the same arrangement of symbols) is of order n4, which is the minimum possible. As observed by Gowers and Long, this number can be interpreted as measuring ``how associative'' the quasigroup associated with the Latin square is.","lang":"eng"}],"issue":"2","type":"journal_article","date_published":"2023-09-01T00:00:00Z","publication":"Israel Journal of Mathematics","citation":{"short":"M.A. Kwan, A. Sah, M. Sawhney, M. Simkin, Israel Journal of Mathematics 256 (2023) 363–416.","mla":"Kwan, Matthew Alan, et al. “Substructures in Latin Squares.” Israel Journal of Mathematics, vol. 256, no. 2, Springer Nature, 2023, pp. 363–416, doi:10.1007/s11856-023-2513-9.","chicago":"Kwan, Matthew Alan, Ashwin Sah, Mehtaab Sawhney, and Michael Simkin. “Substructures in Latin Squares.” Israel Journal of Mathematics. Springer Nature, 2023. https://doi.org/10.1007/s11856-023-2513-9.","ama":"Kwan MA, Sah A, Sawhney M, Simkin M. Substructures in Latin squares. Israel Journal of Mathematics. 2023;256(2):363-416. doi:10.1007/s11856-023-2513-9","ieee":"M. A. Kwan, A. Sah, M. Sawhney, and M. Simkin, “Substructures in Latin squares,” Israel Journal of Mathematics, vol. 256, no. 2. Springer Nature, pp. 363–416, 2023.","apa":"Kwan, M. A., Sah, A., Sawhney, M., & Simkin, M. (2023). Substructures in Latin squares. Israel Journal of Mathematics. Springer Nature. https://doi.org/10.1007/s11856-023-2513-9","ista":"Kwan MA, Sah A, Sawhney M, Simkin M. 2023. Substructures in Latin squares. Israel Journal of Mathematics. 256(2), 363–416."},"article_type":"original","page":"363-416","day":"01","article_processing_charge":"Yes (in subscription journal)","scopus_import":"1","author":[{"first_name":"Matthew Alan","last_name":"Kwan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","orcid":"0000-0002-4003-7567","full_name":"Kwan, Matthew Alan"},{"full_name":"Sah, Ashwin","first_name":"Ashwin","last_name":"Sah"},{"first_name":"Mehtaab","last_name":"Sawhney","full_name":"Sawhney, Mehtaab"},{"full_name":"Simkin, Michael","last_name":"Simkin","first_name":"Michael"}],"date_created":"2023-10-22T22:01:14Z","date_updated":"2023-10-31T11:27:30Z","volume":256,"year":"2023","acknowledgement":"Sah and Sawhney were supported by NSF Graduate Research Fellowship Program DGE-1745302. Sah was supported by the PD Soros Fellowship. Simkin was supported by the Center of Mathematical Sciences and Applications at Harvard University.","publication_status":"published","department":[{"_id":"MaKw"}],"publisher":"Springer Nature","doi":"10.1007/s11856-023-2513-9","language":[{"iso":"eng"}],"oa":1,"external_id":{"arxiv":["2202.05088"]},"main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2202.05088","open_access":"1"}],"quality_controlled":"1","month":"09","publication_identifier":{"issn":["0021-2172"],"eissn":["1565-8511"]}},{"oa_version":"Published Version","file":[{"date_updated":"2023-11-07T09:16:23Z","date_created":"2023-11-07T09:16:23Z","checksum":"54b824098d59073cc87a308d458b0a3e","success":1,"relation":"main_file","file_id":"14500","content_type":"application/pdf","file_size":1218719,"creator":"dernst","file_name":"2023_ForumMathematics_Kwan.pdf","access_level":"open_access"}],"status":"public","title":"Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture","ddc":["510"],"intvolume":" 11","_id":"14499","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"text":"An n-vertex graph is called C-Ramsey if it has no clique or independent set of size Clog2n (i.e., if it has near-optimal Ramsey behavior). In this paper, we study edge statistics in Ramsey graphs, in particular obtaining very precise control of the distribution of the number of edges in a random vertex subset of a C-Ramsey graph. This brings together two ongoing lines of research: the study of ‘random-like’ properties of Ramsey graphs and the study of small-ball probability for low-degree polynomials of independent random variables.\r\n\r\nThe proof proceeds via an ‘additive structure’ dichotomy on the degree sequence and involves a wide range of different tools from Fourier analysis, random matrix theory, the theory of Boolean functions, probabilistic combinatorics and low-rank approximation. In particular, a key ingredient is a new sharpened version of the quadratic Carbery–Wright theorem on small-ball probability for polynomials of Gaussians, which we believe is of independent interest. One of the consequences of our result is the resolution of an old conjecture of Erdős and McKay, for which Erdős reiterated in several of his open problem collections and for which he offered one of his notorious monetary prizes.","lang":"eng"}],"type":"journal_article","date_published":"2023-08-24T00:00:00Z","article_type":"original","publication":"Forum of Mathematics, Pi","citation":{"chicago":"Kwan, Matthew Alan, Ashwin Sah, Lisa Sauermann, and Mehtaab Sawhney. “Anticoncentration in Ramsey Graphs and a Proof of the Erdős–McKay Conjecture.” Forum of Mathematics, Pi. Cambridge University Press, 2023. https://doi.org/10.1017/fmp.2023.17.","mla":"Kwan, Matthew Alan, et al. “Anticoncentration in Ramsey Graphs and a Proof of the Erdős–McKay Conjecture.” Forum of Mathematics, Pi, vol. 11, e21, Cambridge University Press, 2023, doi:10.1017/fmp.2023.17.","short":"M.A. Kwan, A. Sah, L. Sauermann, M. Sawhney, Forum of Mathematics, Pi 11 (2023).","ista":"Kwan MA, Sah A, Sauermann L, Sawhney M. 2023. Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture. Forum of Mathematics, Pi. 11, e21.","ieee":"M. A. Kwan, A. Sah, L. Sauermann, and M. Sawhney, “Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture,” Forum of Mathematics, Pi, vol. 11. Cambridge University Press, 2023.","apa":"Kwan, M. A., Sah, A., Sauermann, L., & Sawhney, M. (2023). Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture. Forum of Mathematics, Pi. Cambridge University Press. https://doi.org/10.1017/fmp.2023.17","ama":"Kwan MA, Sah A, Sauermann L, Sawhney M. Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture. Forum of Mathematics, Pi. 2023;11. doi:10.1017/fmp.2023.17"},"day":"24","article_processing_charge":"Yes","has_accepted_license":"1","keyword":["Discrete Mathematics and Combinatorics","Geometry and Topology","Mathematical Physics","Statistics and Probability","Algebra and Number Theory","Analysis"],"scopus_import":"1","date_updated":"2023-11-07T09:18:57Z","date_created":"2023-11-07T09:02:48Z","volume":11,"author":[{"last_name":"Kwan","first_name":"Matthew Alan","orcid":"0000-0002-4003-7567","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","full_name":"Kwan, Matthew Alan"},{"first_name":"Ashwin","last_name":"Sah","full_name":"Sah, Ashwin"},{"full_name":"Sauermann, Lisa","last_name":"Sauermann","first_name":"Lisa"},{"first_name":"Mehtaab","last_name":"Sawhney","full_name":"Sawhney, Mehtaab"}],"publication_status":"published","publisher":"Cambridge University Press","department":[{"_id":"MaKw"}],"year":"2023","acknowledgement":"Kwan was supported for part of this work by ERC Starting Grant ‘RANDSTRUCT’ No. 101076777. Sah and Sawhney were supported by NSF Graduate Research Fellowship Program DGE-2141064. Sah was supported by the PD Soros Fellowship. Sauermann was supported by NSF Award DMS-2100157, and for part of this work by a Sloan Research Fellowship.","file_date_updated":"2023-11-07T09:16:23Z","article_number":"e21","language":[{"iso":"eng"}],"doi":"10.1017/fmp.2023.17","quality_controlled":"1","project":[{"name":"Randomness and structure in combinatorics","_id":"bd95085b-d553-11ed-ba76-e55d3349be45","grant_number":"101076777"}],"external_id":{"arxiv":["2208.02874"]},"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"month":"08","publication_identifier":{"issn":["2050-5086"]}},{"type":"conference","abstract":[{"lang":"eng","text":"Starting with the empty graph on $[n]$, at each round, a set of $K=K(n)$ edges is presented chosen uniformly at random from the ones that have not been presented yet. We are then asked to choose at most one of the presented edges and add it to the current graph. Our goal is to construct a Hamiltonian graph with $(1+o(1))n$ edges within as few rounds as possible. We show that in this process, one can build a Hamiltonian graph of size $(1+o(1))n$ in $(1+o(1))(1+(\\log n)/2K) n$ rounds w.h.p. The case $K=1$ implies that w.h.p. one can build a Hamiltonian graph by choosing $(1+o(1))n$ edges in an online fashion as they appear along the first $(0.5+o(1))n\\log n$ rounds of the random graph process. This answers a question of Frieze, Krivelevich and Michaeli. Observe that the number of rounds is asymptotically optimal as the first $0.5n\\log n$ edges do not span a Hamilton cycle w.h.p. The case $K=\\Theta(\\log n)$ implies that the Hamiltonicity threshold of the corresponding Achlioptas process is at most $(1+o(1))(1+(\\log n)/2K) n$. This matches the $(1-o(1))(1+(\\log n)/2K) n$ lower bound due to Krivelevich, Lubetzky and Sudakov and resolves the problem of determining the Hamiltonicity threshold of the Achlioptas process with $K=\\Theta(\\log n)$. We also show that in the above process one can construct a graph $G$ that spans a matching of size $\\lfloor V(G)/2) \\rfloor$ and $(0.5+o(1))n$ edges within $(1+o(1))(0.5+(\\log n)/2K) n$ rounds w.h.p. Our proof relies on a robust Hamiltonicity property of the strong $4$-core of the binomial random graph which we use as a black-box. This property allows it to absorb paths covering vertices outside the strong $4$-core into a cycle."}],"ddc":["510"],"status":"public","title":"Constructing Hamilton cycles and perfect matchings efficiently","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"14867","file":[{"success":1,"checksum":"fb1d9a1e7389d90ec0e5e76934373cf8","date_created":"2024-01-24T09:34:43Z","date_updated":"2024-01-24T09:34:43Z","file_id":"14881","relation":"main_file","creator":"dernst","content_type":"application/pdf","file_size":464230,"access_level":"open_access","file_name":"2023_Eurocomb_Anastos.pdf"}],"oa_version":"Published Version","article_processing_charge":"No","has_accepted_license":"1","day":"01","page":"36-41","citation":{"ista":"Anastos M. 2023. Constructing Hamilton cycles and perfect matchings efficiently. Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications. EUROCOMB: European Conference on Combinatorics, Graph Theory and Applications, 36–41.","apa":"Anastos, M. (2023). Constructing Hamilton cycles and perfect matchings efficiently. In Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications (pp. 36–41). Prague, Czech Republic: Masaryk University Press. https://doi.org/10.5817/cz.muni.eurocomb23-005","ieee":"M. Anastos, “Constructing Hamilton cycles and perfect matchings efficiently,” in Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications, Prague, Czech Republic, 2023, pp. 36–41.","ama":"Anastos M. Constructing Hamilton cycles and perfect matchings efficiently. In: Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications. Masaryk University Press; 2023:36-41. doi:10.5817/cz.muni.eurocomb23-005","chicago":"Anastos, Michael. “Constructing Hamilton Cycles and Perfect Matchings Efficiently.” In Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications, 36–41. Masaryk University Press, 2023. https://doi.org/10.5817/cz.muni.eurocomb23-005.","mla":"Anastos, Michael. “Constructing Hamilton Cycles and Perfect Matchings Efficiently.” Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications, Masaryk University Press, 2023, pp. 36–41, doi:10.5817/cz.muni.eurocomb23-005.","short":"M. Anastos, in:, Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications, Masaryk University Press, 2023, pp. 36–41."},"publication":"Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications","date_published":"2023-09-01T00:00:00Z","license":"https://creativecommons.org/licenses/by-nc-nd/4.0/","ec_funded":1,"file_date_updated":"2024-01-24T09:34:43Z","publisher":"Masaryk University Press","department":[{"_id":"MaKw"}],"publication_status":"published","acknowledgement":"This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 101034413.\r\n","year":"2023","date_created":"2024-01-22T12:20:15Z","date_updated":"2024-01-24T09:38:44Z","author":[{"full_name":"Anastos, Michael","last_name":"Anastos","first_name":"Michael","id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb"}],"publication_identifier":{"eissn":["2788-3116"]},"month":"09","project":[{"grant_number":"101034413","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","name":"IST-BRIDGE: International postdoctoral program","call_identifier":"H2020"}],"quality_controlled":"1","oa":1,"tmp":{"name":"Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)","legal_code_url":"https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode","short":"CC BY-NC-ND (4.0)","image":"/images/cc_by_nc_nd.png"},"external_id":{"arxiv":["2209.09860"]},"language":[{"iso":"eng"}],"doi":"10.5817/cz.muni.eurocomb23-005","conference":{"start_date":"2023-08-28","location":"Prague, Czech Republic","end_date":"2023-09-01","name":"EUROCOMB: European Conference on Combinatorics, Graph Theory and Applications"}},{"publication_identifier":{"eissn":["1778-3569"],"issn":["1631-073X"]},"month":"02","doi":"10.5802/crmath.423","language":[{"iso":"eng"}],"external_id":{"arxiv":["2112.03788"]},"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"quality_controlled":"1","file_date_updated":"2024-03-25T07:21:52Z","author":[{"last_name":"Kwan","first_name":"Matthew Alan","orcid":"0000-0002-4003-7567","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","full_name":"Kwan, Matthew Alan"},{"last_name":"Sah","first_name":"Ashwin","full_name":"Sah, Ashwin"},{"full_name":"Sawhney, Mehtaab","first_name":"Mehtaab","last_name":"Sawhney"}],"volume":361,"date_updated":"2024-03-25T07:23:15Z","date_created":"2024-03-24T23:01:00Z","acknowledgement":"Sah and Sawhney were supported by NSF Graduate Research Fellowship Program DGE-1745302. Sah was supported by the PD Soros Fellowship.\r\nWe thank Michael Simkin for helpful comments on the manuscript. We thank Zach Hunter for\r\nseveral corrections.","year":"2023","publisher":"Academie des Sciences","department":[{"_id":"MaKw"}],"publication_status":"published","has_accepted_license":"1","article_processing_charge":"Yes","day":"01","scopus_import":"1","date_published":"2023-02-01T00:00:00Z","citation":{"apa":"Kwan, M. A., Sah, A., & Sawhney, M. (2023). Enumerating matroids and linear spaces. Comptes Rendus Mathematique. Academie des Sciences. https://doi.org/10.5802/crmath.423","ieee":"M. A. Kwan, A. Sah, and M. Sawhney, “Enumerating matroids and linear spaces,” Comptes Rendus Mathematique, vol. 361, no. G2. Academie des Sciences, pp. 565–575, 2023.","ista":"Kwan MA, Sah A, Sawhney M. 2023. Enumerating matroids and linear spaces. Comptes Rendus Mathematique. 361(G2), 565–575.","ama":"Kwan MA, Sah A, Sawhney M. Enumerating matroids and linear spaces. Comptes Rendus Mathematique. 2023;361(G2):565-575. doi:10.5802/crmath.423","chicago":"Kwan, Matthew Alan, Ashwin Sah, and Mehtaab Sawhney. “Enumerating Matroids and Linear Spaces.” Comptes Rendus Mathematique. Academie des Sciences, 2023. https://doi.org/10.5802/crmath.423.","short":"M.A. Kwan, A. Sah, M. Sawhney, Comptes Rendus Mathematique 361 (2023) 565–575.","mla":"Kwan, Matthew Alan, et al. “Enumerating Matroids and Linear Spaces.” Comptes Rendus Mathematique, vol. 361, no. G2, Academie des Sciences, 2023, pp. 565–75, doi:10.5802/crmath.423."},"publication":"Comptes Rendus Mathematique","page":"565-575","article_type":"original","issue":"G2","abstract":[{"text":"We show that the number of linear spaces on a set of n points and the number of rank-3 matroids on a ground set of size n are both of the form (cn+o(n))n2/6, where c=e3√/2−3(1+3–√)/2. This is the final piece of the puzzle for enumerating fixed-rank matroids at this level of accuracy: the numbers of rank-1 and rank-2 matroids on a ground set of size n have exact representations in terms of well-known combinatorial functions, and it was recently proved by van der Hofstad, Pendavingh, and van der Pol that for constant r≥4 there are (e1−rn+o(n))nr−1/r! rank-r matroids on a ground set of size n. In our proof, we introduce a new approach for bounding the number of clique decompositions of a complete graph, using quasirandomness instead of the so-called entropy method that is common in this area.","lang":"eng"}],"type":"journal_article","file":[{"relation":"main_file","file_id":"15174","date_updated":"2024-03-25T07:21:52Z","date_created":"2024-03-25T07:21:52Z","checksum":"d1d0e0a854a79ae95fb66d75d9117a68","success":1,"file_name":"2023_ComptesRendusMath_Kwan.pdf","access_level":"open_access","file_size":598097,"content_type":"application/pdf","creator":"dernst"}],"oa_version":"Published Version","_id":"15173","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","intvolume":" 361","status":"public","title":"Enumerating matroids and linear spaces","ddc":["510"]},{"scopus_import":"1","day":"01","has_accepted_license":"1","article_processing_charge":"No","publication":"Bulletin of the London Mathematical Society","citation":{"ama":"Kwan MA, Sah A, Sawhney M. Large deviations in random latin squares. Bulletin of the London Mathematical Society. 2022;54(4):1420-1438. doi:10.1112/blms.12638","ista":"Kwan MA, Sah A, Sawhney M. 2022. Large deviations in random latin squares. Bulletin of the London Mathematical Society. 54(4), 1420–1438.","ieee":"M. A. Kwan, A. Sah, and M. Sawhney, “Large deviations in random latin squares,” Bulletin of the London Mathematical Society, vol. 54, no. 4. Wiley, pp. 1420–1438, 2022.","apa":"Kwan, M. A., Sah, A., & Sawhney, M. (2022). Large deviations in random latin squares. Bulletin of the London Mathematical Society. Wiley. https://doi.org/10.1112/blms.12638","mla":"Kwan, Matthew Alan, et al. “Large Deviations in Random Latin Squares.” Bulletin of the London Mathematical Society, vol. 54, no. 4, Wiley, 2022, pp. 1420–38, doi:10.1112/blms.12638.","short":"M.A. Kwan, A. Sah, M. Sawhney, Bulletin of the London Mathematical Society 54 (2022) 1420–1438.","chicago":"Kwan, Matthew Alan, Ashwin Sah, and Mehtaab Sawhney. “Large Deviations in Random Latin Squares.” Bulletin of the London Mathematical Society. Wiley, 2022. https://doi.org/10.1112/blms.12638."},"article_type":"original","page":"1420-1438","date_published":"2022-08-01T00:00:00Z","type":"journal_article","abstract":[{"lang":"eng","text":"In this note, we study large deviations of the number 𝐍 of intercalates ( 2×2 combinatorial subsquares which are themselves Latin squares) in a random 𝑛×𝑛 Latin square. In particular, for constant 𝛿>0 we prove that exp(−𝑂(𝑛2log𝑛))⩽Pr(𝐍⩽(1−𝛿)𝑛2/4)⩽exp(−Ω(𝑛2)) and exp(−𝑂(𝑛4/3(log𝑛)))⩽Pr(𝐍⩾(1+𝛿)𝑛2/4)⩽exp(−Ω(𝑛4/3(log𝑛)2/3)) . As a consequence, we deduce that a typical order- 𝑛 Latin square has (1+𝑜(1))𝑛2/4 intercalates, matching a lower bound due to Kwan and Sudakov and resolving an old conjecture of McKay and Wanless."}],"issue":"4","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","_id":"11186","ddc":["510"],"status":"public","title":"Large deviations in random latin squares","intvolume":" 54","file":[{"file_size":233758,"content_type":"application/pdf","creator":"dernst","access_level":"open_access","file_name":"2022_BulletinMathSociety_Kwan.pdf","checksum":"02d74e7ae955ba3c808e2a8aebe6ef98","success":1,"date_updated":"2023-02-03T09:43:38Z","date_created":"2023-02-03T09:43:38Z","relation":"main_file","file_id":"12499"}],"oa_version":"Published Version","month":"08","publication_identifier":{"issn":["0024-6093"],"eissn":["1469-2120"]},"tmp":{"name":"Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)","legal_code_url":"https://creativecommons.org/licenses/by-nc/4.0/legalcode","image":"/images/cc_by_nc.png","short":"CC BY-NC (4.0)"},"external_id":{"isi":["000779920900001"],"arxiv":["2106.11932"]},"oa":1,"isi":1,"quality_controlled":"1","doi":"10.1112/blms.12638","language":[{"iso":"eng"}],"file_date_updated":"2023-02-03T09:43:38Z","year":"2022","acknowledgement":"We thank Zach Hunter for pointing out some important typographical errors. We also thank the referee for several remarks which helped improve the paper substantially.\r\nKwan was supported by NSF grant DMS-1953990. Sah and Sawhney were supported by NSF Graduate Research Fellowship Program DGE-1745302.","publication_status":"published","publisher":"Wiley","department":[{"_id":"MaKw"}],"author":[{"id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","orcid":"0000-0002-4003-7567","first_name":"Matthew Alan","last_name":"Kwan","full_name":"Kwan, Matthew Alan"},{"last_name":"Sah","first_name":"Ashwin","full_name":"Sah, Ashwin"},{"full_name":"Sawhney, Mehtaab","last_name":"Sawhney","first_name":"Mehtaab"}],"date_created":"2022-04-17T22:01:48Z","date_updated":"2023-08-03T06:47:29Z","volume":54},{"title":"List-decodability with large radius for Reed-Solomon codes","status":"public","intvolume":" 2022","_id":"11145","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","oa_version":"Preprint","type":"conference","abstract":[{"text":"List-decodability of Reed-Solomon codes has re-ceived a lot of attention, but the best-possible dependence between the parameters is still not well-understood. In this work, we focus on the case where the list-decoding radius is of the form r=1−ε for ε tending to zero. Our main result states that there exist Reed-Solomon codes with rate Ω(ε) which are (1−ε,O(1/ε) -list-decodable, meaning that any Hamming ball of radius 1−ε contains at most O(1/ε) codewords. This trade-off between rate and list-decoding radius is best-possible for any code with list size less than exponential in the block length. By achieving this trade-off between rate and list-decoding radius we improve a recent result of Guo, Li, Shangguan, Tamo, and Wootters, and resolve the main motivating question of their work. Moreover, while their result requires the field to be exponentially large in the block length, we only need the field size to be polynomially large (and in fact, almost-linear suffices). We deduce our main result from a more general theorem, in which we prove good list-decodability properties of random puncturings of any given code with very large distance.","lang":"eng"}],"page":"720-726","publication":"62nd Annual IEEE Symposium on Foundations of Computer Science","citation":{"short":"A. Ferber, M.A. Kwan, L. Sauermann, in:, 62nd Annual IEEE Symposium on Foundations of Computer Science, IEEE, 2022, pp. 720–726.","mla":"Ferber, Asaf, et al. “List-Decodability with Large Radius for Reed-Solomon Codes.” 62nd Annual IEEE Symposium on Foundations of Computer Science, vol. 2022, IEEE, 2022, pp. 720–26, doi:10.1109/FOCS52979.2021.00075.","chicago":"Ferber, Asaf, Matthew Alan Kwan, and Lisa Sauermann. “List-Decodability with Large Radius for Reed-Solomon Codes.” In 62nd Annual IEEE Symposium on Foundations of Computer Science, 2022:720–26. IEEE, 2022. https://doi.org/10.1109/FOCS52979.2021.00075.","ama":"Ferber A, Kwan MA, Sauermann L. List-decodability with large radius for Reed-Solomon codes. In: 62nd Annual IEEE Symposium on Foundations of Computer Science. Vol 2022. IEEE; 2022:720-726. doi:10.1109/FOCS52979.2021.00075","apa":"Ferber, A., Kwan, M. A., & Sauermann, L. (2022). List-decodability with large radius for Reed-Solomon codes. In 62nd Annual IEEE Symposium on Foundations of Computer Science (Vol. 2022, pp. 720–726). Denver, CO, United States: IEEE. https://doi.org/10.1109/FOCS52979.2021.00075","ieee":"A. Ferber, M. A. Kwan, and L. Sauermann, “List-decodability with large radius for Reed-Solomon codes,” in 62nd Annual IEEE Symposium on Foundations of Computer Science, Denver, CO, United States, 2022, vol. 2022, pp. 720–726.","ista":"Ferber A, Kwan MA, Sauermann L. 2022. List-decodability with large radius for Reed-Solomon codes. 62nd Annual IEEE Symposium on Foundations of Computer Science. FOCS: Symposium on Foundations of Computer Science vol. 2022, 720–726."},"date_published":"2022-02-01T00:00:00Z","scopus_import":"1","day":"01","article_processing_charge":"No","publication_status":"published","department":[{"_id":"MaKw"}],"publisher":"IEEE","year":"2022","date_created":"2022-04-10T22:01:40Z","date_updated":"2023-08-03T06:57:02Z","volume":2022,"author":[{"full_name":"Ferber, Asaf","first_name":"Asaf","last_name":"Ferber"},{"full_name":"Kwan, Matthew Alan","first_name":"Matthew Alan","last_name":"Kwan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","orcid":"0000-0002-4003-7567"},{"last_name":"Sauermann","first_name":"Lisa","full_name":"Sauermann, Lisa"}],"related_material":{"record":[{"status":"public","relation":"later_version","id":"10775"}]},"quality_controlled":"1","isi":1,"oa":1,"external_id":{"arxiv":["2012.10584"],"isi":["000802209600065"]},"main_file_link":[{"url":" https://doi.org/10.48550/arXiv.2012.10584","open_access":"1"}],"language":[{"iso":"eng"}],"conference":{"name":"FOCS: Symposium on Foundations of Computer Science","end_date":"2022-02-10","start_date":"2022-02-07","location":"Denver, CO, United States"},"doi":"10.1109/FOCS52979.2021.00075","month":"02","publication_identifier":{"issn":["0272-5428"],"isbn":["9781665420556"]}},{"month":"06","publication_identifier":{"issn":["0018-9448"],"eissn":["1557-9654"]},"language":[{"iso":"eng"}],"doi":"10.1109/TIT.2022.3148779","isi":1,"quality_controlled":"1","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2012.10584"}],"oa":1,"external_id":{"isi":["000799622500022"],"arxiv":["2012.10584"]},"date_updated":"2023-08-03T06:57:01Z","date_created":"2022-02-20T23:01:34Z","volume":68,"author":[{"first_name":"Asaf","last_name":"Ferber","full_name":"Ferber, Asaf"},{"full_name":"Kwan, Matthew Alan","last_name":"Kwan","first_name":"Matthew Alan","orcid":"0000-0002-4003-7567","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3"},{"first_name":"Lisa","last_name":"Sauermann","full_name":"Sauermann, Lisa"}],"related_material":{"record":[{"id":"11145","relation":"earlier_version","status":"public"}]},"publication_status":"published","department":[{"_id":"MaKw"}],"publisher":"IEEE","year":"2022","acknowledgement":"Research supported by NSF Award DMS-1953990.","day":"01","article_processing_charge":"No","scopus_import":"1","date_published":"2022-06-01T00:00:00Z","article_type":"original","page":"3823-3828","publication":"IEEE Transactions on Information Theory","citation":{"ama":"Ferber A, Kwan MA, Sauermann L. List-decodability with large radius for Reed-Solomon codes. IEEE Transactions on Information Theory. 2022;68(6):3823-3828. doi:10.1109/TIT.2022.3148779","ista":"Ferber A, Kwan MA, Sauermann L. 2022. List-decodability with large radius for Reed-Solomon codes. IEEE Transactions on Information Theory. 68(6), 3823–3828.","ieee":"A. Ferber, M. A. Kwan, and L. Sauermann, “List-decodability with large radius for Reed-Solomon codes,” IEEE Transactions on Information Theory, vol. 68, no. 6. IEEE, pp. 3823–3828, 2022.","apa":"Ferber, A., Kwan, M. A., & Sauermann, L. (2022). List-decodability with large radius for Reed-Solomon codes. IEEE Transactions on Information Theory. IEEE. https://doi.org/10.1109/TIT.2022.3148779","mla":"Ferber, Asaf, et al. “List-Decodability with Large Radius for Reed-Solomon Codes.” IEEE Transactions on Information Theory, vol. 68, no. 6, IEEE, 2022, pp. 3823–28, doi:10.1109/TIT.2022.3148779.","short":"A. Ferber, M.A. Kwan, L. Sauermann, IEEE Transactions on Information Theory 68 (2022) 3823–3828.","chicago":"Ferber, Asaf, Matthew Alan Kwan, and Lisa Sauermann. “List-Decodability with Large Radius for Reed-Solomon Codes.” IEEE Transactions on Information Theory. IEEE, 2022. https://doi.org/10.1109/TIT.2022.3148779."},"abstract":[{"text":"List-decodability of Reed–Solomon codes has received a lot of attention, but the best-possible dependence between the parameters is still not well-understood. In this work, we focus on the case where the list-decoding radius is of the form r = 1-ε for ε tending to zero. Our main result states that there exist Reed–Solomon codes with rate Ω(ε) which are (1 - ε, O(1/ε))-list-decodable, meaning that any Hamming ball of radius 1-ε contains at most O(1/ε) codewords. This trade-off between rate and list-decoding radius is best-possible for any code with list size less than exponential in the block length. By achieving this trade-off between rate and list-decoding radius we improve a recent result of Guo, Li, Shangguan, Tamo, and Wootters, and resolve the main motivating question of their work. Moreover, while their result requires the field to be exponentially large in the block length, we only need the field size to be polynomially large (and in fact, almost-linear suffices). We deduce our main result from a more general theorem, in which we prove good list-decodability properties of random puncturings of any given code with very large distance.","lang":"eng"}],"issue":"6","type":"journal_article","oa_version":"Preprint","status":"public","title":"List-decodability with large radius for Reed-Solomon codes","intvolume":" 68","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","_id":"10775"},{"scopus_import":"1","article_processing_charge":"No","day":"01","page":"4209-4250","article_type":"original","citation":{"mla":"Kwan, Matthew Alan, et al. “Extension Complexity of Low-Dimensional Polytopes.” Transactions of the American Mathematical Society, vol. 375, no. 6, American Mathematical Society, 2022, pp. 4209–50, doi:10.1090/tran/8614.","short":"M.A. Kwan, L. Sauermann, Y. Zhao, Transactions of the American Mathematical Society 375 (2022) 4209–4250.","chicago":"Kwan, Matthew Alan, Lisa Sauermann, and Yufei Zhao. “Extension Complexity of Low-Dimensional Polytopes.” Transactions of the American Mathematical Society. American Mathematical Society, 2022. https://doi.org/10.1090/tran/8614.","ama":"Kwan MA, Sauermann L, Zhao Y. Extension complexity of low-dimensional polytopes. Transactions of the American Mathematical Society. 2022;375(6):4209-4250. doi:10.1090/tran/8614","ista":"Kwan MA, Sauermann L, Zhao Y. 2022. Extension complexity of low-dimensional polytopes. Transactions of the American Mathematical Society. 375(6), 4209–4250.","ieee":"M. A. Kwan, L. Sauermann, and Y. Zhao, “Extension complexity of low-dimensional polytopes,” Transactions of the American Mathematical Society, vol. 375, no. 6. American Mathematical Society, pp. 4209–4250, 2022.","apa":"Kwan, M. A., Sauermann, L., & Zhao, Y. (2022). Extension complexity of low-dimensional polytopes. Transactions of the American Mathematical Society. American Mathematical Society. https://doi.org/10.1090/tran/8614"},"publication":"Transactions of the American Mathematical Society","date_published":"2022-06-01T00:00:00Z","type":"journal_article","issue":"6","abstract":[{"lang":"eng","text":"Sometimes, it is possible to represent a complicated polytope as a projection of a much simpler polytope. To quantify this phenomenon, the extension complexity of a polytope P is defined to be the minimum number of facets of a (possibly higher-dimensional) polytope from which P can be obtained as a (linear) projection. This notion is motivated by its relevance to combinatorial optimisation, and has been studied intensively for various specific polytopes associated with important optimisation problems. In this paper we study extension complexity as a parameter of general polytopes, more specifically considering various families of low-dimensional polytopes. First, we prove that for a fixed dimension d, the extension complexity of a random d-dimensional polytope (obtained as the convex hull of random points in a ball or on a sphere) is typically on the order of the square root of its number of vertices. Second, we prove that any cyclic n-vertex polygon (whose vertices lie on a circle) has extension complexity at most 24√n. This bound is tight up to the constant factor 24. Finally, we show that there exists an no(1)-dimensional polytope with at most n vertices and extension complexity n1−o(1). Our theorems are proved with a range of different techniques, which we hope will be of further interest."}],"intvolume":" 375","status":"public","title":"Extension complexity of low-dimensional polytopes","_id":"11443","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","oa_version":"Preprint","publication_identifier":{"eissn":["1088-6850"],"issn":["0002-9947"]},"month":"06","quality_controlled":"1","isi":1,"oa":1,"main_file_link":[{"url":" https://doi.org/10.48550/arXiv.2006.08836","open_access":"1"}],"external_id":{"isi":["000798461500001"],"arxiv":["2006.08836"]},"language":[{"iso":"eng"}],"doi":"10.1090/tran/8614","department":[{"_id":"MaKw"}],"publisher":"American Mathematical Society","publication_status":"published","acknowledgement":"The research of the first author was supported by SNSF Project 178493 and NSF Award DMS-1953990. The research of the second author supported by NSF Award DMS-1953772.\r\nThe research of the third author was supported by NSF Award DMS-1764176, NSF CAREER Award DMS-2044606, a Sloan Research Fellowship, and the MIT Solomon Buchsbaum Fund. ","year":"2022","volume":375,"date_updated":"2023-08-03T07:17:37Z","date_created":"2022-06-12T22:01:45Z","author":[{"full_name":"Kwan, Matthew Alan","orcid":"0000-0002-4003-7567","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","last_name":"Kwan","first_name":"Matthew Alan"},{"last_name":"Sauermann","first_name":"Lisa","full_name":"Sauermann, Lisa"},{"full_name":"Zhao, Yufei","first_name":"Yufei","last_name":"Zhao"}]},{"date_published":"2022-07-29T00:00:00Z","article_type":"original","publication":"Electronic Journal of Combinatorics","citation":{"chicago":"Cooley, Oliver, Nicola Del Giudice, Mihyun Kang, and Philipp Sprüssel. “Phase Transition in Cohomology Groups of Non-Uniform Random Simplicial Complexes.” Electronic Journal of Combinatorics. Electronic Journal of Combinatorics, 2022. https://doi.org/10.37236/10607.","short":"O. Cooley, N. Del Giudice, M. Kang, P. Sprüssel, Electronic Journal of Combinatorics 29 (2022).","mla":"Cooley, Oliver, et al. “Phase Transition in Cohomology Groups of Non-Uniform Random Simplicial Complexes.” Electronic Journal of Combinatorics, vol. 29, no. 3, P3.27, Electronic Journal of Combinatorics, 2022, doi:10.37236/10607.","ieee":"O. Cooley, N. Del Giudice, M. Kang, and P. Sprüssel, “Phase transition in cohomology groups of non-uniform random simplicial complexes,” Electronic Journal of Combinatorics, vol. 29, no. 3. Electronic Journal of Combinatorics, 2022.","apa":"Cooley, O., Del Giudice, N., Kang, M., & Sprüssel, P. (2022). Phase transition in cohomology groups of non-uniform random simplicial complexes. Electronic Journal of Combinatorics. Electronic Journal of Combinatorics. https://doi.org/10.37236/10607","ista":"Cooley O, Del Giudice N, Kang M, Sprüssel P. 2022. Phase transition in cohomology groups of non-uniform random simplicial complexes. Electronic Journal of Combinatorics. 29(3), P3.27.","ama":"Cooley O, Del Giudice N, Kang M, Sprüssel P. Phase transition in cohomology groups of non-uniform random simplicial complexes. Electronic Journal of Combinatorics. 2022;29(3). doi:10.37236/10607"},"day":"29","has_accepted_license":"1","article_processing_charge":"No","scopus_import":"1","oa_version":"Published Version","file":[{"content_type":"application/pdf","file_size":1768663,"creator":"dernst","file_name":"2022_ElecJournCombinatorics_Cooley.pdf","access_level":"open_access","date_updated":"2022-08-08T06:28:52Z","date_created":"2022-08-08T06:28:52Z","checksum":"057c676dcee70236aa234d4ce6138c69","success":1,"relation":"main_file","file_id":"11742"}],"ddc":["510"],"status":"public","title":"Phase transition in cohomology groups of non-uniform random simplicial complexes","intvolume":" 29","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","_id":"11740","abstract":[{"lang":"eng","text":"We consider a generalised model of a random simplicial complex, which arises from a random hypergraph. Our model is generated by taking the downward-closure of a non-uniform binomial random hypergraph, in which for each k, each set of k+1 vertices forms an edge with some probability pk independently. As a special case, this contains an extensively studied model of a (uniform) random simplicial complex, introduced by Meshulam and Wallach [Random Structures & Algorithms 34 (2009), no. 3, pp. 408–417].\r\nWe consider a higher-dimensional notion of connectedness on this new model according to the vanishing of cohomology groups over an arbitrary abelian group R. We prove that this notion of connectedness displays a phase transition and determine the threshold. We also prove a hitting time result for a natural process interpretation, in which simplices and their downward-closure are added one by one. In addition, we determine the asymptotic behaviour of cohomology groups inside the critical window around the time of the phase transition."}],"issue":"3","type":"journal_article","language":[{"iso":"eng"}],"doi":"10.37236/10607","isi":1,"quality_controlled":"1","tmp":{"short":"CC BY-ND (4.0)","image":"/image/cc_by_nd.png","name":"Creative Commons Attribution-NoDerivatives 4.0 International (CC BY-ND 4.0)","legal_code_url":"https://creativecommons.org/licenses/by-nd/4.0/legalcode"},"oa":1,"external_id":{"arxiv":["2005.07103"],"isi":["000836200300001"]},"month":"07","publication_identifier":{"eissn":["1077-8926"]},"date_updated":"2023-08-03T12:37:54Z","date_created":"2022-08-07T22:01:59Z","volume":29,"author":[{"id":"43f4ddd0-a46b-11ec-8df6-ef3703bd721d","last_name":"Cooley","first_name":"Oliver","full_name":"Cooley, Oliver"},{"last_name":"Del Giudice","first_name":"Nicola","full_name":"Del Giudice, Nicola"},{"full_name":"Kang, Mihyun","last_name":"Kang","first_name":"Mihyun"},{"full_name":"Sprüssel, Philipp","last_name":"Sprüssel","first_name":"Philipp"}],"publication_status":"published","publisher":"Electronic Journal of Combinatorics","department":[{"_id":"MaKw"}],"year":"2022","acknowledgement":"Supported by Austrian Science Fund (FWF): I3747, W1230.","file_date_updated":"2022-08-08T06:28:52Z","article_number":"P3.27"},{"abstract":[{"text":"The k-sample G(k,W) from a graphon W:[0,1]2→[0,1] is the random graph on {1,…,k}, where we sample x1,…,xk∈[0,1] uniformly at random and make each pair {i,j}⊆{1,…,k} an edge with probability W(xi,xj), with all these choices being mutually independent. Let the random variable Xk(W) be the number of edges in G(k,W). Vera T. Sós asked in 2012 whether two graphons U, W are necessarily weakly isomorphic if the random variables Xk(U) and Xk(W) have the same distribution for every integer k≥2. This question when one of the graphons W is a constant function was answered positively by Endre Csóka and independently by Jacob Fox, Tomasz Łuczak and Vera T. Sós. Here we investigate the question when W is a 2-step graphon and prove that the answer is positive for a 3-dimensional family of such graphons. We also present some related results.","lang":"eng"}],"type":"journal_article","oa_version":"Preprint","title":"On a question of Vera T. Sós about size forcing of graphons","status":"public","intvolume":" 168","_id":"12151","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","day":"23","article_processing_charge":"No","keyword":["graphon","k-sample","graphon forcing","graph container"],"scopus_import":"1","date_published":"2022-11-23T00:00:00Z","article_type":"original","page":"1-26","publication":"Acta Mathematica Hungarica","citation":{"ista":"Cooley O, Kang M, Pikhurko O. 2022. On a question of Vera T. Sós about size forcing of graphons. Acta Mathematica Hungarica. 168, 1–26.","ieee":"O. Cooley, M. Kang, and O. Pikhurko, “On a question of Vera T. Sós about size forcing of graphons,” Acta Mathematica Hungarica, vol. 168. Springer Nature, pp. 1–26, 2022.","apa":"Cooley, O., Kang, M., & Pikhurko, O. (2022). On a question of Vera T. Sós about size forcing of graphons. Acta Mathematica Hungarica. Springer Nature. https://doi.org/10.1007/s10474-022-01265-8","ama":"Cooley O, Kang M, Pikhurko O. On a question of Vera T. Sós about size forcing of graphons. Acta Mathematica Hungarica. 2022;168:1-26. doi:10.1007/s10474-022-01265-8","chicago":"Cooley, Oliver, M. Kang, and O. Pikhurko. “On a Question of Vera T. Sós about Size Forcing of Graphons.” Acta Mathematica Hungarica. Springer Nature, 2022. https://doi.org/10.1007/s10474-022-01265-8.","mla":"Cooley, Oliver, et al. “On a Question of Vera T. Sós about Size Forcing of Graphons.” Acta Mathematica Hungarica, vol. 168, Springer Nature, 2022, pp. 1–26, doi:10.1007/s10474-022-01265-8.","short":"O. Cooley, M. Kang, O. Pikhurko, Acta Mathematica Hungarica 168 (2022) 1–26."},"date_created":"2023-01-12T12:07:59Z","date_updated":"2023-08-04T09:02:37Z","volume":168,"author":[{"full_name":"Cooley, Oliver","id":"43f4ddd0-a46b-11ec-8df6-ef3703bd721d","last_name":"Cooley","first_name":"Oliver"},{"full_name":"Kang, M.","first_name":"M.","last_name":"Kang"},{"full_name":"Pikhurko, O.","first_name":"O.","last_name":"Pikhurko"}],"publication_status":"published","publisher":"Springer Nature","department":[{"_id":"MaKw"}],"acknowledgement":"Supported by Austrian Science Fund (FWF) Grant I3747. Supported by ERC Advanced Grant 101020255 and Leverhulme Research Project Grant RPG-2018-424.\r\nAn extended abstract of this paper appeared in the Proceedings of the European Conference\r\non Combinatorics, Graph Theory and Applications (EuroComb 2021), CRM Research Perspectives, Springer.","year":"2022","month":"11","publication_identifier":{"eissn":["1588-2632"],"issn":["0236-5294"]},"language":[{"iso":"eng"}],"doi":"10.1007/s10474-022-01265-8","isi":1,"quality_controlled":"1","external_id":{"arxiv":["2103.09114"],"isi":["000886839900006"]},"oa":1,"main_file_link":[{"open_access":"1","url":" https://doi.org/10.48550/arXiv.2103.09114"}]},{"oa_version":"None","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","_id":"12432","status":"public","title":"Solving the Hamilton cycle problem fast on average","abstract":[{"lang":"eng","text":"We present CertifyHAM, a deterministic algorithm that takes a graph G as input and either finds a Hamilton cycle of G or outputs that such a cycle does not exist. If G ∼ G(n, p) and p ≥\r\n100 log n/n then the expected running time of CertifyHAM is O(n/p) which is best possible. This improves upon previous results due to Gurevich and Shelah, Thomason and Alon, and\r\nKrivelevich, who proved analogous results for p being constant, p ≥ 12n −1/3 and p ≥ 70n\r\n−1/2 respectively."}],"type":"conference","date_published":"2022-12-01T00:00:00Z","citation":{"ama":"Anastos M. Solving the Hamilton cycle problem fast on average. In: 63rd Annual IEEE Symposium on Foundations of Computer Science. Vol 2022-October. Institute of Electrical and Electronics Engineers; 2022:919-930. doi:10.1109/FOCS54457.2022.00091","ista":"Anastos M. 2022. Solving the Hamilton cycle problem fast on average. 63rd Annual IEEE Symposium on Foundations of Computer Science. FOCS: Symposium on Foundations of Computer Science vol. 2022–October, 919–930.","ieee":"M. Anastos, “Solving the Hamilton cycle problem fast on average,” in 63rd Annual IEEE Symposium on Foundations of Computer Science, Denver, CO, United States, 2022, vol. 2022–October, pp. 919–930.","apa":"Anastos, M. (2022). Solving the Hamilton cycle problem fast on average. In 63rd Annual IEEE Symposium on Foundations of Computer Science (Vol. 2022–October, pp. 919–930). Denver, CO, United States: Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/FOCS54457.2022.00091","mla":"Anastos, Michael. “Solving the Hamilton Cycle Problem Fast on Average.” 63rd Annual IEEE Symposium on Foundations of Computer Science, vol. 2022–October, Institute of Electrical and Electronics Engineers, 2022, pp. 919–30, doi:10.1109/FOCS54457.2022.00091.","short":"M. Anastos, in:, 63rd Annual IEEE Symposium on Foundations of Computer Science, Institute of Electrical and Electronics Engineers, 2022, pp. 919–930.","chicago":"Anastos, Michael. “Solving the Hamilton Cycle Problem Fast on Average.” In 63rd Annual IEEE Symposium on Foundations of Computer Science, 2022–October:919–30. Institute of Electrical and Electronics Engineers, 2022. https://doi.org/10.1109/FOCS54457.2022.00091."},"publication":"63rd Annual IEEE Symposium on Foundations of Computer Science","page":"919-930","article_processing_charge":"No","day":"01","scopus_import":"1","author":[{"last_name":"Anastos","first_name":"Michael","id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb","full_name":"Anastos, Michael"}],"volume":"2022-October","date_updated":"2023-08-04T09:37:56Z","date_created":"2023-01-29T23:00:59Z","year":"2022","acknowledgement":"This project has received funding from the European Union’s Horizon 2020\r\nresearch and innovation programme under the Marie Skłodowska-Curie grant\r\nagreement No 101034413","publisher":"Institute of Electrical and Electronics Engineers","department":[{"_id":"MaKw"}],"publication_status":"published","ec_funded":1,"doi":"10.1109/FOCS54457.2022.00091","conference":{"location":"Denver, CO, United States","start_date":"2022-10-31","end_date":"2022-11-03","name":"FOCS: Symposium on Foundations of Computer Science"},"language":[{"iso":"eng"}],"external_id":{"isi":["000909382900084"]},"project":[{"name":"IST-BRIDGE: International postdoctoral program","call_identifier":"H2020","grant_number":"101034413","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c"}],"isi":1,"quality_controlled":"1","publication_identifier":{"isbn":["9781665455190"],"issn":["0272-5428"]},"month":"12"},{"article_processing_charge":"No","has_accepted_license":"1","day":"21","scopus_import":"1","keyword":["Computational Theory and Mathematics","Geometry and Topology","Theoretical Computer Science","Applied Mathematics","Discrete Mathematics and Combinatorics"],"date_published":"2022-10-21T00:00:00Z","citation":{"apa":"Cooley, O., Kang, M., & Zalla, J. (2022). Loose cores and cycles in random hypergraphs. The Electronic Journal of Combinatorics. The Electronic Journal of Combinatorics. https://doi.org/10.37236/10794","ieee":"O. Cooley, M. Kang, and J. Zalla, “Loose cores and cycles in random hypergraphs,” The Electronic Journal of Combinatorics, vol. 29, no. 4. The Electronic Journal of Combinatorics, 2022.","ista":"Cooley O, Kang M, Zalla J. 2022. Loose cores and cycles in random hypergraphs. The Electronic Journal of Combinatorics. 29(4), P4.13.","ama":"Cooley O, Kang M, Zalla J. Loose cores and cycles in random hypergraphs. The Electronic Journal of Combinatorics. 2022;29(4). doi:10.37236/10794","chicago":"Cooley, Oliver, Mihyun Kang, and Julian Zalla. “Loose Cores and Cycles in Random Hypergraphs.” The Electronic Journal of Combinatorics. The Electronic Journal of Combinatorics, 2022. https://doi.org/10.37236/10794.","short":"O. Cooley, M. Kang, J. Zalla, The Electronic Journal of Combinatorics 29 (2022).","mla":"Cooley, Oliver, et al. “Loose Cores and Cycles in Random Hypergraphs.” The Electronic Journal of Combinatorics, vol. 29, no. 4, P4.13, The Electronic Journal of Combinatorics, 2022, doi:10.37236/10794."},"publication":"The Electronic Journal of Combinatorics","article_type":"original","issue":"4","abstract":[{"lang":"eng","text":"Inspired by the study of loose cycles in hypergraphs, we define the loose core in hypergraphs as a structurewhich mirrors the close relationship between cycles and $2$-cores in graphs. We prove that in the $r$-uniform binomial random hypergraph $H^r(n,p)$, the order of the loose core undergoes a phase transition at a certain critical threshold and determine this order, as well as the number of edges, asymptotically in the subcritical and supercritical regimes.
\r\nOur main tool is an algorithm called CoreConstruct, which enables us to analyse a peeling process for the loose core. By analysing this algorithm we determine the asymptotic degree distribution of vertices in the loose core and in particular how many vertices and edges the loose core contains. As a corollary we obtain an improved upper bound on the length of the longest loose cycle in $H^r(n,p)$."}],"type":"journal_article","file":[{"access_level":"open_access","file_name":"2022_ElecJournCombinatorics_Cooley_Kang_Zalla.pdf","content_type":"application/pdf","file_size":626953,"creator":"dernst","relation":"main_file","file_id":"12462","checksum":"00122b2459f09b5ae43073bfba565e94","success":1,"date_created":"2023-01-30T11:45:13Z","date_updated":"2023-01-30T11:45:13Z"}],"oa_version":"Published Version","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","_id":"12286","intvolume":" 29","ddc":["510"],"title":"Loose cores and cycles in random hypergraphs","status":"public","publication_identifier":{"eissn":["1077-8926"]},"month":"10","doi":"10.37236/10794","language":[{"iso":"eng"}],"external_id":{"isi":["000876763300001"]},"tmp":{"short":"CC BY-ND (4.0)","image":"/image/cc_by_nd.png","name":"Creative Commons Attribution-NoDerivatives 4.0 International (CC BY-ND 4.0)","legal_code_url":"https://creativecommons.org/licenses/by-nd/4.0/legalcode"},"oa":1,"isi":1,"quality_controlled":"1","file_date_updated":"2023-01-30T11:45:13Z","article_number":"P4.13","author":[{"id":"43f4ddd0-a46b-11ec-8df6-ef3703bd721d","first_name":"Oliver","last_name":"Cooley","full_name":"Cooley, Oliver"},{"full_name":"Kang, Mihyun","first_name":"Mihyun","last_name":"Kang"},{"full_name":"Zalla, Julian","first_name":"Julian","last_name":"Zalla"}],"volume":29,"date_created":"2023-01-16T10:03:57Z","date_updated":"2023-08-04T10:29:18Z","year":"2022","acknowledgement":"Supported by Austrian Science Fund (FWF): I3747, W1230.","publisher":"The Electronic Journal of Combinatorics","department":[{"_id":"MaKw"}],"publication_status":"published"}]