pipette
ESEspañol

Ordered Trees with Linear Off-Diagonal Ramsey Numbers

Lior Gishboliner, Artur Kravtsov, Xiangyu Li

Preprint

In the authors' words

We characterize the following three classes of ordered trees: (1) trees satisfying ; (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 for various ordered forests .

Main resultThe abstract does not state a limitation.

Appeared: Wednesday, October 21. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 35 pages, 4 figures