|
| | | | |
| | | |
| Stat |
Members: 3665
Articles: 2'599'751
Articles rated: 2609
18 January 2025 |
|
| | | | |
|
Article overview
| |
|
|
Generalized Ramsey numbers at the linear and quadratic thresholds | | Patrick Bennett
; Ryan Cushman
; Andrzej Dudek
; | | Date: |
1 Sep 2023 | | Abstract: | The generalized Ramsey number $f(n, p, q)$ is the smallest number of colors
needed to color the edges of the complete graph $K_n$ so that every $p$-clique
spans at least $q$ colors. Erdős and Gyárfás showed that $f(n, p, q)$
grows linearly in $n$ when $p$ is fixed and $q=q_{ ext{lin}}(p):=inom
p2-p+3$. Similarly they showed that $f(n, p, q)$ is quadratic in $n$ when $p$
is fixed and $q=q_{ ext{quad}}(p):=inom p2-frac p2+2$. In this note we
improve on the known estimates for $f(n, p, q_{ ext{lin}})$ and $f(n, p,
q_{ ext{quad}})$. Our proofs involve establishing a significant strengthening
of a previously known connection between $f(n, p, q)$ and another extremal
problem first studied by Brown, Erdős and Sós, as well as building on
some recent progress on this extremal problem by Delcourt and Postle and by
Shangguan. Also, our upper bound on $f(n, p, q_{ ext{lin}})$ follows from an
application of the recent forbidden submatchings method of Delcourt and Postle. | | Source: | arXiv, 2309.00182 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
|
| |
|
|
|
REGISTER