Subquadratic ordered Ramsey bound for matchings of interval chromatic number two

Let M<M^< be an ordered matching on nn vertices, let K3<K^<_3 be the ordered triangle, and let χ<(M<)\chi_<(M^<) denote the interval chromatic number of M<M^<. Let r<(M<,K3<)r_<(M^<,K^<_3) be the ordered Ramsey number of M<M^< versus K3<K^<_3.

Interval-chromatic-two conjecture. There exists an ϵ>0\epsilon>0 such that, for every ordered matching M<M^< on nn vertices with χ<(M<)=2\chi_<(M^<)=2,

r<(M<,K3<)O(n2ε).r_<(M^<,K^<_3)\in O(n^{2-\varepsilon}).

This is a weaker uniform version of the preceding conjecture for interval chromatic number two. The growth rate of r<(M<,K3<)r_<(M^<,K^<_3) is not understood even in this case, so the asserted subquadratic bound remains open.

Sources & referencesView supporting material

Primary source

Martin Balko and Marian Poljak, “On ordered Ramsey numbers of matchings versus triangles”, arXiv:2305.17933 (2023).

Additional references

2 papers in this index state this conjecture (2018–2023). The statement above is taken from the most recent of them; the others are arXiv:1808.04025.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.