论文标题
Gallai-Ramsey功能和数字的界限
Bounds for Gallai-Ramsey functions and numbers
论文作者
论文摘要
For two graphs $G,H$ and a positive integer $k$, the \emph{Gallai-Ramsey number} $\operatorname{gr}_k(G,H)$ is defined as the minimum number of vertices $n$ such that any $k$-edge-coloring of $K_n$ contains either a rainbow (all different colored) copy of $G$ or a monochromatic copy of $H$.如果$ g $和$ h $都是完整的图形，那么我们称其为Gallai-Ramsey功能。 Fox和Sudakov证明了$ \ operatatorName {gr} _k（k_s，k_t）\ leq s^{4kt} $。 Alon等。表明$ \ operatoTorname {gr} _k（k_s，k_t）\ leq（2s^3+4s^2）^{kt} $。在本文中，我们证明了$ \ operatorName {gr} _k（k_s，k_t）\ leq 2^{kt} s^{3kt} $ for $ t \ geq 47 $。当$ g，h $是一些特殊的图形时，我们还为$ \ operatatorName {gr} _k（g，h）$提供更好的上限。在本文中，我们为lovász局部引理提供了加赖 - 拉姆西功能和数字的一些下限。
For two graphs $G,H$ and a positive integer $k$, the \emph{Gallai-Ramsey number} $\operatorname{gr}_k(G,H)$ is defined as the minimum number of vertices $n$ such that any $k$-edge-coloring of $K_n$ contains either a rainbow (all different colored) copy of $G$ or a monochromatic copy of $H$. If $G$ and $H$ are both complete graphs, then we call it Gallai-Ramsey function. Fox and Sudakov proved $\operatorname{gr}_k(K_s,K_t)\leq s^{4kt}$. Alon et al. showed that $\operatorname{gr}_k(K_s,K_t)\leq (2s^3+4s^2)^{kt}$. In this paper, we prove that $\operatorname{gr}_k(K_s,K_t)\leq 2^{kt}s^{3kt}$ for $t\geq 47$. We also give better upper bounds for $\operatorname{gr}_k(G,H)$ when $G,H$ are some special graphs. In this paper, we derive some lower bounds for Gallai-Ramsey functions and numbers by Lovász Local Lemma.
