关于多色单色路径拉姆塞数的更优上界问询
关于多色单色路径拉姆塞数的更优上界问询
先给大家明确几个基础定义,方便讨论:
- 定义$\rho(k,l)$(要求$k \ge l$)为拉姆塞数$R(P_k,P_l)$:也就是最小的正整数$R$,使得任意红蓝两色边着色的$R$阶完全图中,必然存在红色的$P_k$路径,或者蓝色的$P_l$路径。
- 已有研究证明了这个两色情形的结论:$\rho(k,l) = k + \lceil (l+1)/2 \rceil$。
现在我们拓展到多色场景:
定义$\delta(n,t) = R(\underbrace{P_t,P_t,\dots,P_t}_{n个P_t})$,它是满足以下条件的最小正整数$\delta$:任意用$n$种颜色对$\delta$阶完全图的边进行着色,图中一定存在某一种颜色的单色$P_t$路径。
想请教各位同行,目前关于$\delta(n,t)$有没有更优的上界结论呀?或者有没有相关的研究思路可以分享?
备注:内容来源于stack exchange,提问作者PD_Sathya
相关产品推荐
相关产品推荐

