Nearly-linear monotone paths in edge-ordered graphs

Matija Bucić; Matthew Kwan; Alexey Pokrovskiy; Benny Sudakov; Tuan Tran; Adam Zsolt Wagner

doi:10.1007/s11856-020-2035-7

Nearly-linear monotone paths in edge-ordered graphs

Matija Bucić, Matthew Kwan, Alexey Pokrovskiy, Benny Sudakov, Tuan Tran, Adam Zsolt Wagner

Research output: Contribution to journal › Article › peer-review

6 Scopus citations

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átal and Komlós 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).

Original language	English (US)
Pages (from-to)	663-685
Number of pages	23
Journal	Israel Journal of Mathematics
Volume	238
Issue number	2
DOIs	https://doi.org/10.1007/s11856-020-2035-7
State	Published - Jul 1 2020
Externally published	Yes

All Science Journal Classification (ASJC) codes

General Mathematics

Access to Document

10.1007/s11856-020-2035-7

Cite this

@article{387c1e65f10644488b4fe4832da8f848,

title = "Nearly-linear monotone paths in edge-ordered graphs",

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{\'a}tal and Koml{\'o}s 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).",

author = "Matija Buci{\'c} and Matthew Kwan and Alexey Pokrovskiy and Benny Sudakov and Tuan Tran and Wagner, {Adam Zsolt}",

note = "Publisher Copyright: {\textcopyright} 2020, The Hebrew University of Jerusalem.",

year = "2020",

month = jul,

day = "1",

doi = "10.1007/s11856-020-2035-7",

language = "English (US)",

volume = "238",

pages = "663--685",

journal = "Israel Journal of Mathematics",

issn = "0021-2172",

publisher = "Springer New York",

number = "2",

}

TY - JOUR

T1 - Nearly-linear monotone paths in edge-ordered graphs

AU - Bucić, Matija

AU - Kwan, Matthew

AU - Pokrovskiy, Alexey

AU - Sudakov, Benny

AU - Tran, Tuan

AU - Wagner, Adam Zsolt

PY - 2020/7/1

Y1 - 2020/7/1

N2 - 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átal and Komlós 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).

AB - 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átal and Komlós 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).

UR - http://www.scopus.com/inward/record.url?scp=85087651419&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85087651419&partnerID=8YFLogxK

U2 - 10.1007/s11856-020-2035-7

DO - 10.1007/s11856-020-2035-7

M3 - Article

AN - SCOPUS:85087651419

SN - 0021-2172

VL - 238

SP - 663

EP - 685

JO - Israel Journal of Mathematics

JF - Israel Journal of Mathematics

IS - 2

ER -

Nearly-linear monotone paths in edge-ordered graphs

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this