Ordered Ramsey numbers
Ordered Ramsey numbers
复制标题
DOI：
10.1016/j.jctb.2016.06.007
复制
发表时间：
2014-10
期刊：
影响因子：
--
通讯作者：
D. Conlon;J. Fox;Choongbum Lee;B. Sudakov
中科院分区：
文献类型：
--
作者：
D. Conlon;J. Fox;Choongbum Lee;B. Sudakov
给定一个顶点集为{1,2，…，n}的标记图H，有序拉姆齐数r<(H)是最小的n，使得在{1,2，…，n}上的完全图的每条边的二次着色都包含一个H的副本，其顶点出现的顺序与H相同。对于完全图，标记图H的有序拉姆齐数至少是拉姆齐数r (H)，并且两者重合。然而，我们证明了即使对于匹配，也存在有序拉姆齐数在顶点数上是超多项式的标记。在其他结果中，我们还证明了有序拉姆齐数的一般上界，这意味着对于顶点集{1,2，…，n}上的任何标记图H，存在一个常数c使得r<(H)≤r (H) c log 2 n。
Given a labeled graph H with vertex set {1, 2,…, n}, the ordered Ramsey number r<(H) is the minimum N such that every two-coloring of the edges of the complete graph on {1, 2,…, N} contains a copy of H with vertices appearing in the same order as in H. The ordered Ramsey number of a labeled graph H is at least the Ramsey number r (H) and the two coincide for complete graphs. However, we prove that even for matchings there are labelings where the ordered Ramsey number is superpolynomial in the number of vertices. Among other results, we also prove a general upper bound on ordered Ramsey numbers which implies that there exists a constant c such that r<(H)≤ r (H) c log 2 n for any labeled graph H on vertex set {1, 2,…, n}.