PreprintarXiv licencearXiv
Upper bounds for ordered Ramsey numbers of forests and bounded-degree graphs
Abstract
We prove the following two upper bounds for ordered Ramsey numbers: (1) Every ordered forest F on n vertices satisfies R<(F,F)=O(n1+⌈logχ<(F)⌉). 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,Kn)=OH(nf(Δ,k)).
Related
- Ordered Ramsey numbers of 3-uniform hypergraphs with bounded weak degeneracy
- New results on cyclic and ordered Ramsey numbers
- Ordered Trees with Linear Off-Diagonal Ramsey Numbers
- Spanning Even Linear Forests with Isolated Edges Share the Anti-Ramsey Numbers of Perfect Matchings
- A General Upper Bound on Multicolor Ordered Ramsey Numbers
BibTeX
@misc{gishboliner2026upper,
title = {{Upper bounds for ordered Ramsey numbers of forests and bounded-degree graphs}},
author = {Lior Gishboliner and Xiangyu Li},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.38828},
eprint = {2609.38828},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.38828},
}
RIS
TY - UNPB
TI - Upper bounds for ordered Ramsey numbers of forests and bounded-degree graphs
AU - Lior Gishboliner
AU - Xiangyu Li
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2609.38828
UR - https://arxiv.org/abs/2609.38828
AB - 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+⌈logχ_<(F)⌉). 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)).
ER -