Generalized Ramsey numbers in the non-integral regime

Abstract: "A $(p,q)$-$\textit{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 $\textit{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, Bennett, 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$. In this talk, we will show that the answer is 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 new applications of the recently developed Forbidden Submatching Method."

Back to Search Research Symposium Abstracts