[{"year":"2026","das_tickbox":"0","intvolume":"        69","file":[{"checksum":"9a786460a47542f24576e947987e558a","file_id":"23068","file_name":"2026_RandomStructAlgorithms_Hollom.pdf","date_updated":"2026-10-07T07:10:43Z","access_level":"open_access","date_created":"2026-10-07T07:10:43Z","success":1,"creator":"dernst","content_type":"application/pdf","relation":"main_file","file_size":457581}],"arxiv":1,"PlanS_conform":"1","researchdata_availability":"no","citation":{"ama":"Hollom L, Lichev L, Mond A, Portier J, Wang Y. Approximate Itai–Zehavi conjecture for random graphs. <i>Random Structures and Algorithms</i>. 2026;69(2). doi:<a href=\"https://doi.org/10.1002/rsa.70095\">10.1002/rsa.70095</a>","mla":"Hollom, Lawrence, et al. “Approximate Itai–Zehavi Conjecture for Random Graphs.” <i>Random Structures and Algorithms</i>, vol. 69, no. 2, e70095, Wiley, 2026, doi:<a href=\"https://doi.org/10.1002/rsa.70095\">10.1002/rsa.70095</a>.","chicago":"Hollom, Lawrence, Lyuben Lichev, Adva Mond, Julien Portier, and Yiting Wang. “Approximate Itai–Zehavi Conjecture for Random Graphs.” <i>Random Structures and Algorithms</i>. Wiley, 2026. <a href=\"https://doi.org/10.1002/rsa.70095\">https://doi.org/10.1002/rsa.70095</a>.","short":"L. Hollom, L. Lichev, A. Mond, J. Portier, Y. Wang, Random Structures and Algorithms 69 (2026).","apa":"Hollom, L., Lichev, L., Mond, A., Portier, J., &#38; Wang, Y. (2026). Approximate Itai–Zehavi conjecture for random graphs. <i>Random Structures and Algorithms</i>. Wiley. <a href=\"https://doi.org/10.1002/rsa.70095\">https://doi.org/10.1002/rsa.70095</a>","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.","ieee":"L. Hollom, L. Lichev, A. Mond, J. Portier, and Y. Wang, “Approximate Itai–Zehavi conjecture for random graphs,” <i>Random Structures and Algorithms</i>, vol. 69, no. 2. Wiley, 2026."},"date_updated":"2026-10-07T07:13:30Z","type":"journal_article","status":"public","doi":"10.1002/rsa.70095","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"date_published":"2026-09-01T00:00:00Z","_id":"23001","article_number":"e70095","issue":"2","volume":69,"oa":1,"title":"Approximate Itai–Zehavi conjecture for random graphs","file_date_updated":"2026-10-07T07:10:43Z","publication_identifier":{"issn":["1042-9832"],"eissn":["1098-2418"]},"OA_type":"hybrid","OA_place":"publisher","external_id":{"arxiv":["2506.23970"]},"abstract":[{"text":"A famous conjecture by Itai and Zehavi states that, for every 𝑑\r\n-vertex-connected graph 𝐺\r\n and every vertex 𝑟\r\n in 𝐺\r\n, there are 𝑑\r\n spanning trees of 𝐺\r\n such that, for every vertex 𝑣\r\n in 𝐺 ∖{𝑟}\r\n, the paths between 𝑟\r\n and 𝑣\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 𝐺⁡(𝑛,𝑝)\r\n when 𝑛⁢𝑝 =𝜔⁡(log⁡𝑛)\r\n and for random regular graphs 𝐺⁡(𝑛,𝑑)\r\n when 𝑑 =𝜔⁡(log⁡𝑛)\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.","lang":"eng"}],"date_created":"2026-09-27T22:01:52Z","license":"https://creativecommons.org/licenses/by/4.0/","author":[{"first_name":"Lawrence","full_name":"Hollom, Lawrence","last_name":"Hollom"},{"id":"9aa8388e-d003-11ee-8458-c4c1d7447977","last_name":"Lichev","first_name":"Lyuben","full_name":"Lichev, Lyuben"},{"last_name":"Mond","first_name":"Adva","full_name":"Mond, Adva"},{"full_name":"Portier, Julien","first_name":"Julien","last_name":"Portier"},{"first_name":"Yiting","full_name":"Wang, Yiting","last_name":"Wang","id":"1917d194-076e-11ed-97cd-837255f88785"}],"has_accepted_license":"1","quality_controlled":"1","fulldoi":"https://doi.org/10.1002/rsa.70095","month":"09","supplementarymaterial":"yes","oa_version":"Published Version","article_processing_charge":"Yes (via OA deal)","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","article_type":"original","language":[{"iso":"eng"}],"ddc":["500"],"publication":"Random Structures and Algorithms","scopus_import":"1","project":[{"grant_number":"101076777","name":"Randomness and structure in combinatorics","_id":"bd95085b-d553-11ed-ba76-e55d3349be45"}],"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.","day":"01","department":[{"_id":"MaKw"},{"_id":"GradSch"}],"publisher":"Wiley"},{"date_created":"2025-03-23T23:01:26Z","license":"https://creativecommons.org/licenses/by-nc/4.0/","author":[{"last_name":"Alon","full_name":"Alon, Yahav","first_name":"Yahav"},{"first_name":"Michael","full_name":"Anastos, Michael","last_name":"Anastos","id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb"}],"has_accepted_license":"1","fulldoi":"https://doi.org/10.1002/rsa.21286","quality_controlled":"1","month":"03","oa_version":"Published Version","article_processing_charge":"Yes (in subscription journal)","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","publication_status":"published","article_type":"original","ddc":["510"],"language":[{"iso":"eng"}],"publication":"Random Structures and Algorithms","scopus_import":"1","isi":1,"project":[{"_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","name":"IST-BRIDGE: International postdoctoral program","grant_number":"101034413","call_identifier":"H2020"}],"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.","day":"01","department":[{"_id":"MaKw"}],"publisher":"Wiley","year":"2025","ec_funded":1,"intvolume":"        66","file":[{"date_updated":"2025-03-25T11:46:27Z","access_level":"open_access","date_created":"2025-03-25T11:46:27Z","checksum":"6067747e805fa356d560dc45f2a89918","file_name":"2025_RandomStruc_Alon.pdf","file_id":"19459","success":1,"creator":"dernst","file_size":549236,"content_type":"application/pdf","relation":"main_file"}],"arxiv":1,"citation":{"chicago":"Alon, Yahav, and Michael Anastos. “The Completion Numbers of Hamiltonicity and Pancyclicity in Random Graphs.” <i>Random Structures and Algorithms</i>. Wiley, 2025. <a href=\"https://doi.org/10.1002/rsa.21286\">https://doi.org/10.1002/rsa.21286</a>.","ama":"Alon Y, Anastos M. The completion numbers of hamiltonicity and pancyclicity in random graphs. <i>Random Structures and Algorithms</i>. 2025;66(2). doi:<a href=\"https://doi.org/10.1002/rsa.21286\">10.1002/rsa.21286</a>","mla":"Alon, Yahav, and Michael Anastos. “The Completion Numbers of Hamiltonicity and Pancyclicity in Random Graphs.” <i>Random Structures and Algorithms</i>, vol. 66, no. 2, e21286, Wiley, 2025, doi:<a href=\"https://doi.org/10.1002/rsa.21286\">10.1002/rsa.21286</a>.","apa":"Alon, Y., &#38; Anastos, M. (2025). The completion numbers of hamiltonicity and pancyclicity in random graphs. <i>Random Structures and Algorithms</i>. Wiley. <a href=\"https://doi.org/10.1002/rsa.21286\">https://doi.org/10.1002/rsa.21286</a>","ieee":"Y. Alon and M. Anastos, “The completion numbers of hamiltonicity and pancyclicity in random graphs,” <i>Random Structures and Algorithms</i>, vol. 66, no. 2. Wiley, 2025.","ista":"Alon Y, Anastos M. 2025. The completion numbers of hamiltonicity and pancyclicity in random graphs. Random Structures and Algorithms. 66(2), e21286.","short":"Y. Alon, M. Anastos, Random Structures and Algorithms 66 (2025)."},"date_updated":"2025-09-30T11:15:41Z","status":"public","type":"journal_article","tmp":{"image":"/images/cc_by_nc.png","name":"Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)","short":"CC BY-NC (4.0)","legal_code_url":"https://creativecommons.org/licenses/by-nc/4.0/legalcode"},"doi":"10.1002/rsa.21286","date_published":"2025-03-01T00:00:00Z","_id":"19440","article_number":"e21286","issue":"2","volume":66,"oa":1,"file_date_updated":"2025-03-25T11:46:27Z","title":"The completion numbers of hamiltonicity and pancyclicity in random graphs","publication_identifier":{"eissn":["1098-2418"],"issn":["1042-9832"]},"OA_type":"hybrid","OA_place":"publisher","external_id":{"arxiv":["2304.03710"],"isi":["001420226800001"]},"abstract":[{"text":"Let μ(G) denote the minimum number of edges whose addition to G results in a Hamiltonian graph, and let μ^(G) denote the minimum number of edges whose addition to G results in a pancyclic graph. We study the distributions of μ(G),μ^(G) in the context of binomial random graphs. Letting d=d(n):=n⋅p, we prove that there exists a function f:R+→[0,1] of order f(d)=12de−d+e−d+O(d6e−3d) such that, if G∼G(n,p) with 20≤d(n)≤0.4logn, then with high probability μ(G)=(1+o(1))⋅f(d)⋅n. Let ni(G) denote the number of degree i vertices in G. A trivial lower bound on μ(G) is given by the expression n0(G)+⌈12n1(G)⌉. In the denser regime of random graphs, we show that if np−13logn−2loglogn→∞ and G∼G(n,p) then, with high probability, μ(G)=n0(G)+⌈12n1(G)⌉. For completion to pancyclicity, we show that if G∼G(n,p) and np≥20 then, with high probability, μ^(G)=μ(G). Finally, we present a polynomial time algorithm such that, if G∼G(n,p) and np≥20, then, with high probability, the algorithm returns a set of edges of size μ(G) whose addition to G results in a pancyclic (and therefore also Hamiltonian) graph.","lang":"eng"}]},{"scopus_import":"1","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.","isi":1,"publisher":"Wiley","day":"01","department":[{"_id":"MaKw"}],"language":[{"iso":"eng"}],"ddc":["510"],"publication_status":"published","article_type":"original","publication":"Random Structures and Algorithms","quality_controlled":"1","fulldoi":"https://doi.org/10.1002/rsa.21106","month":"07","article_processing_charge":"Yes (in subscription journal)","oa_version":"Published Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","page":"1035-1055","date_created":"2022-07-31T22:01:49Z","has_accepted_license":"1","author":[{"first_name":"Anita","full_name":"Liebenau, Anita","last_name":"Liebenau"},{"last_name":"Mattos","first_name":"Letícia","full_name":"Mattos, Letícia"},{"id":"12c6bd4d-2cd0-11ec-a0da-e28f42f65ebd","last_name":"Mendonca Dos Santos","full_name":"Mendonca Dos Santos, Walner","first_name":"Walner"},{"full_name":"Skokan, Jozef","first_name":"Jozef","last_name":"Skokan"}],"file_date_updated":"2023-10-04T09:37:26Z","title":"Asymmetric Ramsey properties of random graphs involving cliques and cycles","publication_identifier":{"issn":["1042-9832"],"eissn":["1098-2418"]},"oa":1,"abstract":[{"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. ","lang":"eng"}],"external_id":{"isi":["000828530400001"]},"status":"public","type":"journal_article","date_updated":"2023-10-04T09:38:45Z","_id":"11706","tmp":{"image":"/images/cc_by_nc.png","name":"Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)","short":"CC BY-NC (4.0)","legal_code_url":"https://creativecommons.org/licenses/by-nc/4.0/legalcode"},"doi":"10.1002/rsa.21106","date_published":"2023-07-01T00:00:00Z","issue":"4","volume":62,"intvolume":"        62","file":[{"creator":"dernst","content_type":"application/pdf","relation":"main_file","file_size":1362334,"checksum":"3a5969d0c512aef01c30f3dc81c6d59b","file_id":"14389","file_name":"2023_RandomStructureAlgorithms_Liebenau.pdf","date_updated":"2023-10-04T09:37:26Z","access_level":"open_access","date_created":"2023-10-04T09:37:26Z","success":1}],"citation":{"short":"A. Liebenau, L. Mattos, W. Mendonca dos Santos, J. Skokan, Random Structures and Algorithms 62 (2023) 1035–1055.","apa":"Liebenau, A., Mattos, L., Mendonca dos Santos, W., &#38; Skokan, J. (2023). Asymmetric Ramsey properties of random graphs involving cliques and cycles. <i>Random Structures and Algorithms</i>. Wiley. <a href=\"https://doi.org/10.1002/rsa.21106\">https://doi.org/10.1002/rsa.21106</a>","ieee":"A. Liebenau, L. Mattos, W. Mendonca dos Santos, and J. Skokan, “Asymmetric Ramsey properties of random graphs involving cliques and cycles,” <i>Random Structures and Algorithms</i>, vol. 62, no. 4. Wiley, pp. 1035–1055, 2023.","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.","ama":"Liebenau A, Mattos L, Mendonca dos Santos W, Skokan J. Asymmetric Ramsey properties of random graphs involving cliques and cycles. <i>Random Structures and Algorithms</i>. 2023;62(4):1035-1055. doi:<a href=\"https://doi.org/10.1002/rsa.21106\">10.1002/rsa.21106</a>","mla":"Liebenau, Anita, et al. “Asymmetric Ramsey Properties of Random Graphs Involving Cliques and Cycles.” <i>Random Structures and Algorithms</i>, vol. 62, no. 4, Wiley, 2023, pp. 1035–55, doi:<a href=\"https://doi.org/10.1002/rsa.21106\">10.1002/rsa.21106</a>.","chicago":"Liebenau, Anita, Letícia Mattos, Walner Mendonca dos Santos, and Jozef Skokan. “Asymmetric Ramsey Properties of Random Graphs Involving Cliques and Cycles.” <i>Random Structures and Algorithms</i>. Wiley, 2023. <a href=\"https://doi.org/10.1002/rsa.21106\">https://doi.org/10.1002/rsa.21106</a>."},"year":"2023"},{"day":"01","publisher":"Wiley","scopus_import":"1","publication":"Random Structures & Algorithms","language":[{"iso":"eng"}],"article_type":"original","publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","oa_version":"Preprint","fulldoi":"https://doi.org/10.1002/rsa.20950","month":"12","quality_controlled":"1","author":[{"full_name":"Fox, Jacob","first_name":"Jacob","last_name":"Fox"},{"full_name":"He, Xiaoyu","first_name":"Xiaoyu","last_name":"He"},{"full_name":"Wigderson, Yuval","first_name":"Yuval","last_name":"Wigderson","id":"2d0023a0-1567-11f0-833d-d5c1e476d4b5"}],"page":"1157-1173","date_created":"2026-06-29T10:54:10Z","abstract":[{"text":"We introduce a graph Ramsey game called Ramsey, Paper,Scissors. This game has two players, Proposer and Decider.Starting from an empty graph on n vertices, on each turnProposer proposes a potential edge and Decider simultane-ously decides (without knowing Proposer’s choice) whether toadd it to the graph. Proposer cannot propose an edge whichwould create a triangle in the graph. The game ends whenProposer has no legal moves remaining, and Proposer wins ifthe final graph has independence number at least s. We provea threshold phenomenon exists for this game by exhibitingrandomized strategies for both players that are optimal up toconstants. Namely, there exist constants 0 < A < B such that(under optimal play) Proposer wins with high probability ifs < A√n log n, while Decider wins with high probability ifs > B√n log n. This is a factor of Θ(√log n)) larger than thelower bound coming from the off-diagonal Ramsey numberr(3, s).","lang":"eng"}],"external_id":{"arxiv":["1906.01092"]},"OA_place":"repository","OA_type":"green","title":"Ramsey, Paper, Scissors","publication_identifier":{"eissn":["1098-2418"],"issn":["1042-9832"]},"oa":1,"volume":57,"issue":"4","_id":"22166","date_published":"2020-12-01T00:00:00Z","doi":"10.1002/rsa.20950","status":"public","type":"journal_article","date_updated":"2026-07-14T08:31:05Z","citation":{"chicago":"Fox, Jacob, Xiaoyu He, and Yuval Wigderson. “Ramsey, Paper, Scissors.” <i>Random Structures &#38; Algorithms</i>. Wiley, 2020. <a href=\"https://doi.org/10.1002/rsa.20950\">https://doi.org/10.1002/rsa.20950</a>.","mla":"Fox, Jacob, et al. “Ramsey, Paper, Scissors.” <i>Random Structures &#38; Algorithms</i>, vol. 57, no. 4, Wiley, 2020, pp. 1157–73, doi:<a href=\"https://doi.org/10.1002/rsa.20950\">10.1002/rsa.20950</a>.","ama":"Fox J, He X, Wigderson Y. Ramsey, Paper, Scissors. <i>Random Structures &#38; Algorithms</i>. 2020;57(4):1157-1173. doi:<a href=\"https://doi.org/10.1002/rsa.20950\">10.1002/rsa.20950</a>","apa":"Fox, J., He, X., &#38; Wigderson, Y. (2020). Ramsey, Paper, Scissors. <i>Random Structures &#38; Algorithms</i>. Wiley. <a href=\"https://doi.org/10.1002/rsa.20950\">https://doi.org/10.1002/rsa.20950</a>","ieee":"J. Fox, X. He, and Y. Wigderson, “Ramsey, Paper, Scissors,” <i>Random Structures &#38; Algorithms</i>, vol. 57, no. 4. Wiley, pp. 1157–1173, 2020.","ista":"Fox J, He X, Wigderson Y. 2020. Ramsey, Paper, Scissors. Random Structures &#38; Algorithms. 57(4), 1157–1173.","short":"J. Fox, X. He, Y. Wigderson, Random Structures &#38; Algorithms 57 (2020) 1157–1173."},"main_file_link":[{"url":"https://doi.org/10.48550/arXiv.1906.01092","open_access":"1"}],"arxiv":1,"extern":"1","intvolume":"        57","year":"2020"},{"article_type":"original","publication_status":"published","language":[{"iso":"eng"}],"publication":"Random Structures and Algorithms","scopus_import":"1","day":"01","publisher":"Wiley","date_created":"2021-06-18T12:06:28Z","page":"592-603","author":[{"full_name":"Ferber, Asaf","first_name":"Asaf","last_name":"Ferber"},{"first_name":"Matthew Alan","full_name":"Kwan, Matthew Alan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","last_name":"Kwan","orcid":"0000-0002-4003-7567"},{"full_name":"Sudakov, Benny","first_name":"Benny","last_name":"Sudakov"}],"quality_controlled":"1","fulldoi":"https://doi.org/10.1002/rsa.20815","month":"12","oa_version":"Preprint","article_processing_charge":"No","user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","date_updated":"2023-02-23T14:01:03Z","status":"public","type":"journal_article","date_published":"2018-12-01T00:00:00Z","doi":"10.1002/rsa.20815","_id":"9565","issue":"4","volume":53,"oa":1,"title":"Counting Hamilton cycles in sparse random directed graphs","publication_identifier":{"eissn":["1098-2418"],"issn":["1042-9832"]},"external_id":{"arxiv":["1708.07746"]},"abstract":[{"text":"Let D(n,p) be the random directed graph on n vertices where each of the n(n-1) possible arcs is present independently with probability p. A celebrated result of Frieze shows that if p≥(logn+ω(1))/n then D(n,p) typically has a directed Hamilton cycle, and this is best possible. In this paper, we obtain a strengthening of this result, showing that under the same condition, the number of directed Hamilton cycles in D(n,p) is typically n!(p(1+o(1)))n. We also prove a hitting-time version of this statement, showing that in the random directed graph process, as soon as every vertex has in-/out-degrees at least 1, there are typically n!(logn/n(1+o(1)))n directed Hamilton cycles.","lang":"eng"}],"year":"2018","intvolume":"        53","extern":"1","main_file_link":[{"url":"https://arxiv.org/abs/1708.07746","open_access":"1"}],"arxiv":1,"citation":{"chicago":"Ferber, Asaf, Matthew Alan Kwan, and Benny Sudakov. “Counting Hamilton Cycles in Sparse Random Directed Graphs.” <i>Random Structures and Algorithms</i>. Wiley, 2018. <a href=\"https://doi.org/10.1002/rsa.20815\">https://doi.org/10.1002/rsa.20815</a>.","ama":"Ferber A, Kwan MA, Sudakov B. Counting Hamilton cycles in sparse random directed graphs. <i>Random Structures and Algorithms</i>. 2018;53(4):592-603. doi:<a href=\"https://doi.org/10.1002/rsa.20815\">10.1002/rsa.20815</a>","mla":"Ferber, Asaf, et al. “Counting Hamilton Cycles in Sparse Random Directed Graphs.” <i>Random Structures and Algorithms</i>, vol. 53, no. 4, Wiley, 2018, pp. 592–603, doi:<a href=\"https://doi.org/10.1002/rsa.20815\">10.1002/rsa.20815</a>.","ieee":"A. Ferber, M. A. Kwan, and B. Sudakov, “Counting Hamilton cycles in sparse random directed graphs,” <i>Random Structures and Algorithms</i>, vol. 53, no. 4. Wiley, pp. 592–603, 2018.","ista":"Ferber A, Kwan MA, Sudakov B. 2018. Counting Hamilton cycles in sparse random directed graphs. Random Structures and Algorithms. 53(4), 592–603.","apa":"Ferber, A., Kwan, M. A., &#38; Sudakov, B. (2018). Counting Hamilton cycles in sparse random directed graphs. <i>Random Structures and Algorithms</i>. Wiley. <a href=\"https://doi.org/10.1002/rsa.20815\">https://doi.org/10.1002/rsa.20815</a>","short":"A. Ferber, M.A. Kwan, B. Sudakov, Random Structures and Algorithms 53 (2018) 592–603."}},{"title":"The random k‐matching‐free process","publication_identifier":{"issn":["1042-9832"],"eissn":["1098-2418"]},"oa":1,"abstract":[{"text":"Let P be a graph property which is preserved by removal of edges, and consider the random graph process that starts with the empty n-vertex graph and then adds edges one-by-one, each chosen uniformly at random subject to the constraint that P is not violated. These types of random processes have been the subject of extensive research over the last 20 years, having striking applications in extremal combinatorics, and leading to the discovery of important probabilistic tools. In this paper we consider the k-matching-free process, where P is the property of not containing a matching of size k. We are able to analyse the behaviour of this process for a wide range of values of k; in particular we prove that if k=o(n) or if n−2k=o(n−−√/logn) then this process is likely to terminate in a k-matching-free graph with the maximum possible number of edges, as characterised by Erdős and Gallai. We also show that these bounds on k are essentially best possible, and we make a first step towards understanding the behaviour of the process in the intermediate regime.","lang":"eng"}],"external_id":{"arxiv":["1708.01054"]},"_id":"9567","date_published":"2018-12-01T00:00:00Z","doi":"10.1002/rsa.20814","type":"journal_article","status":"public","date_updated":"2023-02-23T14:01:07Z","volume":53,"issue":"4","extern":"1","intvolume":"        53","citation":{"chicago":"Krivelevich, Michael, Matthew Alan Kwan, Po‐Shen Loh, and Benny Sudakov. “The Random K‐matching‐free Process.” <i>Random Structures and Algorithms</i>. Wiley, 2018. <a href=\"https://doi.org/10.1002/rsa.20814\">https://doi.org/10.1002/rsa.20814</a>.","ama":"Krivelevich M, Kwan MA, Loh P, Sudakov B. The random k‐matching‐free process. <i>Random Structures and Algorithms</i>. 2018;53(4):692-716. doi:<a href=\"https://doi.org/10.1002/rsa.20814\">10.1002/rsa.20814</a>","mla":"Krivelevich, Michael, et al. “The Random K‐matching‐free Process.” <i>Random Structures and Algorithms</i>, vol. 53, no. 4, Wiley, 2018, pp. 692–716, doi:<a href=\"https://doi.org/10.1002/rsa.20814\">10.1002/rsa.20814</a>.","ista":"Krivelevich M, Kwan MA, Loh P, Sudakov B. 2018. The random k‐matching‐free process. Random Structures and Algorithms. 53(4), 692–716.","ieee":"M. Krivelevich, M. A. Kwan, P. Loh, and B. Sudakov, “The random k‐matching‐free process,” <i>Random Structures and Algorithms</i>, vol. 53, no. 4. Wiley, pp. 692–716, 2018.","apa":"Krivelevich, M., Kwan, M. A., Loh, P., &#38; Sudakov, B. (2018). The random k‐matching‐free process. <i>Random Structures and Algorithms</i>. Wiley. <a href=\"https://doi.org/10.1002/rsa.20814\">https://doi.org/10.1002/rsa.20814</a>","short":"M. Krivelevich, M.A. Kwan, P. Loh, B. Sudakov, Random Structures and Algorithms 53 (2018) 692–716."},"arxiv":1,"main_file_link":[{"url":"https://arxiv.org/abs/1708.01054","open_access":"1"}],"year":"2018","scopus_import":"1","publisher":"Wiley","day":"01","language":[{"iso":"eng"}],"article_type":"original","publication_status":"published","publication":"Random Structures and Algorithms","article_processing_charge":"No","oa_version":"Preprint","quality_controlled":"1","fulldoi":"https://doi.org/10.1002/rsa.20814","month":"12","user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","date_created":"2021-06-18T12:37:40Z","page":"692-716","author":[{"first_name":"Michael","full_name":"Krivelevich, Michael","last_name":"Krivelevich"},{"first_name":"Matthew Alan","full_name":"Kwan, Matthew Alan","last_name":"Kwan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","orcid":"0000-0002-4003-7567"},{"last_name":"Loh","first_name":"Po‐Shen","full_name":"Loh, Po‐Shen"},{"full_name":"Sudakov, Benny","first_name":"Benny","last_name":"Sudakov"}]},{"publication":"Random Structures and Algorithms","language":[{"iso":"eng"}],"publication_status":"published","article_type":"original","day":"01","publisher":"Wiley","scopus_import":"1","author":[{"id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","orcid":"0000-0002-4003-7567","last_name":"Kwan","full_name":"Kwan, Matthew Alan","first_name":"Matthew Alan"},{"first_name":"Benny","full_name":"Sudakov, Benny","last_name":"Sudakov"}],"page":"181-196","date_created":"2021-06-18T12:47:25Z","user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","article_processing_charge":"No","oa_version":"Preprint","month":"03","fulldoi":"https://doi.org/10.1002/rsa.20742","quality_controlled":"1","volume":52,"issue":"2","_id":"9568","date_published":"2018-03-01T00:00:00Z","doi":"10.1002/rsa.20742","type":"journal_article","status":"public","date_updated":"2023-02-23T14:01:09Z","abstract":[{"text":"An intercalate in a Latin square is a 2×2 Latin subsquare. Let N be the number of intercalates in a uniformly random n×n Latin square. We prove that asymptotically almost surely N≥(1−o(1))n2/4, and that EN≤(1+o(1))n2/2 (therefore asymptotically almost surely N≤fn2 for any f→∞). This significantly improves the previous best lower and upper bounds. We also give an upper tail bound for the number of intercalates in two fixed rows of a random Latin square. In addition, we discuss a problem of Linial and Luria on low-discrepancy Latin squares.","lang":"eng"}],"external_id":{"arxiv":["1607.04981"]},"publication_identifier":{"issn":["1042-9832"],"eissn":["1098-2418"]},"title":"Intercalates and discrepancy in random Latin squares","oa":1,"year":"2018","citation":{"short":"M.A. Kwan, B. Sudakov, Random Structures and Algorithms 52 (2018) 181–196.","ieee":"M. A. Kwan and B. Sudakov, “Intercalates and discrepancy in random Latin squares,” <i>Random Structures and Algorithms</i>, vol. 52, no. 2. Wiley, pp. 181–196, 2018.","ista":"Kwan MA, Sudakov B. 2018. Intercalates and discrepancy in random Latin squares. Random Structures and Algorithms. 52(2), 181–196.","apa":"Kwan, M. A., &#38; Sudakov, B. (2018). Intercalates and discrepancy in random Latin squares. <i>Random Structures and Algorithms</i>. Wiley. <a href=\"https://doi.org/10.1002/rsa.20742\">https://doi.org/10.1002/rsa.20742</a>","mla":"Kwan, Matthew Alan, and Benny Sudakov. “Intercalates and Discrepancy in Random Latin Squares.” <i>Random Structures and Algorithms</i>, vol. 52, no. 2, Wiley, 2018, pp. 181–96, doi:<a href=\"https://doi.org/10.1002/rsa.20742\">10.1002/rsa.20742</a>.","ama":"Kwan MA, Sudakov B. Intercalates and discrepancy in random Latin squares. <i>Random Structures and Algorithms</i>. 2018;52(2):181-196. doi:<a href=\"https://doi.org/10.1002/rsa.20742\">10.1002/rsa.20742</a>","chicago":"Kwan, Matthew Alan, and Benny Sudakov. “Intercalates and Discrepancy in Random Latin Squares.” <i>Random Structures and Algorithms</i>. Wiley, 2018. <a href=\"https://doi.org/10.1002/rsa.20742\">https://doi.org/10.1002/rsa.20742</a>."},"arxiv":1,"main_file_link":[{"url":"https://arxiv.org/abs/1607.04981","open_access":"1"}],"extern":"1","intvolume":"        52"},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","fulldoi":"https://doi.org/10.1002/(sici)1098-2418(199712)11:4<369::aid-rsa5>3.0.co;2-x","month":"12","quality_controlled":"1","article_processing_charge":"No","oa_version":"None","author":[{"full_name":"Henzinger, Monika H","first_name":"Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530"},{"last_name":"Thorup","full_name":"Thorup, Mikkel","first_name":"Mikkel"}],"page":"369-379","date_created":"2022-08-17T07:21:55Z","day":"07","publisher":"Wiley","scopus_import":"1","publication":"Random Structures and Algorithms","language":[{"iso":"eng"}],"article_type":"original","publication_status":"published","citation":{"short":"M. Henzinger, M. Thorup, Random Structures and Algorithms 11 (1997) 369–379.","apa":"Henzinger, M., &#38; Thorup, M. (1997). Sampling to provide or to bound: With applications to fully dynamic graph algorithms. <i>Random Structures and Algorithms</i>. Wiley. <a href=\"https://doi.org/10.1002/(sici)1098-2418(199712)11:4&#60;369::aid-rsa5&#62;3.0.co;2-x\">https://doi.org/10.1002/(sici)1098-2418(199712)11:4&#60;369::aid-rsa5&#62;3.0.co;2-x</a>","ista":"Henzinger M, Thorup M. 1997. Sampling to provide or to bound: With applications to fully dynamic graph algorithms. Random Structures and Algorithms. 11(4), 369–379.","ieee":"M. Henzinger and M. Thorup, “Sampling to provide or to bound: With applications to fully dynamic graph algorithms,” <i>Random Structures and Algorithms</i>, vol. 11, no. 4. Wiley, pp. 369–379, 1997.","ama":"Henzinger M, Thorup M. Sampling to provide or to bound: With applications to fully dynamic graph algorithms. <i>Random Structures and Algorithms</i>. 1997;11(4):369-379. doi:<a href=\"https://doi.org/10.1002/(sici)1098-2418(199712)11:4&#60;369::aid-rsa5&#62;3.0.co;2-x\">10.1002/(sici)1098-2418(199712)11:4&#60;369::aid-rsa5&#62;3.0.co;2-x</a>","mla":"Henzinger, Monika, and Mikkel Thorup. “Sampling to Provide or to Bound: With Applications to Fully Dynamic Graph Algorithms.” <i>Random Structures and Algorithms</i>, vol. 11, no. 4, Wiley, 1997, pp. 369–79, doi:<a href=\"https://doi.org/10.1002/(sici)1098-2418(199712)11:4&#60;369::aid-rsa5&#62;3.0.co;2-x\">10.1002/(sici)1098-2418(199712)11:4&#60;369::aid-rsa5&#62;3.0.co;2-x</a>.","chicago":"Henzinger, Monika, and Mikkel Thorup. “Sampling to Provide or to Bound: With Applications to Fully Dynamic Graph Algorithms.” <i>Random Structures and Algorithms</i>. Wiley, 1997. <a href=\"https://doi.org/10.1002/(sici)1098-2418(199712)11:4&#60;369::aid-rsa5&#62;3.0.co;2-x\">https://doi.org/10.1002/(sici)1098-2418(199712)11:4&#60;369::aid-rsa5&#62;3.0.co;2-x</a>."},"intvolume":"        11","extern":"1","year":"1997","abstract":[{"lang":"eng","text":"In dynamic graph algorithms the following provide-or-bound problem has to be solved quickly: Given a set S containing a subset R and a way of generating random elements from S testing for membership in R, either (i) provide an element of R, or (ii) give a (small) upper bound on the size of R that holds with high probability. We give an optimal algorithm for this problem. This algorithm improves the time per operation for various dynamic graph algorithms by a factor of O(log n). For example, it improves the time per update for fully dynamic connectivity from O(log3n) to O(log2n)."}],"publication_identifier":{"eissn":["1098-2418"],"issn":["1042-9832"]},"title":"Sampling to provide or to bound: With applications to fully dynamic graph algorithms","issue":"4","volume":11,"status":"public","type":"journal_article","date_updated":"2024-11-06T12:00:44Z","_id":"11883","date_published":"1997-12-07T00:00:00Z","doi":"10.1002/(sici)1098-2418(199712)11:4<369::aid-rsa5>3.0.co;2-x"}]