A random coloring process gives improved bounds for the Erd\H{o}s-Gy\'arf\'as problem on generalized Ramsey numbers

MaRDI QIDQ6420484zbMATH OpenFDO

Authors Patrick Bennett, Andrzej Dudek, Sean English

Publication date 13 December 2022

Abstract: The ErdH{o}s-Gy'arf'as number $f(n,p,q)$ is the smallest number of colors needed to color the edges of the complete graph $K_n$ so that all of its $p$-clique spans at least $q$ colors. In this paper we improve the best known upper bound on $f(n,p,q)$ for many fixed values of $p,q$ and large $n$. Our proof uses a randomized coloring process, which we analyze using the so-called differential equation method to establish dynamic concentration.

This page was built for publication: A random coloring process gives improved bounds for the Erd\H{o}s-Gy\'arf\'as problem on generalized Ramsey numbers

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