On generalized Ramsey numbers in the non-integral regime

arXiv2212.10542MaRDI QIDQ6421147FDOQ6421147

Authors: Patrick Bennett, Michelle Delcourt, Lina Li, Luke Postle 

Publication date: 20 December 2022

Abstract: 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, ErdH{o}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, ErdH{o}s and Gy'arf'as showed that $f(n,p,q)$ is at most a constant times $$. Very recently the first author, Dudek, and English improved this bound by a factor of $$ for all $qlefrac{p}^2-26p+554$, 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 $$. 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.

Mathematics Subject Classification ID

Generalized Ramsey theory (05C55) Extremal set theory (05D05) Ramsey theory (05D10)

This page was built for publication: On generalized Ramsey numbers in the non-integral regime

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6421147)