论文标题
在非综合制度中的广义拉姆西数字上
On generalized Ramsey numbers in the non-integral regime
论文作者
论文摘要
a $（p，q）$ - 图$ g $的颜色是$ g $的边缘颜色，因此每个$ p $ clique至少收到$ q $颜色。 1975年，Erdős和Shelah推出了广义的Ramsey数字$ F（N，P，Q）$，这是A $（P，Q）$ - 颜色$ K_n $所需的最低颜色数量。在1997年，Erdős和Gyárfás表明$ f（n，p，q）$最多是恒定时间$ n^{\ frac {p -2} {\ binom {p} {p} {2} {2} - q + 1}}} $。最近，第一作者杜德克（Dudek）和英语改进了这一限制的限制，$ \ log n^{\ frac {-1} {\ binom {\ binom {p} {2} {2} - q + 1}} $ for $ q \ le \ le \ le \ le \ frac {p^2-26p + 55} $ 我们对整个非综合制度的肯定回答，也就是说，对于所有整数$ p，q $，$ p-2 $不可用$ \ binom {p} {2} {2} - q + 1 $排除。此外，我们提供了同时的三向概括，如下所示：其中$ p $ -clique被任何固定的图形$ f $替换（带有$ | v（f）| -2 $不可分由$ | e（f）| - q + 1 $）;列出着色；以及$ k $均匀的超图。我们的结果是第二和第四作者的禁止征收方法的新应用。
A $(p,q)$-coloring of a graph $G$ is an edge-coloring of $G$ such that every $p$-clique receives at least $q$ colors. In 1975, Erdős and Shelah introduced the generalized Ramsey number $f(n,p,q)$ which is the minimum number of colors needed in a $(p,q)$-coloring of $K_n$. In 1997, Erdős and Gyárfás showed that $f(n,p,q)$ is at most a constant times $n^{\frac{p-2}{\binom{p}{2} - q + 1}}$. Very recently the first author, Dudek, and English improved this bound by a factor of $\log n^{\frac{-1}{\binom{p}{2} - q + 1}} $ for all $q \le \frac{p^2 - 26p + 55}{4}$, and they ask if this improvement could hold for a wider range of $q$. We answer this in the affirmative for the entire non-integral regime, that is, for all integers $p, q$ with $p-2$ not divisible by $\binom{p}{2} - q + 1$. Furthermore, we provide a simultaneous three-way generalization as follows: where $p$-clique is replaced by any fixed graph $F$ (with $|V(F)|-2$ not divisible by $|E(F)| - q + 1$); to list coloring; and to $k$-uniform hypergraphs. Our results are a new application of the Forbidden Submatching Method of the second and fourth authors.
