TOPICS
Search

Set-Coloring Ramsey Number

The set-coloring Ramsey number R(k;r,s) for positive integers k, r, and s with r>s is the least N such that every assignment of an s-element subset of [r] to each edge of the complete graph K_N yields a clique K_k such that the assigned subsets of its graph edges have a common element. When s=1, it is the usual r-color Ramsey number for K_k.

For every fixed prime power q, Lin and Niu (2026) constructed infinitely many triples (r,j,s) with

s=(1-1/q)(r-j) and j∼(q-1)^(-2/3)r^(1/3)

such that

R(q+1;r,s)=Theta_q(r^(4/3)).

For q=3, this shows that polynomially superlinear growth of R(4;r,2(r-j)/3) occurs already when j=Theta(r^(1/3)). Lin and Niu (2026) state that discussions with ChatGPT led them to an error-correcting code construction using ovoid codes concatenated with simplex codes.

See also

Error-Correcting Code, Ramsey Number

Explore with Wolfram|Alpha

References

Lin, Q. and Niu, L. "Polynomially Superlinear Growth of Set-Coloring Ramsey Numbers." 28 Sep 2026. https://arxiv.org/abs/2609.35079.

Cite this as:

Weisstein, Eric W. "Set-Coloring Ramsey Number." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Set-ColoringRamseyNumber.html

Subject classifications