On generalized Ramsey numbers in the non-integral regime
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916438867968000 |
|---|---|
| author | Bennett, Patrick Delcourt, Michelle Li, Lina Postle, Luke |
| author_facet | Bennett, Patrick Delcourt, Michelle Li, Lina Postle, Luke |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2212_10542 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | On generalized Ramsey numbers in the non-integral regime Bennett, Patrick Delcourt, Michelle Li, Lina Postle, Luke Combinatorics 05C55, 05D05, 05D10 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. |
| title | On generalized Ramsey numbers in the non-integral regime |
| topic | Combinatorics 05C55, 05D05, 05D10 |
| url | https://arxiv.org/abs/2212.10542 |