Long Increasing Paths in Edge-Ordered Graphs

Definitions and mathematical statement

An edge ordering of a finite graph $G=(V,E)$ is a strict total order $\prec$ on $E$. Write $n=|V|$ and $m=e(G)=|E|$. An increasing path of length $\ell$ consists of distinct vertices $v_0,\ldots,v_\ell$ such that $v_{i-1}v_i\in E$ for $1\le i\le\ell$ and \[ v_0v_1\prec v_1v_2\prec\cdots\prec v_{\ell-1}v_\ell. \] Thus length counts edges; a single vertex gives a path of length zero.

The supplied record does not explicitly specify whether graphs are finite, simple, and undirected. Subject to confirming this conventional interpretation, and restricting to $n\ge1$ so that the density is defined, the question is: do there exist absolute constants $\varepsilon>0$ and $c>0$ such that, for every finite simple undirected graph $G$ with at least one vertex and every strict total ordering of its edges, there is an increasing path of length $\ell$ satisfying \[ \ell\ge c\left(\frac{m}{n}\right)^{1/2+\varepsilon}? \] The constants must be independent of the graph and its edge ordering. This makes explicit the uniform interpretation of the source's $\Omega$-notation. The parameter $m/n$ is half the average degree. If $m=0$, the bound is zero and a single vertex suffices. The graph with no vertices is outside this formulation because $m/n$ is undefined.

The graph conventions and the edge-count convention for path length require confirmation against the source. The supplied registry labels the problem open and its statement corrected_verified; these are supplied curation labels, not independent mathematical verification.

Short English statement

Is there a fixed positive improvement over the square-root exponent such that every edge-ordered graph has an increasing path whose length is at least a universal constant times $(e(G)/|V(G)|)^{1/2+\varepsilon}$? The explicit formulation uses finite simple undirected graphs with at least one vertex, pending confirmation of these unstated source conventions.

Sources

• Local UnsolvedMath registry, supplied complete record for permanent ID $30004135$, titled "Long Increasing Paths in Edge-Ordered Graphs," source problem code catalogue entry, in the Oberwolfach Reports Open Problems collection. The record gives proposed year 2019 and names no proposer. Its statement-verification note says that mathematical content was preserved while notation, typography, and sentence structure were repaired for publication; this claim is supplied metadata.
• Supplied report citation: Combinatorics, Probability and Computing (2020), Oberwolfach Reports, pp. 1113--1189, DOI 10.4171/owr/2019/19. https://doi.org/10.4171/owr/2019/19. The background describes the collection as drawn from reports documenting mathematical workshops and their open-problem discussions. No page locating this particular problem within the report is supplied.
• Supplied literature reference, attributed to Bucic--Kwan--Pokrovskiy--Sudakov--Tran--Wagner: https://arxiv.org/abs/1809.01468.
• Supplied literature reference labeled "Published paper": https://people.math.ethz.ch/~sudakovb/monotone-path-complete-graph.pdf.
• Literature assessment dated exactly 2026-08-22: the supplied curation labels the problem open and states that nearly linear monotone paths are proved for complete graphs and reasonably dense edge-ordered graphs, while the fixed-average-degree sparse regime in the stated problem remains unresolved. This is supplied dated curation derived from the OWR material, not an independently verified assessment. Its time-sensitive status and cited claims require independent verification.