{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T01:49:49Z","timestamp":1787363389059,"version":"build-2736575974"},"reference-count":21,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-6721878"],"award-info":[{"award-number":["DMS-6721878"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001742","name":"United States-Israel Binational Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001742","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>We first consider the following problem. We are given a fixed perfect matching $M$ of $[n]$ and we add random edges one at a time until there is a Hamilton cycle containing $M$. We show that with high probability (w.h.p.) the hitting time for this event is the same as that for the first time there are no isolated vertices in the graph induced by the random edges. We then use this result for the following problem. We generate random edges and randomly color them black or white. A path\/cycle is said to be zebraic if the colors alternate along the path. We show that w.h.p. the hitting time for a zebraic Hamilton cycle coincides with every vertex meeting at least one edge of each color. We then consider some related problems and (partially) extend our results to multiple colors. We also briefly consider directed versions.<\/jats:p>","DOI":"10.1137\/15m1047106","type":"journal-article","created":{"date-parts":[[2018,7,10]],"date-time":"2018-07-10T15:08:06Z","timestamp":1531235286000},"page":"1585-1618","source":"Crossref","is-referenced-by-count":7,"title":["Elegantly Colored Paths and Cycles in Edge Colored Random Graphs"],"prefix":"10.1137","volume":"32","author":[{"given":"Lisa","family":"Espig","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alan","family":"Frieze","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Krivelevich","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,7,10]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"N. Alon and J. Spencer,\n                      The Probabilistic Method\n                      , 3rd ed., John Wiley & Sons, New York, 2008.","DOI":"10.1002\/9780470277331"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.37236\/1204"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20594"},{"key":"atypb4","unstructured":"B. Bolloba\u0301s,\n                      Random Graphs\n                      , 2nd ed., Cambridge University Press, Cambridge, 2001."},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548301005004"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1994.1060"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1137\/140998433"},{"key":"atypb8","first-page":"54","author":"Erdo\u0308s P.","year":"1983","journal-title":"Leipzig"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1007\/BF01894879"},{"key":"atypb10","first-page":"167","author":"Ferber A.","year":"2016","journal-title":"New York"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"A. M. Frieze and M. Karon\u0301ski,\n                      Introduction to Random Graphs\n                      , Cambridge University Press, Cambridge, 2015.","DOI":"10.1017\/CBO9781316339831"},{"key":"atypb12","doi-asserted-by":"crossref","first-page":"5","DOI":"10.37236\/2784","volume":"19","author":"Frieze A. M.","year":"2012","journal-title":"Electron. J. Combin."},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20475"},{"key":"atypb14","unstructured":"A. M. Frieze and T. \u0141uczak,\n                      Hamiltonian cycles in a class of random graphs: One step further\n                      , in Proceedings of Random Graphs '87, M. Karonski, J. Jaworski, and A. Rucinski, eds., 1990, pp. 53-59."},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(93)90054-W"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(86)90038-5"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.37236\/2708"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"S. Janson, T. \u0141uczak, and A. Rucin\u0301ski,\n                      Random Graphs\n                      , John Wiley & Sons, New York, 2000.","DOI":"10.1002\/9781118032718"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22003"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.1024"},{"key":"atypb21","unstructured":"P. Winkler,\n                      private communication\n                      , 1984."}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/15M1047106","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:58:27Z","timestamp":1787320707000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/15M1047106"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":21,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/15M1047106"],"URL":"https:\/\/doi.org\/10.1137\/15m1047106","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}