zbMATH — the first resource for mathematics

Long monotone trails in random edge-labellings of random graphs. (English) Zbl 07186374
Summary: Given a graph \(G\) and a bijection \(f : E(G) \rightarrow \{1, 2,\ldots, e(G)\}\), we say that a trail/path in \(G\) is \(f- increasing\) if the labels of consecutive edges of this trail/path form an increasing sequence. More than 40 years ago Chvátal and Komlós raised the question of providing worst-case estimates of the length of the longest increasing trail/path over all edge orderings of \(K_n \). The case of a trail was resolved by Graham and Kleitman, who proved that the answer is \(n-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. In this paper we consider the random graph \(G = G_{n,p }\) 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 \(K_n\) has w.h.p. an increasing trail of length \((1-o(1)) en \), and that this is tight. We also obtain an asymptotically tight result for the length of the longest increasing path for random Erdős-Renyi graphs with \(p = o(1)\).

05C38 Paths and cycles
05C80 Random graphs (graph-theoretic aspects)
Full Text: DOI
[1] Alon, N. (2003) Problems and results in extremal combinatorics, I. Discrete Math.27331-53.
[2] Bollobás, B. (2001) Random Graphs, Vol. 73 of Cambridge Studies in Advanced Mathematics, Cambridge University Press.
[3] Bucić, 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
[4] Calderbank, A. R., Chung, F. R. and Sturtevant, D. G. (1984) Increasing sequences with nonzero block sums and increasing paths in edge-ordered graphs. Discrete Math.5015-28. · Zbl 0542.05058
[5] Chvátal, V. and Komlós, J. (1971) Some combinatorial theorems on monotonicity. Canad. Math. Bull.14151-157. · Zbl 0214.23503
[6] Devroye, L. and Reed, B. (1995) On the variance of the height of random binary search trees. SIAM J. Comput.241157-1162. · Zbl 0845.68027
[7] Graham, R. L. and Kleitman, D. J. (1973) Increasing paths in edge ordered graphs. Periodica Math. Hungar.3141-148. · Zbl 0243.05116
[8] Lavrov, M. and Loh, P.-S. (2016) Increasing Hamiltonian paths in random edge orderings. Random Struct. Algorithms.48588-611. · Zbl 1338.05150
[9] Martinsson, A. (2019) Most edge-orderings of K_n have maximal altitude. Random Struct. Algorithms. 54559-585. arXiv:1605.07204 · Zbl 1414.05268
[10] Mcdiarmid, C. (1995) Minimal positions in a branching random walk. Ann. Appl. Probab.5128-139. · Zbl 0836.60089
[11] Milans, K. G. (2017) Monotone paths in dense edge-ordered graphs. J. Comb.8423-437. arXiv:1509.02143 · Zbl 1370.05111
[12] Roditty, Y., Shoham, B. and Yuster, R. (2001) Monotone paths in edge-ordered sparse graphs. Discrete Math.226411-417. · Zbl 0961.05040
[13] Rödl, V. (1973) Master’s thesis, Charles University.
[14] De Silva, J., Molla, T., Pfender, F., Retter, T. and Tait, M. (2016) Increasing paths in edge-ordered graphs: The hypercube and random graph. Electron. J. Combin. 23 P2.15. · Zbl 1335.05150
[15] Spitzer, F. (1956) A combinatorial lemma and its application to probability theory. Trans. Amer. Math. Soc.82323-339. · Zbl 0071.13003
[16] Yuster, R. (2001) Large monotone paths in graphs with bounded degree. Graphs Combin.17579-587. · Zbl 1010.05044
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.