{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,29]],"date-time":"2025-12-29T11:33:52Z","timestamp":1767008032640,"version":"build-2065373602"},"reference-count":16,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2019,10,8]],"date-time":"2019-10-08T00:00:00Z","timestamp":1570492800000},"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":[[2020,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Given a graph <jats:italic>G<\/jats:italic> and a bijection <jats:italic>f<\/jats:italic> : <jats:italic>E<\/jats:italic>(<jats:italic>G<\/jats:italic>) \u2192 {1, 2,\u2026,<jats:italic>e<\/jats:italic>(<jats:italic>G<\/jats:italic>)}, we say that a trail\/path in <jats:italic>G<\/jats:italic> is <jats:italic>f<\/jats:italic>-<jats:italic>increasing<\/jats:italic> if the labels of consecutive edges of this trail\/path form an increasing sequence. More than 40 years ago Chv\u00e1tal and Koml\u00f3s raised the question of providing worst-case estimates of the length of the longest increasing trail\/path over all edge orderings of <jats:italic>K<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>. The case of a trail was resolved by Graham and Kleitman, who proved that the answer is <jats:italic>n<\/jats:italic>-1, and the case of a path is still wide open. Recently Lavrov and Loh proposed studying the average-case version of this problem, in which the edge ordering is chosen uniformly at random. They conjectured (and Martinsson later proved) that such an ordering with high probability (w.h.p.) contains an increasing Hamilton path.<\/jats:p><jats:p>In this paper we consider the random graph <jats:italic>G<\/jats:italic> = <jats:italic>G<jats:sub>n,p<\/jats:sub><\/jats:italic> with an edge ordering chosen uniformly at random. In this setting we determine w.h.p. the asymptotics of the number of edges in the longest increasing trail. In particular we prove an average-case version of the result of Graham and Kleitman, showing that the random edge ordering of <jats:italic>K<jats:sub>n<\/jats:sub><\/jats:italic> has w.h.p. an increasing trail of length (1-<jats:italic>o<\/jats:italic>(1))<jats:italic>en<\/jats:italic>, and that this is tight. We also obtain an asymptotically tight result for the length of the longest increasing path for random Erd\u0151s-Renyi graphs with <jats:italic>p<\/jats:italic> = <jats:italic>o<\/jats:italic>(1).<\/jats:p>","DOI":"10.1017\/s096354831900018x","type":"journal-article","created":{"date-parts":[[2019,10,8]],"date-time":"2019-10-08T07:41:29Z","timestamp":1570520489000},"page":"22-30","source":"Crossref","is-referenced-by-count":5,"title":["Long Monotone Trails in Random Edge-Labellings of Random Graphs"],"prefix":"10.1017","volume":"29","author":[{"given":"Omer","family":"Angel","sequence":"first","affiliation":[]},{"given":"Asaf","family":"Ferber","sequence":"additional","affiliation":[]},{"given":"Benny","family":"Sudakov","sequence":"additional","affiliation":[]},{"given":"Vincent","family":"Tassion","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2019,10,8]]},"reference":[{"key":"S096354831900018X_ref9","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20803"},{"key":"S096354831900018X_ref7","doi-asserted-by":"publisher","DOI":"10.1007\/BF02018469"},{"key":"S096354831900018X_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/s003730170031"},{"key":"S096354831900018X_ref15","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1956-0079851-X"},{"key":"S096354831900018X_ref2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814068"},{"key":"S096354831900018X_ref11","first-page":"423","article-title":"Monotone paths in dense edge-ordered graphs","volume":"8","author":"Milans","year":"2017","journal-title":"J. Comb."},{"key":"S096354831900018X_ref5","doi-asserted-by":"publisher","DOI":"10.4153\/CMB-1971-028-8"},{"key":"S096354831900018X_ref6","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792237541"},{"key":"S096354831900018X_ref14","doi-asserted-by":"publisher","DOI":"10.37236\/5036"},{"key":"S096354831900018X_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(84)90031-1"},{"key":"S096354831900018X_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(03)00227-9"},{"key":"S096354831900018X_ref13","unstructured":"[13] R\u00f6dl, V. (1973) Master\u2019s thesis, Charles University."},{"key":"S096354831900018X_ref3","unstructured":"[3] Buci\u0107, M. , Kwan, M. , Pokrovskiy, A. , Sudakov, B. , Tran, T. and Wagner, A. (2018) Nearly-linear monotone paths in edge-ordered graphs. Israel J. Math, to appear. arXiv:1809.01468"},{"key":"S096354831900018X_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(00)00174-6"},{"key":"S096354831900018X_ref8","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20592"},{"key":"S096354831900018X_ref10","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1177004832"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S096354831900018X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,14]],"date-time":"2020-01-14T10:57:05Z","timestamp":1578999425000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S096354831900018X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,8]]},"references-count":16,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["S096354831900018X"],"URL":"https:\/\/doi.org\/10.1017\/s096354831900018x","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"type":"print","value":"0963-5483"},{"type":"electronic","value":"1469-2163"}],"subject":[],"published":{"date-parts":[[2019,10,8]]}}}