PreprintarXiv licencearXiv
Polynomially superlinear growth of set-coloring Ramsey numbers
Abstract
The set-coloring Ramsey number R(k;r,s) is the least N such that every assignment of an s-element subset of [r] to each edge of KN yields a copy of Kk whose edges share a common color. For every fixed prime power q, we construct infinitely many positive integer triples (r,j,s) with j∼(q−1)−2/3r1/3 and s=(1−1/q)(r−j) such that R(q+1;r,s)=Θq(r4/3). For q=3, this answers in the affirmative a question of Conlon, Fox, Pham and Zhao, showing that polynomially superlinear growth for $R(4;r,2(r-j)/3)$ already occurs at the scale j=Θ(r1/3). Moreover, along the same sequence, the maximum size of a q-ary code of length r and minimum Hamming distance at least s is (1+o(1))(q−1)4/3r4/3.
Related
- Ramsey numbers R(K1,4,Km,n) for small m
- Spanning Even Linear Forests with Isolated Edges Share the Anti-Ramsey Numbers of Perfect Matchings
- On the multicolour Ramsey numbers R(3,3,k)
- Upper bounds for ordered Ramsey numbers of forests and bounded-degree graphs
- Ordered Trees with Linear Off-Diagonal Ramsey Numbers
BibTeX
@misc{lin2026polynomially,
title = {{Polynomially superlinear growth of set-coloring Ramsey numbers}},
author = {Qizhong Lin and Lin Niu},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.35079},
eprint = {2609.35079},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.35079},
}
RIS
TY - UNPB
TI - Polynomially superlinear growth of set-coloring Ramsey numbers
AU - Qizhong Lin
AU - Lin Niu
PY - 2026
DA - 2026/09/28
PB - arXiv
DO - 10.48550/arxiv.2609.35079
UR - https://arxiv.org/abs/2609.35079
AB - The set-coloring Ramsey number R(k;r,s) is the least N such that every assignment of an s-element subset of [r] to each edge of K_N yields a copy of K_k whose edges share a common color. For every fixed prime power q, we construct infinitely many positive integer triples (r,j,s) with j∼(q−1)^−2/3r^1/3 and s=(1−1/q)(r−j) such that R(q+1;r,s)=Θ_q(r^4/3). For q=3, this answers in the affirmative a question of Conlon, Fox, Pham and Zhao, showing that polynomially superlinear growth for $R(4;r,2(r-j)/3)$ already occurs at the scale j=Θ(r^1/3). Moreover, along the same sequence, the maximum size of a q-ary code of length r and minimum Hamming distance at least s is (1+o(1))(q−1)^4/3r^4/3.
ER -