Nearly-linear monotone paths in edge-ordered graphs

DOI10.1007/S11856-020-2035-7MaRDI QIDQ2200054zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 15 September 2020

Published in Israel Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1809.01468

Mathematics Subject Classification ID

Paths and cycles (05C38)

Abstract: How long a monotone path can one always find in any edge-ordering of the complete graph $K_n$? This appealing question was first asked by Chv'atal and Koml'os in 1971, 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)}$.

Recommendations

• Monotone paths in dense edge-ordered graphs
• A monotone path in an edge-ordered graph
• Monotone paths in edge-ordered sparse graphs
• Long monotone trails in random edge-labellings of random graphs
• Non-crossing monotone paths and binary trees in edge-ordered complete geometric graphs

Cites work

• Altitude of regular graphs with girth at least five
• Concentration inequalities. A nonasymptotic theory of independence
• Dense graphs without 3-regular subgraphs
• scientific article; zbMATH DE number 2147937 (Why is no real title available?)
• scientific article; zbMATH DE number 2174618 (Why is no real title available?)
• scientific article; zbMATH DE number 6737879 (Why is no real title available?)
• Increasing Hamiltonian paths in random edge orderings
• Increasing paths in edge ordered graphs
• Increasing paths in edge-ordered graphs: the hypercube and random graph
• Increasing sequences with nonzero block sums and increasing paths in edge-ordered graphs
• Large monotone paths in graphs with bounded degree
• Large Nearly Regular Induced Subgraphs
• Long monotone trails in random edge-labellings of random graphs
• Monotone paths in dense edge-ordered graphs
• Monotone paths in edge-ordered sparse graphs
• Most edge-orderings of \(K_{n}\) have maximal altitude
• On some extremal problems in graph theory
• On the combinatorial problems which I would most like to see solved
• Problems and results in extremal combinatorics. I.
• Problems and results in extremal combinatorics. II
• Regular subgraphs of almost regular graphs
• Regular subgraphs of dense graphs
• Some Combinatorial Theorems on Monotonicity

Cited in

(20)

• A monotone path in an edge-ordered graph
• Monotone paths in edge-ordered sparse graphs
• Erdős-Hajnal-type results for monotone paths
• Increasing paths in countable graphs
• Non-crossing monotone paths and binary trees in edge-ordered complete geometric graphs
• Monotone paths in dense edge-ordered graphs
• Turán problems for edge-ordered graphs
• On edge-ordered Ramsey numbers
• Long monotone trails in random edge-labellings of random graphs
• Most edge-orderings of \(K_{n}\) have maximal altitude
• Finding monotone paths in edge-ordered graphs
• Sharp Thresholds in Random Simple Temporal Graphs
• Resolution of the Erdős–Sauer problem on regular subgraphs
• Tiling edge-ordered graphs with monotone paths and other structures
• Cycles with many chords
• Nearly Hamilton cycles in sublinear expanders and applications
• Tiling problems in edge-ordered graphs (extended abstract)
• Edge-disjoint cycles with the same vertex set
• Regular subgraphs at every density
• Increasing sequences with nonzero block sums and increasing paths in edge-ordered graphs

This page was built for publication: Nearly-linear monotone paths in edge-ordered graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2200054)