An edge-ordering of a graph $G=(V,E)$ is a bijection $phi:Eto{1,2,...,|E|}$. Given an edge-ordering, a sequence of edges $P=e_1,e_2,...,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)$.
Download