[{"month":"07","publication_identifier":{"eissn":["1077-8926"]},"quality_controlled":"1","article_type":"original","volume":30,"date_created":"2023-09-10T22:01:12Z","article_number":"P3.10","department":[{"_id":"MaKw"}],"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).","file_date_updated":"2023-09-15T08:02:09Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["510"],"article_processing_charge":"Yes","intvolume":"        30","author":[{"first_name":"Michael","full_name":"Anastos, Michael","id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb","last_name":"Anastos"},{"full_name":"Fabian, David","first_name":"David","last_name":"Fabian"},{"last_name":"Müyesser","full_name":"Müyesser, Alp","first_name":"Alp"},{"last_name":"Szabó","first_name":"Tibor","full_name":"Szabó, Tibor"}],"_id":"14319","oa":1,"date_published":"2023-07-28T00:00:00Z","doi":"10.37236/11714","language":[{"iso":"eng"}],"year":"2023","publisher":"Electronic Journal of Combinatorics","type":"journal_article","publication":"Electronic Journal of Combinatorics","title":"Splitting matchings and the Ryser-Brualdi-Stein conjecture for multisets","file":[{"date_created":"2023-09-15T08:02:09Z","checksum":"52c46c8cb329f9aaee9ade01525f317b","file_id":"14338","date_updated":"2023-09-15T08:02:09Z","success":1,"file_name":"2023_elecJournCombinatorics_Anastos.pdf","file_size":247917,"access_level":"open_access","relation":"main_file","content_type":"application/pdf","creator":"dernst"}],"external_id":{"arxiv":["2212.03100"]},"arxiv":1,"citation":{"mla":"Anastos, Michael, et al. “Splitting Matchings and the Ryser-Brualdi-Stein Conjecture for Multisets.” <i>Electronic Journal of Combinatorics</i>, vol. 30, no. 3, P3.10, Electronic Journal of Combinatorics, 2023, doi:<a href=\"https://doi.org/10.37236/11714\">10.37236/11714</a>.","short":"M. Anastos, D. Fabian, A. Müyesser, T. Szabó, Electronic Journal of Combinatorics 30 (2023).","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.","apa":"Anastos, M., Fabian, D., Müyesser, A., &#38; Szabó, T. (2023). Splitting matchings and the Ryser-Brualdi-Stein conjecture for multisets. <i>Electronic Journal of Combinatorics</i>. Electronic Journal of Combinatorics. <a href=\"https://doi.org/10.37236/11714\">https://doi.org/10.37236/11714</a>","ama":"Anastos M, Fabian D, Müyesser A, Szabó T. Splitting matchings and the Ryser-Brualdi-Stein conjecture for multisets. <i>Electronic Journal of Combinatorics</i>. 2023;30(3). doi:<a href=\"https://doi.org/10.37236/11714\">10.37236/11714</a>","chicago":"Anastos, Michael, David Fabian, Alp Müyesser, and Tibor Szabó. “Splitting Matchings and the Ryser-Brualdi-Stein Conjecture for Multisets.” <i>Electronic Journal of Combinatorics</i>. Electronic Journal of Combinatorics, 2023. <a href=\"https://doi.org/10.37236/11714\">https://doi.org/10.37236/11714</a>.","ieee":"M. Anastos, D. Fabian, A. Müyesser, and T. Szabó, “Splitting matchings and the Ryser-Brualdi-Stein conjecture for multisets,” <i>Electronic Journal of Combinatorics</i>, vol. 30, no. 3. Electronic Journal of Combinatorics, 2023."},"project":[{"grant_number":"101034413","call_identifier":"H2020","name":"IST-BRIDGE: International postdoctoral program","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c"}],"scopus_import":"1","issue":"3","has_accepted_license":"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"},"day":"28","publication_status":"published","oa_version":"Published Version","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."}],"ec_funded":1,"date_updated":"2023-09-15T08:12:30Z","status":"public","license":"https://creativecommons.org/licenses/by-nd/4.0/"},{"abstract":[{"lang":"eng","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."}],"publication_status":"published","page":"2286-2323","oa_version":"Preprint","day":"01","status":"public","date_updated":"2023-09-25T09:13:41Z","external_id":{"arxiv":["2111.14759"]},"title":"Fast algorithms for solving the Hamilton cycle problem with high probability","publication":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2111.14759","open_access":"1"}],"scopus_import":"1","citation":{"chicago":"Anastos, Michael. “Fast Algorithms for Solving the Hamilton Cycle Problem with High Probability.” In <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>, 2023:2286–2323. Society for Industrial and Applied Mathematics, 2023. <a href=\"https://doi.org/10.1137/1.9781611977554.ch88\">https://doi.org/10.1137/1.9781611977554.ch88</a>.","ieee":"M. Anastos, “Fast algorithms for solving the Hamilton cycle problem with high probability,” in <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Florence, Italy, 2023, vol. 2023, pp. 2286–2323.","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.","mla":"Anastos, Michael. “Fast Algorithms for Solving the Hamilton Cycle Problem with High Probability.” <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>, vol. 2023, Society for Industrial and Applied Mathematics, 2023, pp. 2286–323, doi:<a href=\"https://doi.org/10.1137/1.9781611977554.ch88\">10.1137/1.9781611977554.ch88</a>.","short":"M. Anastos, in:, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2023, pp. 2286–2323.","apa":"Anastos, M. (2023). Fast algorithms for solving the Hamilton cycle problem with high probability. In <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i> (Vol. 2023, pp. 2286–2323). Florence, Italy: Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/1.9781611977554.ch88\">https://doi.org/10.1137/1.9781611977554.ch88</a>","ama":"Anastos M. Fast algorithms for solving the Hamilton cycle problem with high probability. In: <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>. Vol 2023. Society for Industrial and Applied Mathematics; 2023:2286-2323. doi:<a href=\"https://doi.org/10.1137/1.9781611977554.ch88\">10.1137/1.9781611977554.ch88</a>"},"arxiv":1,"date_published":"2023-01-01T00:00:00Z","oa":1,"_id":"14344","author":[{"id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb","last_name":"Anastos","full_name":"Anastos, Michael","first_name":"Michael"}],"type":"conference","publisher":"Society for Industrial and Applied Mathematics","year":"2023","language":[{"iso":"eng"}],"doi":"10.1137/1.9781611977554.ch88","volume":2023,"quality_controlled":"1","publication_identifier":{"isbn":["9781611977554"]},"month":"01","intvolume":"      2023","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","conference":{"location":"Florence, Italy","name":"SODA: Symposium on Discrete Algorithms","start_date":"2023-01-22","end_date":"2023-01-25"},"department":[{"_id":"MaKw"}],"date_created":"2023-09-17T22:01:10Z"},{"type":"conference","publisher":"Masaryk University Press","year":"2023","language":[{"iso":"eng"}],"doi":"10.5817/cz.muni.eurocomb23-005","date_published":"2023-09-01T00:00:00Z","oa":1,"_id":"14867","author":[{"id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb","last_name":"Anastos","first_name":"Michael","full_name":"Anastos, Michael"}],"ddc":["510"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","conference":{"location":"Prague, Czech Republic","start_date":"2023-08-28","end_date":"2023-09-01","name":"EUROCOMB: European Conference on Combinatorics, Graph Theory and Applications"},"file_date_updated":"2024-01-24T09:34:43Z","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","department":[{"_id":"MaKw"}],"date_created":"2024-01-22T12:20:15Z","quality_controlled":"1","publication_identifier":{"eissn":["2788-3116"]},"month":"09","status":"public","date_updated":"2024-01-24T09:38:44Z","ec_funded":1,"abstract":[{"text":"<jats:p>Starting with the empty graph on $[n]$, at each round, a set of $K=K(n)$ edges is presented chosen uniformly at random from the ones that have not been presented yet. We are then asked to choose at most one of the presented edges and add it to the current graph. Our goal is to construct a Hamiltonian graph with $(1+o(1))n$ edges within as few rounds as possible. We show that in this process, one can build a Hamiltonian graph of size $(1+o(1))n$ in $(1+o(1))(1+(\\log n)/2K) n$ rounds w.h.p. The case $K=1$ implies that w.h.p. one can build a Hamiltonian graph by choosing $(1+o(1))n$ edges in an online fashion as they appear along the first $(0.5+o(1))n\\log n$ rounds of the random graph process. This answers a question of Frieze, Krivelevich and Michaeli. Observe that the number of rounds is asymptotically optimal as the first $0.5n\\log n$ edges do not span a Hamilton cycle w.h.p. The case $K=\\Theta(\\log n)$ implies that the Hamiltonicity threshold of the corresponding Achlioptas process is at most $(1+o(1))(1+(\\log n)/2K) n$. This matches the $(1-o(1))(1+(\\log n)/2K) n$ lower bound due to Krivelevich, Lubetzky and Sudakov and resolves the problem of determining the Hamiltonicity threshold of the Achlioptas process with $K=\\Theta(\\log n)$. We also show that in the above process one can construct a graph $G$ that spans a matching of size $\\lfloor V(G)/2) \\rfloor$ and $(0.5+o(1))n$ edges within $(1+o(1))(0.5+(\\log n)/2K) n$ rounds w.h.p. Our proof relies on a robust Hamiltonicity property of the strong $4$-core of the binomial random graph which we use as a black-box. This property allows it to absorb paths covering vertices outside the strong $4$-core into a cycle.</jats:p>","lang":"eng"}],"page":"36-41","publication_status":"published","oa_version":"Published Version","day":"01","tmp":{"image":"/images/cc_by_nc_nd.png","short":"CC BY-NC-ND (4.0)","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"},"has_accepted_license":"1","project":[{"name":"IST-BRIDGE: International postdoctoral program","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","call_identifier":"H2020","grant_number":"101034413"}],"citation":{"short":"M. Anastos, in:, Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications, Masaryk University Press, 2023, pp. 36–41.","apa":"Anastos, M. (2023). Constructing Hamilton cycles and perfect matchings efficiently. In <i>Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications</i> (pp. 36–41). Prague, Czech Republic: Masaryk University Press. <a href=\"https://doi.org/10.5817/cz.muni.eurocomb23-005\">https://doi.org/10.5817/cz.muni.eurocomb23-005</a>","ista":"Anastos M. 2023. Constructing Hamilton cycles and perfect matchings efficiently. Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications. EUROCOMB: European Conference on Combinatorics, Graph Theory and Applications, 36–41.","mla":"Anastos, Michael. “Constructing Hamilton Cycles and Perfect Matchings Efficiently.” <i>Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications</i>, Masaryk University Press, 2023, pp. 36–41, doi:<a href=\"https://doi.org/10.5817/cz.muni.eurocomb23-005\">10.5817/cz.muni.eurocomb23-005</a>.","ama":"Anastos M. Constructing Hamilton cycles and perfect matchings efficiently. In: <i>Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications</i>. Masaryk University Press; 2023:36-41. doi:<a href=\"https://doi.org/10.5817/cz.muni.eurocomb23-005\">10.5817/cz.muni.eurocomb23-005</a>","chicago":"Anastos, Michael. “Constructing Hamilton Cycles and Perfect Matchings Efficiently.” In <i>Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications</i>, 36–41. Masaryk University Press, 2023. <a href=\"https://doi.org/10.5817/cz.muni.eurocomb23-005\">https://doi.org/10.5817/cz.muni.eurocomb23-005</a>.","ieee":"M. Anastos, “Constructing Hamilton cycles and perfect matchings efficiently,” in <i>Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications</i>, Prague, Czech Republic, 2023, pp. 36–41."},"arxiv":1,"external_id":{"arxiv":["2209.09860"]},"title":"Constructing Hamilton cycles and perfect matchings efficiently","file":[{"file_name":"2023_Eurocomb_Anastos.pdf","file_size":464230,"file_id":"14881","date_created":"2024-01-24T09:34:43Z","checksum":"fb1d9a1e7389d90ec0e5e76934373cf8","success":1,"date_updated":"2024-01-24T09:34:43Z","creator":"dernst","access_level":"open_access","content_type":"application/pdf","relation":"main_file"}],"publication":"Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications"},{"date_published":"2023-05-05T00:00:00Z","author":[{"id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb","last_name":"Anastos","first_name":"Michael","full_name":"Anastos, Michael"}],"_id":"13042","oa":1,"type":"journal_article","doi":"10.37236/11471","language":[{"iso":"eng"}],"year":"2023","publisher":"Electronic Journal of Combinatorics","isi":1,"volume":30,"article_type":"original","month":"05","publication_identifier":{"eissn":["1077-8926"]},"quality_controlled":"1","file_date_updated":"2023-05-22T07:43:19Z","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","article_processing_charge":"No","ddc":["510"],"intvolume":"        30","date_created":"2023-05-21T22:01:05Z","article_number":"P2.21","department":[{"_id":"MaKw"}],"acknowledgement":"We would like to thank the reviewers for their helpful comments and remarks.","day":"05","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)"},"oa_version":"Published Version","publication_status":"published","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"}],"status":"public","date_updated":"2023-08-01T14:44:52Z","publication":"Electronic Journal of Combinatorics","title":"A note on long cycles in sparse random graphs","file":[{"file_size":448736,"file_name":"2023_JourCombinatorics_Anastos.pdf","success":1,"date_updated":"2023-05-22T07:43:19Z","date_created":"2023-05-22T07:43:19Z","file_id":"13046","checksum":"6269ed3b3eded6536d3d9d6baad2d5b9","creator":"dernst","content_type":"application/pdf","relation":"main_file","access_level":"open_access"}],"external_id":{"arxiv":["2105.13828"],"isi":["000988285500001"]},"scopus_import":"1","issue":"2","has_accepted_license":"1","arxiv":1,"citation":{"ama":"Anastos M. A note on long cycles in sparse random graphs. <i>Electronic Journal of Combinatorics</i>. 2023;30(2). doi:<a href=\"https://doi.org/10.37236/11471\">10.37236/11471</a>","apa":"Anastos, M. (2023). A note on long cycles in sparse random graphs. <i>Electronic Journal of Combinatorics</i>. Electronic Journal of Combinatorics. <a href=\"https://doi.org/10.37236/11471\">https://doi.org/10.37236/11471</a>","ista":"Anastos M. 2023. A note on long cycles in sparse random graphs. Electronic Journal of Combinatorics. 30(2), P2.21.","short":"M. Anastos, Electronic Journal of Combinatorics 30 (2023).","mla":"Anastos, Michael. “A Note on Long Cycles in Sparse Random Graphs.” <i>Electronic Journal of Combinatorics</i>, vol. 30, no. 2, P2.21, Electronic Journal of Combinatorics, 2023, doi:<a href=\"https://doi.org/10.37236/11471\">10.37236/11471</a>.","ieee":"M. Anastos, “A note on long cycles in sparse random graphs,” <i>Electronic Journal of Combinatorics</i>, vol. 30, no. 2. Electronic Journal of Combinatorics, 2023.","chicago":"Anastos, Michael. “A Note on Long Cycles in Sparse Random Graphs.” <i>Electronic Journal of Combinatorics</i>. Electronic Journal of Combinatorics, 2023. <a href=\"https://doi.org/10.37236/11471\">https://doi.org/10.37236/11471</a>."}},{"publication":"63rd Annual IEEE Symposium on Foundations of Computer Science","title":"Solving the Hamilton cycle problem fast on average","external_id":{"isi":["000909382900084"]},"citation":{"ama":"Anastos M. Solving the Hamilton cycle problem fast on average. In: <i>63rd Annual IEEE Symposium on Foundations of Computer Science</i>. Vol 2022-October. Institute of Electrical and Electronics Engineers; 2022:919-930. doi:<a href=\"https://doi.org/10.1109/FOCS54457.2022.00091\">10.1109/FOCS54457.2022.00091</a>","mla":"Anastos, Michael. “Solving the Hamilton Cycle Problem Fast on Average.” <i>63rd Annual IEEE Symposium on Foundations of Computer Science</i>, vol. 2022–October, Institute of Electrical and Electronics Engineers, 2022, pp. 919–30, doi:<a href=\"https://doi.org/10.1109/FOCS54457.2022.00091\">10.1109/FOCS54457.2022.00091</a>.","apa":"Anastos, M. (2022). Solving the Hamilton cycle problem fast on average. In <i>63rd Annual IEEE Symposium on Foundations of Computer Science</i> (Vol. 2022–October, pp. 919–930). Denver, CO, United States: Institute of Electrical and Electronics Engineers. <a href=\"https://doi.org/10.1109/FOCS54457.2022.00091\">https://doi.org/10.1109/FOCS54457.2022.00091</a>","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.","short":"M. Anastos, in:, 63rd Annual IEEE Symposium on Foundations of Computer Science, Institute of Electrical and Electronics Engineers, 2022, pp. 919–930.","ieee":"M. Anastos, “Solving the Hamilton cycle problem fast on average,” in <i>63rd Annual IEEE Symposium on Foundations of Computer Science</i>, Denver, CO, United States, 2022, vol. 2022–October, pp. 919–930.","chicago":"Anastos, Michael. “Solving the Hamilton Cycle Problem Fast on Average.” In <i>63rd Annual IEEE Symposium on Foundations of Computer Science</i>, 2022–October:919–30. Institute of Electrical and Electronics Engineers, 2022. <a href=\"https://doi.org/10.1109/FOCS54457.2022.00091\">https://doi.org/10.1109/FOCS54457.2022.00091</a>."},"project":[{"grant_number":"101034413","call_identifier":"H2020","name":"IST-BRIDGE: International postdoctoral program","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c"}],"scopus_import":"1","day":"01","page":"919-930","publication_status":"published","oa_version":"None","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."}],"ec_funded":1,"date_updated":"2023-08-04T09:37:56Z","status":"public","month":"12","publication_identifier":{"isbn":["9781665455190"],"issn":["0272-5428"]},"quality_controlled":"1","isi":1,"volume":"2022-October","date_created":"2023-01-29T23:00:59Z","department":[{"_id":"MaKw"}],"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","conference":{"name":"FOCS: Symposium on Foundations of Computer Science","end_date":"2022-11-03","start_date":"2022-10-31","location":"Denver, CO, United States"},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","article_processing_charge":"No","author":[{"last_name":"Anastos","id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb","full_name":"Anastos, Michael","first_name":"Michael"}],"_id":"12432","date_published":"2022-12-01T00:00:00Z","doi":"10.1109/FOCS54457.2022.00091","language":[{"iso":"eng"}],"year":"2022","publisher":"Institute of Electrical and Electronics Engineers","type":"conference"}]