New upper bounds for the Erdős-Gyárfás problem on generalized Ramsey numbers
Combinatorics, Probability and Computing · 2023-03 · 32 (2) · 349-362
DOI: 10.1017/s0963548322000293 ↗Kurz gefasst
Fachartikel in der Zeitschrift Combinatorics, Probability and Computing, online erschienen am 24.11.2022. Verfasst von Alex Cameron und 1 weiteren Autor:innen. Die Arbeit wurde bisher 8-mal zitiert (Crossref) und nennt 8 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
A $(p,q)$ -colouring of a graph $G$ is an edge-colouring of $G$ which assigns at least $q$ colours to each $p$ -clique. The problem of determining the minimum number of colours, $f(n,p,q)$ , needed to give a $(p,q)$ -colouring of the complete graph $K_n$ is a natural generalization of the well-known problem of identifying the diagonal Ramsey numbers $r_k(p)$ . The best-known general upper bound on $f(n,p,q)$ was given by Erdős and Gyárfás in 1997 using a probabilistic argument. Since then, improved bounds in the cases where $p=q$ have been obtained only for $p\in \{4,5\}$ , each of which was proved by giving a deterministic construction which combined a $(p,p-1)$ -colouring using few colours with an algebraic colouring. In this paper, we provide a framework for proving new upper bounds on $f(n,p,p)$ in the style of these earlier constructions. We characterize all colourings of $p$ -cliques with $p-1$ colours which can appear in our modified version of the $(p,p-1)$ -colouring of Conlon, Fox, Lee, and Sudakov. This allows us to greatly reduce the amount of case-checking required in identifying $(p,p)$ -colourings, which would otherwise make this problem intractable for large values of $p$ . In addition, we generalize our algebraic colouring from the $p=5$ setting and use this to give improved upper bounds on $f(n,6,6)$ and $f(n,8,8)$ .
Zitieren
APA
Cameron, A., & Heath, E. (2023). New upper bounds for the Erdős-Gyárfás problem on generalized Ramsey numbers. Combinatorics, Probability and Computing, 32(2), 349-362. https://doi.org/10.1017/s0963548322000293
Vancouver
Cameron A, Heath E. New upper bounds for the Erdős-Gyárfás problem on generalized Ramsey numbers. Combinatorics, Probability and Computing. 2023;32(2):349-362. doi:10.1017/s0963548322000293
BibTeX
@article{Cameron2023,
author = {Cameron, Alex and Heath, Emily},
title = {New upper bounds for the Erdős-Gyárfás problem on generalized Ramsey numbers},
journal = {Combinatorics, Probability and Computing},
year = {2023},
volume = {32},
number = {2},
pages = {349--362},
doi = {10.1017/s0963548322000293}
}
EUVIMED