On the minimum degree of minimal Ramsey graphs for multiple colours

详细信息    查看全文

• 作者：Jacob Fox^a ; ¹ ; ^{fox@math.mit.edu" class="auth_mail" title="E-mail the corresponding author} ; Andrey Grinshpun^b ; ² ; ^{agrinshp@math.mit.edu" class="auth_mail" title="E-mail the corresponding author} ; Anita Liebenau^c ; ³ ; ^{anita.liebenau@monash.edu" class="auth_mail" title="E-mail the corresponding author} ; Yury Person^d ; ^{person@math.uni-frankfurt.de" class="auth_mail" title="E-mail the corresponding author} ; Tibor Szabó ; ^e ; ⁴ ; ^{szabo@math.fu-berlin.de" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Graph theory ; Ramsey theory ; Minimal Ramsey graphs ; Minimum degree ; Erdős&ndash ; Rogers function
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：2016
• 出版时间：September 2016
• 年：2016
• 卷：120
• 期：Complete
• 页码：64-82
• 全文大小：460 K

文摘

A graph G is r-Ramsey for a graph H  , denoted by G→(H)_r$G\to {(H)}_r$, if every r-colouring of the edges of G contains a monochromatic copy of H. The graph G is called r-Ramsey-minimal for H if it is r-Ramsey for H but no proper subgraph of G   possesses this property. Let s_r(H)$s_r(H)$ denote the smallest minimum degree of G over all graphs G that are r-Ramsey-minimal for H  . The study of the parameter s₂$s_2$ was initiated by Burr, Erdős, and Lovász in 1976 when they showed that for the clique s₂(K_k)=(k−1)²$s_2(K_k)={(k-1)}^2$. In this paper, we study the dependency of s_r(K_k)$s_r(K_k)$ on r and show that, under the condition that k   is constant, $s_r(K_k)=r^2\cdot \text{polylog}r$. We also give an upper bound on s_r(K_k)$s_r(K_k)$ which is polynomial in both r and k  , and we show that cr²ln⁡r⩽s_r(K₃)⩽Cr²ln²⁡r$c{r}^2\ln r⩽s_r(K_3)⩽C{r}^2{\ln }^{2}r$ for some constants c,C>0$c,C>0$.