Journal article
A random coloring process gives improved bounds for the Erdős-Gyárfás problem on generalized Ramsey numbers
The Electronic journal of combinatorics, v 32(2), 219
01 Apr 2025
Abstract
The Erd & odblac;s-Gy & aacute;rf & aacute;s number f(n, p, q) is the smallest number of colors needed to color the edges of the complete graph Kn 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.
Metrics
1 Record Views
Details
- Title
- A random coloring process gives improved bounds for the Erdős-Gyárfás problem on generalized Ramsey numbers
- Creators
- Patrick Bennett - Western Michigan UniversityAndrzej Dudek - Western Michigan UniversitySean English - Univ North Carolina, Dept Math & Stat, Wilmington, NC USA
- Publication Details
- The Electronic journal of combinatorics, v 32(2), 219
- Publisher
- Electronic Journal Of Combinatorics
- Number of pages
- 67
- Grant note
- MPS-TSM-00007551; 848648 / Simons Foundation
- Resource Type
- Journal article
- Language
- English
- Academic Unit
- Mathematics
- Web of Science ID
- WOS:001490288700001
- Other Identifier
- 991022197423204721