Geodesic
A random coloring process gives improved bounds for the Erdős-Gyárfás problem on generalized Ramsey numbers
Patrick Bennett ; Andrzej Dudek1 ; Sean English2
1Western Michigan University
2University of North Carolina Wilmington
The electronic journal of combinatorics, Tome 32 (2025) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

The Erdős-Gyárfás 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.
DOI : 10.37236/12387
Classification : 05C15, 05C55, 05D10, 05D40
Mots-clés : Erdős-Gyárfás number, randomized coloring process, differential equation method

Patrick Bennett    ; Andrzej Dudek  1   ; Sean English  2

1 Western Michigan University
2 University of North Carolina Wilmington 
@article{10_37236_12387,
     author = {Patrick Bennett and Andrzej Dudek and Sean English},
     title = {A random coloring process gives improved bounds for the {Erd\H{o}s-Gy\'arf\'as} problem on generalized {Ramsey} numbers},
     journal = {The electronic journal of combinatorics},
     year = {2025},
     volume = {32},
     number = {2},
     doi = {10.37236/12387},
     zbl = {1565.05029},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/12387/}
}
TY  - JOUR
AU  - Patrick Bennett
AU  - Andrzej Dudek
AU  - Sean English
TI  - A random coloring process gives improved bounds for the Erdős-Gyárfás problem on generalized Ramsey numbers
JO  - The electronic journal of combinatorics
PY  - 2025
VL  - 32
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/12387/
DO  - 10.37236/12387
ID  - 10_37236_12387
ER  - 
%0 Journal Article
%A Patrick Bennett
%A Andrzej Dudek
%A Sean English
%T A random coloring process gives improved bounds for the Erdős-Gyárfás problem on generalized Ramsey numbers
%J The electronic journal of combinatorics
%D 2025
%V 32
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/12387/
%R 10.37236/12387
%F 10_37236_12387
Patrick Bennett; Andrzej Dudek; Sean English. A random coloring process gives improved bounds for the Erdős-Gyárfás problem on generalized Ramsey numbers. The electronic journal of combinatorics, Tome 32 (2025) no. 2. doi: 10.37236/12387

Cité par Sources :