zbMATH — the first resource for mathematics

Nearly-linear monotone paths in edge-ordered graphs. (English) Zbl 1447.05113
Summary: How long is a monotone path one can always find in any edge-ordering of the complete graph \(K_n\)? This appealing question was first asked by V. Chvátal and J. Komlós [Can. Math. Bull. 14, 151–157 (1971; Zbl 0214.23503)], and has since attracted the attention of many researchers, inspiring a variety of related problems. The prevailing conjecture is that one can always find a monotone path of linear length, but until now the best known lower bound was \(n^{2/3-o(1)}\). In this paper we almost close this gap, proving that any edge-ordering of the complete graph contains a monotone path of length \(n^{1-o(1)}\).
05C38 Paths and cycles
Full Text: DOI
[1] Alon, N., Problems and results in extremal combinatorics. I, Discrete Mathematics, 273, 31-53 (2003) · Zbl 1033.05060
[2] Alon, N., Problems and results in extremal combinatorics. II, Discrete Mathematics, 308, 4460-4472 (2008) · Zbl 1152.05053
[3] Alon, N.; Friedland, S.; Kalai, G., Regular subgraphs of almost regular graphs, Journal of Combinatorial Theory. Series B, 37, 79-91 (1984) · Zbl 0527.05059
[4] Alon, N.; Krivelevich, M.; Sudakov, B., Large nearly regular induced subgraphs, SIAM Journal on Discrete Mathematics, 22, 1325-1337 (2008) · Zbl 1229.05207
[5] Angel, O.; Ferber, A.; Sudakov, B.; Tassion, V., Long monotone trails in random edgelabelings of random graphs, Combinatorics, Probability and Computing, 29, 22-30 (2020) · Zbl 07186374
[6] Boucheron, S.; Lugosi, G.; Massart, P., Concentration Inequalities (2013), Oxford: Oxford University Press, Oxford
[7] Burger, A. P.; Cockayne, E. J.; Mynhardt, C. M., Altitude of small complete and complete bipartite graphs, Australasian Journal of Combinatorics, 31, 167-177 (2005) · Zbl 1080.05046
[8] Calderbank, A. R.; Chung, F. R K.; Sturtevant, D. G., Increasing sequences with nonzero block sums and increasing paths in edge-ordered graphs, Discrete Mathematics, 50, 15-28 (1984) · Zbl 0542.05058
[9] Chvátal, V.; Komlós, J., Some combinatorial theorems on monotonicity, Canadian Mathematical Bulletin, 14, 151-157 (1971) · Zbl 0214.23503
[10] Cockayne, E. J.; Mynhardt, C. M., Altitude of K_3,n, Journal of Combinatorial Mathematics and Combinatorial Computing, 52, 143-157 (2005) · Zbl 1073.05062
[11] J. De Silva, T. Molla, F. Pfender, T. Retter and M. Tait, Increasing paths in edge-ordered graphs: the hypercube and random graph, Electronic Journal of Combinatorics 23 (2016), Paper bo. 2.15. · Zbl 1335.05150
[12] Diestel, R., Graph Theory (2017), Berlin: Springer, Berlin
[13] Erdős, P., On some extremal problems in graph theory, Israel Journal of Mathematics, 3, 113-116 (1965) · Zbl 0134.43403
[14] Erdős, P., On the combinatorial problems which I would most like to see solved, Combinatorica, 1, 25-42 (1981) · Zbl 0486.05001
[15] Graham, R. L.; Kleitman, D. J., Increasing paths in edge ordered graphs, Periodica Mathematica Hungarica, 3, 141-148 (1973) · Zbl 0243.05116
[16] P. Horn and D. West, Increasing paths in edge ordered graphs (1971), https://faculty.math.illinois.edu/ west/regs/increasing.html.
[17] Lavrov, M.; Loh, P-S, Increasing Hamiltonian paths in random edge orderings, Random Structures & Algorithms, 48, 588-611 (2016) · Zbl 1338.05150
[18] Martinsson, A., Most edge-orderings of K_n have maximal altitude, Random Structures & Algorithms, 54, 559-585 (2019) · Zbl 1414.05268
[19] Milans, K. G., Monotone paths in dense edge-ordered graphs, Journal of Combinatorics, 8, 423-437 (2017) · Zbl 1370.05111
[20] Mynhardt, C. M.; Burger, A. P.; Clark, T. C.; Falvai, B.; Henderson, N. D R., Altitude of regular graphs with girth at least five, Discrete Mathematics, 294, 241-257 (2005) · Zbl 1062.05131
[21] Pyber, L., Regular subgraphs of dense graphs, Combinatorica, 5, 347-349 (1985) · Zbl 0596.05035
[22] Pyber, L.; Rödl, V.; Szemerédi, E., Dense graphs without 3-regular subgraphs, Journal of Combinatorial Theory. Series B, 63, 41-54 (1995) · Zbl 0822.05037
[23] Roditty, Y.; Shoham, B.; Yuster, R., Monotone paths in edge-ordered sparse graphs, Discrete Mathematics, 226, 411-417 (2001) · Zbl 0961.05040
[24] V. Rödl, The dimension of a graph and generalized Ramsey theorems, Master’s thesis, Charles University, 1973.
[25] Yuster, R., Large monotone paths in graphs with bounded degree, Graphs and Combinatorics, 17, 579-587 (2001) · 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.