三色拉姆齐数：小路径与线性森林

《Discrete Applied Mathematics》：Three-color Ramsey numbers for small paths and linear forests

　　摘要

对于k≥2的图G1,…,Gk，k色Ramsey数R(G1,…,Gk)定义为最小的整数N，使得完全图KN的任意k边着色都包含某个颜色i∈{1,…,k}的Gi的同色拷贝。本文研究3色Ramsey数R(P3,L1,L2)，其中L1和L2是线性森林。通过建立普适比较原理，我们证明当3≤p≤q且(p,q)?{(3,3),(3,4)}时，有R(L1,L2)≤R(P3,L1,L2)≤R(Pp,Pq)，并精确刻画了这些边界相等的条件。利用理论归约、计算验证以及基于Ore哈密顿连通性定理的结构论证，我们证明在特定条件下，P3的引入不会增大相应的两色Ramsey数。特别地，对于线性森林L，我们推导了图族R(P3,Pn,mK2)、R(P3,mK2,L)和R(P3,2P3∪K2,L)的公式，并为图族R(P3,2P3,L)提供了完整的解答。

引言

本文所考虑的图均为有限简单图。对于图G，我们用V(G)表示其顶点集，E(G)表示其边集。对于S?V(G)，令G[S]表示由S导出的子图。G的阶为|V(G)|。对于顶点v∈V(G)，v在G中的度记为dG(v)，当图从上下文中清晰时简记为d(v)。G的最小度和最大度分别记为δ(G)和Δ(G)。

对于k≥2的图G1,…,Gk，k色Ramsey数R(G1,…,Gk)定义为最小的整数N，使得完全图KN的任意k边着色都包含某个颜色i∈{1,…,k}的Gi的同色拷贝。对于图G的以红、蓝、绿为颜色的3边着色，令Gr、Gb和Gg分别表示由相应颜色的边构成的生成子图。令Pn和mK2分别表示n阶路径和大小为m的匹配。线性森林是指每个连通分量都是路径的图。我们将线性森林写作L=Pa1∪Pa2∪?∪Pak，其中a1≥a2≥?≥ak≥2，且L的阶为∑i=1kai。因此，在本文中，线性森林没有孤立顶点。线性森林L的连通分量Pai称为奇分量，如果ai为奇数；否则称为偶分量。L的奇分量个数记为odd(L)。在各种图类中，路径、圈、匹配和线性森林因其基本结构和重要的组合性质而被广泛研究。

在经典的两色情形中，Faudree和Schelp [5] 解决了所有线性森林的Ramsey数问题，并建立了统一公式，这成为后续森林和路径Ramsey数研究的基石。对于涉及路径和圈的三色Ramsey数，Gyárfás等人 [7] 确定了充分大n时的R(Pn,Pn,Pn)。Benevides和Skokan [2] 证明了存在n1，使得对所有偶数n≥n1，R(Cn,Cn,Cn)=2n。Shao等人 [14] 确定了若干整数k的R(P4,P5,Ck)和R(P4,P6,Ck)的精确值。Dybizbański和Dzido [4] 在没有计算机算法辅助的情况下得到了R(P8,P8,P8)=14以及所有n≥3时的R(P2n+1,P2n+1,P2n+1)。三色Ramsey数R(C4,K1,m,Pn)、R(C4,C4,K1,n)和R(C4,C4,Wn)分别在文献[16]、[17]、[18]中被研究。其他相关结果可在文献[1]、[15]中找到。

近年来，研究人员在改进多色Ramsey数的界方面取得了实质性进展。Knierim和Su [9] 使用先进的图论方法改进了路径和偶圈的多色Ramsey数的渐近界。Sárk?zy [13] 也研究了路径和偶圈的多色Ramsey数，并为这些参数提供了非平凡界。Buci?、Letzter和Sudakov [10] 将研究扩展到二部宿主图，确定了圈和路径的三色二部Ramsey数。Khamseh和Omidi [8] 推广了线性森林的Ramsey理论。

随着计算机科学的发展，计算方法已成为验证Ramsey数的有力工具。Duggan [3] 应用SAT求解器和计算机代数系统验证了经典Ramsey问题R(3,8)和R(3,9)，这展示了计算方法在Ramsey理论中的有效性。

本文聚焦于Ramsey数R(P3,L1,L2)，其中L1和L2是任意线性森林。关键观察是，每个p阶线性森林都可以嵌入Pp，而平凡的两色下界R(L1,L2)仍然有效。这产生了如下简单而有效的比较原理：

定理1.1

设L1和L2分别是p阶和q阶的线性森林。令ji=odd(Li)，i=1,2。假设3≤p≤q且(p,q)?{(3,3),(3,4)}。则

R(L1,L2)≤R(P3,L1,L2)≤R(Pp,Pq)=q+p2?1。

等价地，

max{p+q?j2/2?1, q+p?j1/2?1}≤R(P3,L1,L2)≤q+p2?1。

第一个直接推论是：当较小的森林具有奇偶性所允许的最小可能的奇分量数时，上述不等式取等号。

定理1.2

在定理1.1的条件下，若j1=odd(L1)≤1，则

R(P3,L1,L2)=R(L1,L2)=R(Pp,Pq)=q+p2?1。

注

当较小的森林L1至多有一个奇分量时，定理1.2表明P3的引入不影响相应的两色Ramsey数。受此现象启发，我们进一步研究L1恰好有两个奇分量时的图族R(P3,L1,L2)。令人惊讶的是，即使在这种情况下，P3的加入仍然不改变Ramsey数R(L1,L2)。我们在某些条件下为R(P3,2P3,L2)和R(P3,2P3∪K2,L2)提供了完整的解答；分别参见定理4.4和定理5.1。

本文余下部分安排如下。第2节提供一些辅助结果。第3节建立定理1.1中所述的比较原理，确定其给出精确值的条件，并应用这些结果推导若干图族的精确公式。对于L1=2P3的情形，第4节给出R(P3,2P3,L2)的完整刻画，并证明红色P3约束从不增大相应的两色数：R(P3,2P3,L2)=R(2P3,L2)。第5节研究当8阶图族L1包含两个奇分量时的Ramsey数R(P3,L1,L2)，并证明对于每个满足|L2|≥12的线性森林L2，有R(P3,2P3∪K2,L2)=R(2P3∪K2,L2)。最后，附录详细说明我们在计算机辅助验证基础情形时使用的SAT编码。

章节片段

预备知识

本节回顾后续将使用的几个辅助结果。

定理2.1 Gerencsér–Gyárfás [6]

对于整数2≤p≤q，R(Pp,Pq)=q+p2?1。

Faudree和Schelp [5] 将该公式从路径推广到任意线性森林。

定理2.2 Faudree–Schelp [5]

设L1和L2分别是p阶和q阶的线性森林，令ji=odd(Li)，i=1,2。则

R(L1,L2)=max{p+q?j2/2?1, q+p?j1/2?1}。

对于路径的特殊三色Ramsey数，Maherani等人 [11] 证明了如下归约定理。

定理2.3 [11]

若3≤p≤q且(p,q)?{(3,3),(3,4)}，则

R(P3,Pp,Pq)=R(Pp,Pq)

Ramsey数R(P3,L1,L2)

本节证明R(P3,L1,L2)的比较原理，然后刻画其上下界何时相等。我们从如下命题开始，它展示了定理1.1中R(P3,L1,L2)的一般下界。

图族R(P3,2P3,L)：完整解答

当较小线性森林L1至多有一个奇分量时，Ramsey数R(P3,L1,L2)已被确定。自然的下一步是刻画当L1恰好包含两个奇分量时的R(P3,L1,L2)。

对于L1=2P3，我们有|L1|=6且odd(L1)=2。对于任意阶q≥7的线性森林L，定理1.1给出

q+1≤R(P3,2P3,L)≤q+2。

因此，较小森林中存在两个奇分量引入了一个单位的不确定性。受此现象启发，对于线性森林L，本节旨在……

R(P3,P5∪P3,L) 和 R(P3,2P3∪K2,L)

定理4.4给出了L1=2P3（具有两个奇分量）情形下R(P3,L1,L2)的完整精确公式。沿着这一研究路线，本节考虑L1是恰好包含两个奇分量的8顶点线性森林的情形。根据我们关于线性森林没有孤立顶点的约定，这样的森林只有P5∪P3和2P3∪K2。对于这两者，与更大森林比较时定理1.1仅产生一个单位的不确定性。我们的第一个观察是……

结语

本文研究了线性森林L1和L2的三色Ramsey数R(P3,L1,L2)。我们建立了普适比较原理，证明当3≤p≤q且(p,q)?{(3,3),(3,4)}时，有

R(L1,L2)≤R(P3,L1,L2)≤R(Pp,Pq)，

并精确刻画了这些边界何时相等。通过结合理论归约、计算验证和基于Ore哈密顿连通性定理的结构论证，我们证明在特定条件下红色P3的存在……

Minglei Mao | Lihong Qiu