EUVIMEDEUVIMED entdecken
Crossref

On Generalized Ramsey Numbers in the Non-Integral Regime

Patrick Bennett, Michelle Delcourt, Lina Li, Luke Postle

The Electronic Journal of Combinatorics · 24.04.2026 · 33 (2)

DOI: 10.37236/14326 ↗

Kurz gefasst

Fachartikel in der Zeitschrift The Electronic Journal of Combinatorics, online erschienen am 24.04.2026. Verfasst von Patrick Bennett und 3 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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, Erdő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, Erdős and Gyárfás showed that $f(n,p,q)$ is at most a constant times $n^{\frac{p-2}{\binom{p}{2} - q + 1}}$. Very recently the first author, Dudek, and English improved this bound by a factor of $\log n^{\frac{-1}{\binom{p}{2} - q + 1}} $ for all $q \le \frac{p^2 - 26p + 55}{4}$, 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 $\binom{p}{2} - q + 1$. 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.

Zitieren

APA

Bennett, P., Delcourt, M., Li, L., & Postle, L. (2026). On Generalized Ramsey Numbers in the Non-Integral Regime. The Electronic Journal of Combinatorics, 33(2). https://doi.org/10.37236/14326

Vancouver

Bennett P, Delcourt M, Li L, Postle L. On Generalized Ramsey Numbers in the Non-Integral Regime. The Electronic Journal of Combinatorics. 2026;33(2). doi:10.37236/14326

BibTeX
@article{Bennett2026,
  author = {Bennett, Patrick and Delcourt, Michelle and Li, Lina and Postle, Luke},
  title = {On Generalized Ramsey Numbers in the Non-Integral Regime},
  journal = {The Electronic Journal of Combinatorics},
  year = {2026},
  volume = {33},
  number = {2},
  doi = {10.37236/14326}
}
Kostenlos starten →