PreprintarXiv licencearXiv
Ordered Trees with Linear Off-Diagonal Ramsey Numbers
Abstract
We characterize the following three classes of ordered trees: (1) trees T satisfying R<(T,Kn)=O(n); (2) χ-bounding trees; (3) Ramsey-good trees. In particular, we show that the first two classes coincide. The second characterization answers a question of Axenovich, Rollin and Ueckerdt, and the third resolves a problem of Balko and Poljak. In our proof, we also introduce several novel constructions of ordered graphs with sublinear independence number, giving lower bounds on R<(F,Kn) for various ordered forests F.
Related
BibTeX
@misc{gishboliner2026ordered,
title = {{Ordered Trees with Linear Off-Diagonal Ramsey Numbers}},
author = {Lior Gishboliner and Artur Kravtsov and Xiangyu Li},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.28299},
eprint = {2610.28299},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.28299},
}
RIS
TY - UNPB
TI - Ordered Trees with Linear Off-Diagonal Ramsey Numbers
AU - Lior Gishboliner
AU - Artur Kravtsov
AU - Xiangyu Li
PY - 2026
DA - 2026/10/20
PB - arXiv
DO - 10.48550/arxiv.2610.28299
UR - https://arxiv.org/abs/2610.28299
AB - We characterize the following three classes of ordered trees: (1) trees T satisfying R_<(T,K_n)=O(n); (2) χ-bounding trees; (3) Ramsey-good trees. In particular, we show that the first two classes coincide. The second characterization answers a question of Axenovich, Rollin and Ueckerdt, and the third resolves a problem of Balko and Poljak. In our proof, we also introduce several novel constructions of ordered graphs with sublinear independence number, giving lower bounds on R_<(F,K_n) for various ordered forests F.
ER -