The ordered Ramsey number of a graph \(G^<\) with a linearly ordered vertex set is the smallest positive integer N such that any two-coloring of the edges of the ordered complete graph on N vertices contains a monochromatic copy of \(G^<\) in the given ordering. The study of the quantitative behavior of ordered Ramsey numbers is a relatively new theme in Ramsey theory full of interesting and difficult problems. In this survey paper, we summarize recent developments in the theory of ordered Ramsey numbers. We point out connections to other areas of combinatorics and some well-known conjectures. We also list several new and challenging open problems and highlight the often strikingly different behavior from the unordered case.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

A Survey on Ordered Ramsey Numbers

  • Martin Balko

摘要

The ordered Ramsey number of a graph \(G^<\) with a linearly ordered vertex set is the smallest positive integer N such that any two-coloring of the edges of the ordered complete graph on N vertices contains a monochromatic copy of \(G^<\) in the given ordering. The study of the quantitative behavior of ordered Ramsey numbers is a relatively new theme in Ramsey theory full of interesting and difficult problems. In this survey paper, we summarize recent developments in the theory of ordered Ramsey numbers. We point out connections to other areas of combinatorics and some well-known conjectures. We also list several new and challenging open problems and highlight the often strikingly different behavior from the unordered case.