Increasing Paths in Edge-Ordered Graphs: The Hypercube and Random Graph

Abstract

An edge-ordering of a graph $G=(V,E)$ is a bijection $\phi:E\to\{1,2,\ldots,|E|\}$. Given an edge-ordering, a sequence of edges $P=e_1,e_2,\ldots,e_k$ is an increasing path if it is a path in $G$ which satisfies $\phi(e_i)<\phi(e_j)$ for all $i<j$. For a graph $G$, let $f(G)$ be the largest integer $\ell$ such that every edge-ordering of $G$ contains an increasing path of length $\ell$. The parameter $f(G)$ was first studied for $G=K_n$ and has subsequently been studied for other families of graphs. This paper gives bounds on $f$ for the hypercube and the random graph $G(n,p)$.