pipette
ENEnglish

Ordered Trees with Linear Off-Diagonal Ramsey Numbers

Lior Gishboliner, Artur Kravtsov, Xiangyu Li

Preprint

En palabras de los autores

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 .

Resultado principalEl resumen no menciona limitaciones.

Apareció: miércoles, 21 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 35 pages, 4 figures