Axenovich–Rollin–Ueckerdt and Balko–Poljak ordered-tree problems
Determine precisely which ordered trees satisfy ; equivalently, characterize the ordered trees for which there exists a constant such that for every integer .
Equivalent formulations
Characterize the Ramsey-good ordered trees; the cited preprint claims that this class coincides with the ordered trees satisfying .
source: Ordered Trees with Linear Off-Diagonal Ramsey Numbers
Characterize the ordered trees that are -bounding; the cited preprint claims that this class coincides with the class of ordered trees satisfying .
source: Ordered Trees with Linear Off-Diagonal Ramsey Numbers
References
- Ordered Trees with Linear Off-Diagonal Ramsey Numbers — arXiv — Lior Gishboliner, Artur Kravtsov, Xiangyu Li
Source: arXiv
Progress summary
A new unrefereed preprint claims to settle the ordered-tree questions, but the claim has not been independently checked.
The problem concerns structural characterizations of ordered trees associated with linear Ramsey numbers, -bounding, and Ramsey goodness. The latest preprint claims equivalence of the relevant classes and a resolution of the cited Ramsey-goodness problem.
Known results
- For non-crossing ordered graphs, bounded chromatic number is characterized by forests containing no bonnet; connected cases satisfy (2016).
- For crossing ordered graphs, the boundedness question was reduced to monotonically alternating trees (2016).
- Ordered Ramsey work introduced -goodness, found a new class of ordered trees good for every , and established (2022).
October 2026 claimed resolution
A preprint by Lior Gishboliner, Artur Kravtsov, and Xiangyu Li claims equivalence of the linear-Ramsey and -bounding classes and says it resolves the Ramsey-goodness problem. The supplied scans found no independent assessment, correction, withdrawal, or retraction.
Current status (as of October 2026): The preprint claims a complete resolution, but that resolution remains unverified; the earlier literature establishes only partial characterizations and bounds.
Solutions 0
No solutions have been posted yet.