Ordered Trees with Linear Off-Diagonal Ramsey Numbers
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