Title	Nearly-linear monotone paths in edge-ordered graphs
Creator	Bucic, Matija
Publisher	Banff International Research Station for Mathematical Innovation and Discovery
Date Issued	2019-09-04T10:40
Description	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 Chvatal and Komlos 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)}$. We almost close this gap, proving that any edge-ordering of the complete graph contains a monotone path of length $n^{1-o(1)}$. This is joint work with Matthew Kwan, Alexey Pokrovskiy, Benny Sudakov, Tuan Tran and Adam Wagner.
Extent	35.0 minutes
Subject	Mathematics; Combinatorics; Probability theory and stochastic processes
Type	Moving Image
File Format	video/mp4
Language	eng
Notes	Author affiliation: ETH Zurich
Series	BIRS Workshop Lecture Videos (Banff, Alta)
Date Available	2020-03-03
Provider	Vancouver : University of British Columbia Library
Rights	Attribution-NonCommercial-NoDerivatives 4.0 International
DOI	10.14288/1.0388838
URI	http://hdl.handle.net/2429/73667
Affiliation	Non UBC
Peer Review Status	Unreviewed
Scholarly Level	Graduate
Rights URI	http://creativecommons.org/licenses/by-nc-nd/4.0/
Aggregated Source Repository	DSpace

Open Collections

BIRS Workshop Lecture Videos