Track new results across pure and applied mathematics.
Search papers, labs, and topics across Lattice.
We establish new upper bounds for ordered Ramsey numbers of forests and bounded-degree graphs. For forests, we show $R_{<}(F,F)=O(n^{1+\lceil\logχ_{<}(F)\rceil})$, resolving a question by Geneson et al. concerning the relationship between interval chromatic number and Ramsey properties. Additionally, for fixed ordered graphs $H$ with bounded maximum degree and interval chromatic number, we prove $R_{<}(H,K_n)=O_H(n^{f(Δ,k)})$, providing a general bound for a broad class of graphs.
Ordered Ramsey numbers for forests are tightly linked to their interval chromatic number, with $R_{<}(F,F)$ growing polynomially with a degree dependent on $\log \chi_{<}(F)$.
We prove the following two upper bounds for ordered Ramsey numbers: (1) Every ordered forest $F$ on $n$ vertices satisfies $R_{<}(F,F)=O(n^{1+\lceil\logχ_{<}(F)\rceil})$. This in particular answers a question of Geneson, Holmes, Liu, Neidinger, Pehova and Wass. (2) There is a function $f$ such that, for every fixed ordered graph $H$ with maximum degree at most $Δ$ and interval chromatic number at most $k$, it holds that $R_{<}(H,K_n)=O_H(n^{f(Δ,k)})$.