10 problems

Kucheriya–Tardos conjecture. The stronger bound

Consider edge-ordered acyclic patterns with order chromatic number $2$, and their extremal functions. Gerbner–et al. polylogarithmic conjecture. Every such extremal function should…

Consider forbidden patterns in edge-ordered graphs, and let the order chromatic number be the analogue of interval chromatic number for this setting. Gerbner–et al. conjecture. The…

Let $H$ be an acyclic edge-ordered graph of order-chromatic number $2$, and let $\operatorname{Ex}(H,n)$ denote its extremal function. Kucheriya–Tardos conjecture. There is a const…

For an edge-ordered complete graph on $n$ vertices, consider the maximum length of a monotone increasing path that must appear. Chvátal–Komlós conjecture. This quantity is linear i…

An edge-ordered graph is a graph whose edges are equipped with a linear ordering. A graph is $d$-degenerate if every induced subgraph has a vertex of degree at most $d$. For an edg…

An edge-ordered graph is a graph whose edges are equipped with a linear ordering. A graph is $d$-degenerate if every induced subgraph has a vertex of degree at most $d$. For an edg…

Lavrov–Loh random-order Hamiltonian-path conjecture. With probability tending to $1$ as $n$ tends to infinity, a uniformly random edge-ordering of $K_n$ contains a monotone Hamilto…

Chvátal–Komlós altitude conjecture. The parameter $\alpha(K_n)$ has order of magnitude $n$; equivalently, $\alpha(K_n)=\Theta(n)$.

Growth conjecture for $f(K_n)$. The lower bound