← All problems

Axenovich–Rollin–Ueckerdt and Balko–Poljak ordered-tree problems

Determine precisely which ordered trees TT satisfy R<(T,Kn)=O(n)R_{<}(T,K_n)=O(n); equivalently, characterize the ordered trees TT for which there exists a constant CT<∞C_T<\infty such that R<(T,Kn)≤CTnR_{<}(T,K_n)\le C_T n for every integer n≥1n\ge 1.

Equivalent formulations
  1. Characterize the Ramsey-good ordered trees; the cited preprint claims that this class coincides with the ordered trees satisfying R<(T,Kn)=O(n)R_{<}(T,K_n)=O(n).

    source: Ordered Trees with Linear Off-Diagonal Ramsey Numbers

  2. Characterize the ordered trees that are χ\chi-bounding; the cited preprint claims that this class coincides with the class of ordered trees satisfying R<(T,Kn)=O(n)R_{<}(T,K_n)=O(n).

    source: Ordered Trees with Linear Off-Diagonal Ramsey Numbers

References

Source: arXiv

Progress summary

Refreshed
Open · solution reported

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, χ\chi-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 ∣V(H)∣−1≤f≺(H)≤2∣V(H)∣−3|V(H)|-1\le f_{\prec}(H)\le 2^{|V(H)|-3} (2016).
  • For crossing ordered graphs, the boundedness question was reduced to monotonically alternating trees (2016).
  • Ordered Ramsey work introduced nn-goodness, found a new class of ordered trees good for every nn, and established r<(NMm<,Kn<)=Θ(mn)r_{<}(NM_m^{<},K_n^{<})=\Theta(mn) (2022).

October 2026 claimed resolution

A preprint by Lior Gishboliner, Artur Kravtsov, and Xiangyu Li claims equivalence of the linear-Ramsey and χ\chi-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.

Sources

Solutions 0

No solutions have been posted yet.