betaFeedback

WorksMathematics

Set-coloring Ramsey numbers with multiple intersections

Abstract

For integers r≥s≥t≥1r\ge s\ge t\ge1, we introduce the Ramsey number R(G;r,s,t)R(G;r,s,t), defined as the least NN such that every assignment of an ss-element subset of [r][r] to each edge of KNK_N yields a copy of GG whose edges have at least tt colors in common. This generalizes the classical set-coloring Ramsey number R(G;r,s)=R(G;r,s,1)R(G;r,s)=R(G;r,s,1), studied since the work of Erdos, Hajnal, and Rado. We show that tt cannot in general be eliminated by reparametrization: infinitely many quadruples (G;r,s,t)(G;r,s,t) satisfy R(G;r,s,t)≠R(G;a,b)R(G;r,s,t)\ne R(G;a,b) for every a≥b≥1a\ge b\ge1. Writing α=(rt)/(st)α=\binom{r}{t}/\binom{s}{t}, the shadow inequality R(G;r,s,t)≤R(G;(rt),(st),1)R(G;r,s,t)\le R(G;\binom{r}{t},\binom{s}{t},1) and the recent proof of the Erdos–Sos conjecture imply R(Tn;r,s,t)≤⌊α(n−2)⌋+2R(T_n;r,s,t)\le\lfloorα(n-2)\rfloor+2 for every nn-vertex tree TnT_n. For stars, we obtain packing bounds and exact values under suitable divisibility conditions. For paths and even cycles GG of order nn, we improve the upper bound to R(G;r,s,t)≤(α−γ+o(1))nR(G;r,s,t)\le(α-γ+o(1))n as n→∞n\to\infty, for fixed r>s≥t≥1r>s\ge t\ge1 and some γ=γ(r,s,t)>0γ=γ(r,s,t)>0. We also prove that, for fixed s,ts,t, the tree bound is asymptotically sharp for paths as r,n→∞r,n\to\infty, and for even cycles when n→∞n\to\infty first and then r→∞r\to\infty. For cliques KnK_n, we transfer known bounds of Conlon et al. for ordinary set-coloring Ramsey numbers to the general parameter tt, obtaining two-sided exponential bounds. For each fixed n≥3n\ge3, we identify an explicit piecewise-linear function ΦnΦ_n that determines a growth threshold. If s/r→σs/r\toσ and t/r→τt/r\toτ as r→∞r\to\infty, with 0<τ≤σ<10<τ\leσ<1, then R(Kn;r,s,t)=O(1)R(K_n;r,s,t)=O(1) when τ<Φn(σ)τ<Φ_n(σ), whereas R(Kn;r,s,t)≥exp⁡(cr)R(K_n;r,s,t)\ge\exp(cr) for some c>0c>0 when τ>Φn(σ)τ>Φ_n(σ).

Paper details

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

views · 7

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…