Increasing paths in edge-ordered graphs: the hypercube and random graph (Q281608)

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