← All problems

Rohatgi's almost-every matching conjecture for ordered Ramsey numbers

4 years old · traced to

Let M<M^< be an ordered matching on nn vertices with interval chromatic number hihi, and let K3<K^<_3 be the ordered triangle. For a positive integer hihi, there is a constant psilon(hi)>0psilon(hi)>0 such that

R<(M<,K3<)≤O(n2−psilon(χ))R_<(M^<,K^<_3)\leq O(n^{2-psilon(\chi)})

for almost every ordered matching M<M^< on nn vertices with interval chromatic number hihi.

Rohatgi's conjecture. The stated subquadratic bound holds for almost every ordered matching of each fixed interval chromatic number.

References

3 papers in this index state this conjecture (2022–2025). The statement above is taken from the most recent of them; the others are arXiv:2305.17933, arXiv:2201.07637.

Source: Martin Balko, “A Survey on Ordered Ramsey Numbers”, arXiv:2502.02155 (2025).

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.