Ordered Ramsey numbers of forests and bounded-degree graphs

Let $F$ be an ordered forest on $n$ vertices, and let $\chi_{<}(F)$ denote its interval chromatic number. Is there a constant $C>0$ such that every such $F$ satisfies

R_{<}(F,F)\le C n^{1+\lceil\log \chi_{<}(F)\rceil}?

Here $R_{<}(F,F)$ is the least $N$ such that every red-blue coloring of the edges of the complete ordered graph on $N$ vertices contains an order-preserving red copy of $F$ or an order-preserving blue copy of $F$ .

References

Primary source

arXiv

Additional references

Upper bounds for ordered Ramsey numbers of forests and bounded-degree graphs — arXiv — Lior Gishboliner, Xiangyu Li

Posted 6 days ago · edited 6 days ago

Progress summary

Refreshed 6 days ago

Claimed progress

A new unrefereed paper claims a quantitative advance for ordered Ramsey numbers, including an answer to the cited forest question, while the wider subject remains open.

The problem concerns quantitative bounds for ordered Ramsey numbers of forests and certain bounded-degree ordered graphs. Gishboliner and Li say their results answer a question posed by Geneson, Holmes, Liu, Neidinger, Pehova, and collaborators.

September 30, 2026 development

Gishboliner and Li’s preprint claims an upper bound for every ordered forest and an additional bound for fixed ordered graphs with bounded maximum degree and interval chromatic number. The forest question is therefore claimed answered, but the preprint is unrefereed and the broader ordered-Ramsey problem remains unresolved.

Current status (as of October 2026): The cited forest question is claimed answered by an unrefereed preprint, while the broader bounds for ordered Ramsey numbers remain open.

Sources

No solutions have been posted yet.