论文标题
erdős-gyárfás问题的新上限
New Upper Bounds for the Erdős-Gyárfás Problem on Generalized Ramsey Numbers
论文作者
论文摘要
a $（p，q）$ - 图$ g $的颜色是$ g $的边彩色，为每个$ p $ clique分配至少$ q $颜色。确定$ f（n，p，q）$的最小颜色数量的问题是给出$（p，q）$ - 完整图的着色$ k_n $是识别对角线ramsey数字$ r_k（p）$的众所周知问题的自然概括。 $ f（n，p，q）$上最著名的一般上限是由Erdős和Gyárfás在1997年使用概率论点给出的。从那时起，在仅以$ p \ in \ {4,5 \} $获得$ p = q $的情况下，改进的界限，通过给出$（p，p，p-1）$的确定性结构证明了每种颜色。 在本文中，我们提供了一个框架，用于以这些早期构造的方式证明$ f（n，p，p）$上的新上限。我们表征了$ p $ cliques的所有颜色，并带有$ p-1 $颜色，这些颜色可以出现在我们修改的$（p，p，p-1）$ - Conlon，Fox，Lee和Sudakov的颜色中。这使我们可以大大减少确定$（p，p）$ - 颜色所需的病例检查量，否则，这将使此问题对于$ p $的大值很难。此外，我们从$ p = 5 $设置中概括了代数着色，并使用它来改善$ f（n，6,6）$和$ f（n，8,8）$的上限。
A $(p,q)$-coloring of a graph $G$ is an edge-coloring of $G$ which assigns at least $q$ colors to each $p$-clique. The problem of determining the minimum number of colors, $f(n,p,q)$, needed to give a $(p,q)$-coloring of the complete graph $K_n$ is a natural generalization of the well-known problem of identifying the diagonal Ramsey numbers $r_k(p)$. The best-known general upper bound on $f(n,p,q)$ was given by Erdős and Gyárfás in 1997 using a probabilistic argument. Since then, improved bounds in the cases where $p=q$ have been obtained only for $p\in\{4,5\}$, each of which was proved by giving a deterministic construction which combined a $(p,p-1)$-coloring using few colors with an algebraic coloring. In this paper, we provide a framework for proving new upper bounds on $f(n,p,p)$ in the style of these earlier constructions. We characterize all colorings of $p$-cliques with $p-1$ colors which can appear in our modified version of the $(p,p-1)$-coloring of Conlon, Fox, Lee, and Sudakov. This allows us to greatly reduce the amount of case-checking required in identifying $(p,p)$-colorings, which would otherwise make this problem intractable for large values of $p$. In addition, we generalize our algebraic coloring from the $p=5$ setting and use this to give improved upper bounds on $f(n,6,6)$ and $f(n,8,8)$.
