Nearly-linear monotone paths in edge-ordered graphs
- PDF / 302,470 Bytes
- 23 Pages / 429.408 x 636.768 pts Page_size
- 0 Downloads / 171 Views
NEARLY-LINEAR MONOTONE PATHS IN EDGE-ORDERED GRAPHS BY
´ Matija Bucic Department of Mathematics, ETH Z¨ urich, 8092 Zurich, Switzerland e-mail: [email protected] AND
Matthew Kwan∗ Department of Mathematics, Stanford University, CA 94305, USA e-mail: [email protected] AND
Alexey Pokrovskiy Department of Economics, Mathematics, and Statistics, Birkbeck University of London, London WC1E 7HX, UK e-mail: [email protected] AND
Benny Sudakov∗∗ Department of Mathematics, ETH Z¨ urich, 8092 Zurich, Switzerland e-mail: [email protected] AND
Tuan Tran† School of Applied Mathematics and Informatics Hanoi University of Science and Technology, Hanoi e-mail: [email protected] AND
Adam Zsolt Wagner Department of Mathematics, ETH Z¨ urich, 8092 Zurich, Switzerland e-mail: [email protected] ∗ Research supported in part by SNSF project 178493. ∗∗ Research supported in part by SNSF grant 200021-175573. † Research supported by the Humboldt Research Foundation.
Received September 4, 2018 and in revised form May 1, 2019
1
´ ET AL. M. BUCIC
2
Isr. J. Math.
ABSTRACT
How long a monotone path can one always find in any edge-ordering of the complete graph Kn ? 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 n2/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 n1−o(1) .
1. Introduction An edge-ordering of a graph G is a total order ≤G of the edge set E(G). A path P in G is said to be monotone if the consecutive edges of P form a monotone sequence with respect to ≤G . In 1971, Chv´atal and Koml´ os [9] asked for the length of the longest monotone path one can guarantee in any edge-ordering of the complete n-vertex graph Kn . To be precise, let f (Kn ) be the maximum such that every edge-ordering of Kn has a monotone path of length . What is the value of f (Kn ), as a function of n? This question was originally motivated by an analogous problem for directed graphs, which is closely related to both of the celebrated theorems of Erd˝os and Szekeres concerning convex subsets of points in the plane and concerning monotone subsequences of sequences of real numbers. Although the question of Chv´ atal and Koml´ os sounds rather innocent, it has turned out to be quite challenging even to understand the order of magnitude of f (Kn ), and progress on this problem over the years has been rather sparse. The first nontrivial results were proved by Graham and Kleitman [15], who √ showed that there is always a monotone path of length Ω( n). They also constructed an edge-ordering permitting no monotone path longer than (3/4)n. √ That is, Ω( n) ≤ f (Kn ) ≤ (3/4)n. Apart from some results for small values of n (see [7]), until recently the only improvem
Data Loading...
