[{"language":[{"iso":"eng"}],"month":"07","article_number":"P3.10","oa_version":"Published Version","project":[{"name":"IST-BRIDGE: International postdoctoral program","grant_number":"101034413","call_identifier":"H2020","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c"}],"publication":"Electronic Journal of Combinatorics","has_accepted_license":"1","status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"success":1,"relation":"main_file","access_level":"open_access","file_id":"14338","creator":"dernst","date_created":"2023-09-15T08:02:09Z","file_size":247917,"checksum":"52c46c8cb329f9aaee9ade01525f317b","date_updated":"2023-09-15T08:02:09Z","content_type":"application/pdf","file_name":"2023_elecJournCombinatorics_Anastos.pdf"}],"oa":1,"publication_identifier":{"eissn":["1077-8926"]},"date_published":"2023-07-28T00:00:00Z","type":"journal_article","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by-nd/4.0/legalcode","name":"Creative Commons Attribution-NoDerivatives 4.0 International (CC BY-ND 4.0)","image":"/image/cc_by_nd.png","short":"CC BY-ND (4.0)"},"article_type":"original","publisher":"Electronic Journal of Combinatorics","file_date_updated":"2023-09-15T08:02:09Z","ec_funded":1,"quality_controlled":"1","title":"Splitting matchings and the Ryser-Brualdi-Stein conjecture for multisets","intvolume":"        30","publication_status":"published","date_created":"2023-09-10T22:01:12Z","department":[{"_id":"MaKw"}],"article_processing_charge":"Yes","author":[{"full_name":"Anastos, Michael","last_name":"Anastos","first_name":"Michael","id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb"},{"last_name":"Fabian","first_name":"David","full_name":"Fabian, David"},{"first_name":"Alp","last_name":"Müyesser","full_name":"Müyesser, Alp"},{"first_name":"Tibor","last_name":"Szabó","full_name":"Szabó, Tibor"}],"issue":"3","_id":"14319","license":"https://creativecommons.org/licenses/by-nd/4.0/","scopus_import":"1","ddc":["510"],"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).","abstract":[{"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.","lang":"eng"}],"arxiv":1,"doi":"10.37236/11714","day":"28","external_id":{"arxiv":["2212.03100"]},"date_updated":"2023-09-15T08:12:30Z","year":"2023","citation":{"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.","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>","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.","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)."}},{"quality_controlled":"1","page":"2286-2323","publisher":"Society for Industrial and Applied Mathematics","author":[{"id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb","full_name":"Anastos, Michael","last_name":"Anastos","first_name":"Michael"}],"scopus_import":"1","_id":"14344","intvolume":"      2023","title":"Fast algorithms for solving the Hamilton cycle problem with high probability","department":[{"_id":"MaKw"}],"date_created":"2023-09-17T22:01:10Z","article_processing_charge":"No","publication_status":"published","volume":2023,"external_id":{"arxiv":["2111.14759"]},"year":"2023","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.","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>","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.","short":"M. Anastos, in:, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2023, pp. 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>."},"date_updated":"2023-09-25T09:13:41Z","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."}],"day":"01","arxiv":1,"doi":"10.1137/1.9781611977554.ch88","language":[{"iso":"eng"}],"conference":{"location":"Florence, Italy","end_date":"2023-01-25","name":"SODA: Symposium on Discrete Algorithms","start_date":"2023-01-22"},"publication":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms","month":"01","oa_version":"Preprint","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2111.14759","open_access":"1"}],"type":"conference","date_published":"2023-01-01T00:00:00Z","oa":1,"publication_identifier":{"isbn":["9781611977554"]}},{"publisher":"Masaryk University Press","page":"36-41","quality_controlled":"1","ec_funded":1,"file_date_updated":"2024-01-24T09:34:43Z","publication_status":"published","date_created":"2024-01-22T12:20:15Z","article_processing_charge":"No","department":[{"_id":"MaKw"}],"title":"Constructing Hamilton cycles and perfect matchings efficiently","_id":"14867","author":[{"full_name":"Anastos, Michael","last_name":"Anastos","first_name":"Michael","id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb"}],"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","ddc":["510"],"arxiv":1,"doi":"10.5817/cz.muni.eurocomb23-005","day":"01","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"}],"date_updated":"2024-01-24T09:38:44Z","citation":{"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.","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>.","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>","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>","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>.","short":"M. Anastos, in:, Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications, Masaryk University Press, 2023, pp. 36–41."},"year":"2023","external_id":{"arxiv":["2209.09860"]},"conference":{"location":"Prague, Czech Republic","end_date":"2023-09-01","start_date":"2023-08-28","name":"EUROCOMB: European Conference on Combinatorics, Graph Theory and Applications"},"language":[{"iso":"eng"}],"oa_version":"Published Version","project":[{"call_identifier":"H2020","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","grant_number":"101034413","name":"IST-BRIDGE: International postdoctoral program"}],"month":"09","publication":"Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications","has_accepted_license":"1","file":[{"checksum":"fb1d9a1e7389d90ec0e5e76934373cf8","file_size":464230,"date_created":"2024-01-24T09:34:43Z","file_name":"2023_Eurocomb_Anastos.pdf","content_type":"application/pdf","date_updated":"2024-01-24T09:34:43Z","success":1,"access_level":"open_access","relation":"main_file","creator":"dernst","file_id":"14881"}],"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_identifier":{"eissn":["2788-3116"]},"oa":1,"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode","short":"CC BY-NC-ND (4.0)","name":"Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)","image":"/images/cc_by_nc_nd.png"},"date_published":"2023-09-01T00:00:00Z","type":"conference"},{"file":[{"creator":"dernst","file_id":"13046","success":1,"relation":"main_file","access_level":"open_access","content_type":"application/pdf","file_name":"2023_JourCombinatorics_Anastos.pdf","date_updated":"2023-05-22T07:43:19Z","file_size":448736,"checksum":"6269ed3b3eded6536d3d9d6baad2d5b9","date_created":"2023-05-22T07:43:19Z"}],"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","status":"public","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"date_published":"2023-05-05T00:00:00Z","type":"journal_article","publication_identifier":{"eissn":["1077-8926"]},"oa":1,"language":[{"iso":"eng"}],"publication":"Electronic Journal of Combinatorics","has_accepted_license":"1","oa_version":"Published Version","month":"05","article_number":"P2.21","volume":30,"acknowledgement":"We would like to thank the reviewers for their helpful comments and remarks.","ddc":["510"],"date_updated":"2023-08-01T14:44:52Z","citation":{"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>.","short":"M. Anastos, Electronic Journal of Combinatorics 30 (2023).","ista":"Anastos M. 2023. A note on long cycles in sparse random graphs. Electronic Journal of Combinatorics. 30(2), P2.21.","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>","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>."},"year":"2023","isi":1,"external_id":{"isi":["000988285500001"],"arxiv":["2105.13828"]},"doi":"10.37236/11471","arxiv":1,"day":"05","abstract":[{"lang":"eng","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→∞."}],"quality_controlled":"1","file_date_updated":"2023-05-22T07:43:19Z","publisher":"Electronic Journal of Combinatorics","article_type":"original","_id":"13042","scopus_import":"1","author":[{"id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb","full_name":"Anastos, Michael","last_name":"Anastos","first_name":"Michael"}],"issue":"2","publication_status":"published","department":[{"_id":"MaKw"}],"date_created":"2023-05-21T22:01:05Z","article_processing_charge":"No","title":"A note on long cycles in sparse random graphs","intvolume":"        30"},{"language":[{"iso":"eng"}],"conference":{"location":"Denver, CO, United States","end_date":"2022-11-03","start_date":"2022-10-31","name":"FOCS: Symposium on Foundations of Computer Science"},"publication":"63rd Annual IEEE Symposium on Foundations of Computer Science","project":[{"_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","call_identifier":"H2020","grant_number":"101034413","name":"IST-BRIDGE: International postdoctoral program"}],"oa_version":"None","month":"12","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","status":"public","type":"conference","date_published":"2022-12-01T00:00:00Z","publication_identifier":{"isbn":["9781665455190"],"issn":["0272-5428"]},"ec_funded":1,"quality_controlled":"1","page":"919-930","publisher":"Institute of Electrical and Electronics Engineers","scopus_import":"1","_id":"12432","author":[{"id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb","first_name":"Michael","last_name":"Anastos","full_name":"Anastos, Michael"}],"date_created":"2023-01-29T23:00:59Z","department":[{"_id":"MaKw"}],"article_processing_charge":"No","publication_status":"published","title":"Solving the Hamilton cycle problem fast on average","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","volume":"2022-October","year":"2022","citation":{"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>.","short":"M. Anastos, in:, 63rd Annual IEEE Symposium on Foundations of Computer Science, Institute of Electrical and Electronics Engineers, 2022, pp. 919–930.","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.","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>","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>","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>.","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."},"date_updated":"2023-08-04T09:37:56Z","external_id":{"isi":["000909382900084"]},"isi":1,"day":"01","doi":"10.1109/FOCS54457.2022.00091","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."}]}]