论文标题
在非对角线上订购的拉姆齐数量的嵌套比赛
On off-diagonal ordered Ramsey numbers of nested matchings
论文作者
论文摘要
对于两个图表$ g^<$和$ h^<$，带有线性订购的顶点集，订购的ramsey编号$ r _ <（g^<，h^<）$是$ n $的最低$ n $，使得$ n $ vertices上订购的每个订购完整图形的每个红色颜色都包含$ g^<$ g^<$或blue a $ h $ h^$ h^$ h^$ h^$ h^$ h^$ h^$ h^$ h^$ h^$ h^$ h^$ h^$ h^^$。 对于一个正整数$ n $，嵌套匹配的$ nm^<_ n $是$ 2N $ vertices上的订购图，每个$ i = 1，\ dots，n $，带有边缘$ \ {i，2n-i+1 \} $。我们在Rohatgi获得的Ramsey数字$ r _ <（nm^<_ n，k^<_ 3）$上提高界限，我们通过显示$ 4N+1 \ leq r _ <（nm^<_ n，k^<_ 3）\ leq（nm^_ n，k^<_ 3） $ r _ <（nm^<_ n，k^<_ 3）$正好适合$ n = 4,5 $。作为推论，这给出了每$ k \ geq 3 $的$ k $ queue图的最大色度的更强下限。我们还证明了$ r _ <（nm^<_ m，k^<_ n）=θ（mn）$ for nutary $ m $和$ n $。 我们将Ramsey Goodness的经典概念扩展到有序的情况下，并试图表征所有连接的有序图，这些图形为$ n $ good，每$ n \ in \ Mathbb {n} $中的每个$ n \ good。特别是，我们发现了一类新的有序树，对于\ mathbb {n} $中的每$ n \ $ n $ good，都扩展了所有以前已知的示例。
For two graphs $G^<$ and $H^<$ with linearly ordered vertex sets, the ordered Ramsey number $r_<(G^<,H^<)$ is the minimum $N$ such that every red-blue coloring of the edges of the ordered complete graph on $N$ vertices contains a red copy of $G^<$ or a blue copy of $H^<$. For a positive integer $n$, a nested matching $NM^<_n$ is the ordered graph on $2n$ vertices with edges $\{i,2n-i+1\}$ for every $i=1,\dots,n$. We improve bounds on the ordered Ramsey numbers $r_<(NM^<_n,K^<_3)$ obtained by Rohatgi, we disprove his conjecture by showing $4n+1 \leq r_<(NM^<_n,K^<_3) \leq (3+\sqrt{5})n$ for every $n \geq 6$, and we determine the numbers $r_<(NM^<_n,K^<_3)$ exactly for $n=4,5$. As a corollary, this gives stronger lower bounds on the maximum chromatic number of $k$-queue graphs for every $k \geq 3$. We also prove $r_<(NM^<_m,K^<_n)=Θ(mn)$ for arbitrary $m$ and $n$. We expand the classical notion of Ramsey goodness to the ordered case and we attempt to characterize all connected ordered graphs that are $n$-good for every $n\in\mathbb{N}$. In particular, we discover a new class of ordered trees that are $n$-good for every $n \in \mathbb{N}$, extending all the previously known examples.
