{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,9,2]],"date-time":"2023-09-02T19:08:45Z","timestamp":1693681725761},"reference-count":24,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2012,5,4]],"date-time":"2012-05-04T00:00:00Z","timestamp":1336089600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2012,9]]},"abstract":"<jats:p>Consider the random graph process where we start with an empty graph on <jats:italic>n<\/jats:italic> vertices and, at time <jats:italic>t<\/jats:italic>, are given an edge <jats:italic>e<\/jats:italic><jats:sub><jats:italic>t<\/jats:italic><\/jats:sub> chosen uniformly at random among the edges which have not appeared so far. A classical result in random graph theory asserts that w.h.p. the graph becomes Hamiltonian at time (1\/2+<jats:italic>o<\/jats:italic>(1))<jats:italic>n<\/jats:italic> log <jats:italic>n<\/jats:italic>. On the contrary, if all the edges were directed randomly, then the graph would have a directed Hamilton cycle w.h.p. only at time (1+<jats:italic>o<\/jats:italic>(1))<jats:italic>n<\/jats:italic> log <jats:italic>n<\/jats:italic>. In this paper we further study the directed case, and ask whether it is essential to have twice as many edges compared to the undirected case. More precisely, we ask if, at time <jats:italic>t<\/jats:italic>, instead of a random direction one is allowed to choose the orientation of <jats:italic>e<\/jats:italic><jats:sub><jats:italic>t<\/jats:italic><\/jats:sub>, then whether or not it is possible to make the resulting directed graph Hamiltonian at time earlier than <jats:italic>n<\/jats:italic> log <jats:italic>n<\/jats:italic>. The main result of our paper answers this question in the strongest possible way, by asserting that one can orient the edges on-line so that w.h.p. the resulting graph has a directed Hamilton cycle exactly at the time at which the underlying graph is Hamiltonian.<\/jats:p>","DOI":"10.1017\/s096354831200020x","type":"journal-article","created":{"date-parts":[[2012,5,4]],"date-time":"2012-05-04T09:32:05Z","timestamp":1336123925000},"page":"773-801","source":"Crossref","is-referenced-by-count":3,"title":["Getting a Directed Hamilton Cycle Two Times Faster"],"prefix":"10.1017","volume":"21","author":[{"given":"CHOONGBUM","family":"LEE","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"BENNY","family":"SUDAKOV","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"DAN","family":"VILENCHIK","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2012,5,4]]},"reference":[{"key":"S096354831200020X_ref21","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(76)90068-6"},{"key":"S096354831200020X_ref6","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548306007486"},{"key":"S096354831200020X_ref5","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20038"},{"key":"S096354831200020X_ref16","unstructured":"[16] Frieze A. Personal communication."},{"key":"S096354831200020X_ref23","first-page":"710","volume-title":"APPROX-RANDOM","author":"Sinclair","year":"2010"},{"key":"S096354831200020X_ref3","doi-asserted-by":"publisher","DOI":"10.1214\/10-AAP718"},{"key":"S096354831200020X_ref7","first-page":"335","volume-title":"Graph Theory and Combinatorics: Proc. Cambridge Combinatorial Conference in Honour of Paul Erd\u0151s, 1984","author":"Bollob\u00e1s","year":"1984"},{"key":"S096354831200020X_ref12","first-page":"17","article-title":"On the evolution of random graphs.","volume":"5A","author":"Erd\u0151s","year":"1960","journal-title":"Publ. Math. Inst. Hung. Acad. Sci."},{"key":"S096354831200020X_ref11","volume-title":"Graduate Texts in Mathematics","author":"Diestel","year":"2005"},{"key":"S096354831200020X_ref20","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20302"},{"key":"S096354831200020X_ref2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795288490"},{"key":"S096354831200020X_ref18","first-page":"760","article-title":"Solution of a problem of Erd\u0151s and R\u00e9nyi on Hamilton cycles in non-oriented graphs.","volume":"17","author":"Korshunov","year":"1976","journal-title":"Soviet Math. Dokl."},{"key":"S096354831200020X_ref1","doi-asserted-by":"publisher","DOI":"10.1002\/0471722154"},{"key":"S096354831200020X_ref17","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(83)90021-3"},{"key":"S096354831200020X_ref24","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-007-2163-2"},{"key":"S096354831200020X_ref13","doi-asserted-by":"publisher","DOI":"10.1007\/BF00536750"},{"key":"S096354831200020X_ref15","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(88)90037-5"},{"key":"S096354831200020X_ref4","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.1019"},{"key":"S096354831200020X_ref14","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20070"},{"key":"S096354831200020X_ref19","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20254"},{"key":"S096354831200020X_ref9","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1994.1060"},{"key":"S096354831200020X_ref10","doi-asserted-by":"publisher","DOI":"10.1002\/1098-2418(200007)16:4<369::AID-RSA6>3.0.CO;2-J"},{"key":"S096354831200020X_ref8","first-page":"430","volume-title":"Proc. 17th Annual ACM Symposium on Theory of Computing, 1985","author":"Bollob\u00e1s","year":"1985"},{"key":"S096354831200020X_ref22","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240050209"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S096354831200020X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,24]],"date-time":"2019-04-24T23:02:35Z","timestamp":1556146955000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S096354831200020X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,5,4]]},"references-count":24,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2012,9]]}},"alternative-id":["S096354831200020X"],"URL":"https:\/\/doi.org\/10.1017\/s096354831200020x","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,5,4]]}}}