Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
The authors investigate the asymptotic thresholds for set-coloring Ramsey numbers $R(k;r,s)$, which govern the minimum graph size required to guarantee monochromatic cliques when edges receive multi-element color sets. For any prime power $q$, they establish that $R(q+1;r,s) = \Theta_q(r^{4/3})$ when $s=(1-1/q)(r-j)$ and $j \sim (q-1)^{-2/3}r^{1/3}$, settling an open question of Conlon, Fox, Pham, and Zhao regarding superlinear growth regimes. This framework simultaneously resolves the exact asymptotic maximum size of length-$r$ $q$-ary codes with minimum Hamming distance at least $s$ as $(1+o(1))(q-1)^{4/3}r^{4/3}$.
Set-coloring Ramsey numbers achieve polynomially superlinear $\Theta(r^{4/3})$ growth far earlier than previously known, resolving a conjecture of Conlon et al. while pinning down tight capacity bounds for high-distance $q$-ary codes.
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\sim(q-1)^{-2/3}r^{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/3}r^{4/3}$.