Upper bounds for ordered Ramsey numbers of forests and bounded-degree graphs
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)})$.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.38828
curl -X POST /api/v1/records/arxiv/2609.38828/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.38828/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'