On the minimum degree of minimal Ramsey graphs for multiple colours
On the minimum degree of minimal Ramsey graphs for multiple colours
复制标题
关于多种颜色的最小 Ramsey 图的最小度
DOI：
10.1016/j.jctb.2016.03.006
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Tibor Szabó
中科院分区：
文献类型：
--
作者：
J. Fox;A. Grinshpun;Anita Liebenau;Y. Person;Tibor Szabó
图G是图H的r-Ramsey，记为G→（H）r，如果G的每一条边的r-着色都包含H的一个单色副本.称图G为r-Ramsey-minimal（H），如果它是r-Ramsey（H），但G的任意真子图都不具有此性质.设sr（H）表示所有对H为r-Ramsey-极小的图G的最小度。参数s 2的研究是由伯尔、埃尔德什和洛瓦兹在1976年开始的，当时他们证明了对于团s 2（K k）=（k− 1）2。本文研究了sr（Kk）对r的依赖性，证明了在k为常数的条件下，sr（Kk）= r2 <$polylog r.给出了关于r和k均为多项式的sr（Kk）的上界，并证明了对于某些常数c，C> 0，cr2 ln <$sr（K3）<$Cr2 ln 2 <$r.
A graph G is r-Ramsey for a graph H, denoted by G→(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) denote the smallest minimum degree of G over all graphs G that are r-Ramsey-minimal for H. The study of the parameter s 2 was initiated by Burr, Erdős, and Lovász in 1976 when they showed that for the clique s 2 (K k)=(k− 1) 2. In this paper, we study the dependency of s r (K k) on r and show that, under the condition that k is constant, s r (K k)= r 2⋅ polylog r. We also give an upper bound on s r (K k) which is polynomial in both r and k, and we show that c r 2 ln r⩽ s r (K 3)⩽ C r 2 ln 2 r for some constants c, C> 0.