Parameters governing acyclic digraph Ramsey growth

Open problem on parameters governing $\overrightarrow{r}_1(H)$ · arXiv:2105.02383

arXiv Informal medium confidence— first stated 2022-01-21

Authors: Jacob Fox, Xiaoyu He, Yuval Wigderson

Status partial high confidence

The source paper itself already demonstrates that bounded degree alone does not suffice for polynomial (let alone linear) oriented Ramsey numbers, constructing bounded-degree acyclic digraphs with $\overrightarrow{r}_1(H) \ge n^{\Omega(\Delta^{2/3}/\log^{5/3}\Delta)}$, while the complete characterization via natural parameters remains open. The 2025 follow-up by Bradač, Morawski, Sudakov, and Wigderson extends the linear upper bound regime to acyclic digraphs with 'graded bandwidth' (local edge structure), unifying previous results on bounded height, bounded bandwidth, and tree blowups. However, the full picture is explicitly acknowledged as far from resolved: a complete analogue of the degeneracy-plus-vertex-count framework for undirected graphs has not been found for the directed setting.

Cited literature (1)

partial Ramsey numbers of digraphs with local edge structure (2025)

Domagoj Bradač, Patryk Morawski, Benny Sudakov, Yuval Wigderson · arXiv preprint · arXiv:2509.05055

Proves linear oriented Ramsey numbers for bounded-degree acyclic digraphs with graded bandwidth (local edge structure), extending the class of digraphs known to have linear $\overrightarrow{r}_1(H)$ and contributing a structural parameter candidate, while noting the full characterization of which parameters govern the growth order remains far from complete.

Reviewer notes. The open problem has two parts: (1) polynomial vs. super-polynomial for bounded-degree digraphs — partially answered, as super-polynomial examples exist in the source paper itself; (2) identifying the right structural parameter — partially addressed by 'multiscale complexity' (source paper) and 'graded bandwidth' (2509.05055), but no complete characterisation is known. The conjecture is best described as open with substantial partial progress.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Informal. What natural parameters (analogous to degeneracy and vertex count for undirected graphs) determine the growth order of $\overrightarrow{r}_1(H)$ for acyclic digraphs? In particular, is $\overrightarrow{r}_1(H)$ polynomial or super-polynomial in $n$ when $H$ has bounded degree?

Context

For undirected graphs, the Ramsey number is governed by degeneracy and vertex count (Conlon–Fox–Sudakov conjecture, verified up to a $\log^2 d$ factor). The authors introduce the notion of 'multiscale complexity' as a candidate parameter for the directed setting, but stress that the full picture remains unresolved and deserves further research.

Notes. Stated as prose in the introduction (no formal theorem environment); also reiterated in the conclusion.

Source paper

Ramsey numbers of sparse digraphs
Jacob Fox, Xiaoyu He, Yuval Wigderson · 2022-01-21
https://arxiv.org/abs/2105.02383 PDF source