betaFeedback

WorksMathematics

The Common-Color Spectrum of Endpoint Set-Coloring Ramsey Numbers

Abstract

The set-coloring Ramsey number R(n;r,s,t)R(n;r,s,t) is the least NN such that every assignment of an ss-element subset of [r]={1,…,r}[r]=\{1,\ldots,r\} to each edge of KNK_N contains a KnK_n whose edge labels have at least tt common colors. Motivated by the work of Erdős and Szemerédi on R(n;r,r−1,1)R(n;r,r-1,1), we write R(n;r,r−1,t)=exp⁡(nfr,n(t))R(n;r,r-1,t)=\exp\bigl(nf_{r,n}(t)\bigr) and study f(t):=fr,n(t)f(t):=f_{r,n}(t) as tt ranges from 11 to r−1r-1. For fixed integers r≥2r\ge2 and 1≤t<r1\le t<r, we prove that, as n→∞n\to\infty, 12log⁡rr−t+o(1)≤f(t)≤rr−tlog⁡rr−t+C+Or,t ⁣(log⁡nn), \frac12\log\frac{r}{r-t}+o(1) \le f(t) \le \frac{r}{r-t}\log\frac{r}{r-t} +C+O_{r,t}\!\left(\frac{\log n}{n}\right), where C>0C>0 is an absolute constant. Comparisons between different numbers of colors show that the rates lim inf⁡n→∞fr,n(t)\liminf_{n\to\infty}f_{r,n}(t) and lim sup⁡n→∞fr,n(t)\limsup_{n\to\infty}f_{r,n}(t), defined for fixed rr and tt, each have a limit as r→∞r\to\infty and tr→α∈(0,1)\frac{t}{r}\toα\in(0,1) from above. The resulting two functions of αα are finite, positive, nondecreasing, and right-continuous. Writing Δt=f(t+1)−f(t)Δ_t=f(t+1)-f(t), we further prove that, as r→∞r\to\infty, uniformly for n≥r2n\ge r^2, at least (1−o(1))log⁡rlog⁡log⁡r\frac{(1-o(1))\log r}{\log\log r} indices 1≤t<r21\le t<\frac{r}{2} satisfy Δt≥1−o(1)2rΔ_t\ge\frac{1-o(1)}{2r}. For r,n≥3r,n\ge3 and 2≤h≤r−12\le h\le r-1, the final h−1h-1 increments account for at least 1−1⌈h/2⌉1-\frac{1}{\left\lceil h/2\right\rceil} of the total increase f(r−1)−f(1)f(r-1)-f(1). For each fixed r≥4r\ge4, the last increment has a positive lower limit as n→∞n\to\infty. Moreover, for r,n≥3r,n\ge3, it exceeds the sum of all preceding increments whenever rr is even or n=3n=3.

Paper details

vlnc:W_h463mx4c
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
  • Mathematics

generative AI

View statement
Looking for related papers…