免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
返回列表 发帖

[组合] R(3,6)=18怎么证明

本帖最后由 realnumber 于 2020-7-18 08:52 编辑

要找这样一个最小的数n ,使得n个人中必定有k个人相识或l个人互不相识.
比如6个人中,必定有“3个人互相认识”或“3个人互相不认识”,5个人就不会有这个结果.这样记R(3,3)=6.
已知的拉姆齐数非常少,保罗·艾狄胥曾以一个故事来描述寻找拉姆齐数的难度:“想像有队外星人军队在地球降落,要求取得R(5,5)的值,否则便会毁灭地球。在这个情况,我们应该集中所有电脑和数学家尝试去找这个数值。若它们要求的是R(6,6)的值,我们要尝试毁灭这班外星人了。”
R(2,m)=m(m>1),R(3,3)=6,R(3,4)=9,R(3,5)=14,R(3,6)=18=R(4,4)
问题重新描述为n个点,两点之间要么连红线,要么连蓝线.
----
R(3,3)≤6,如下,ABCDEF,比如A点与其它5点相连,(由抽屉原理)这5条线必定有3线(或以上)同色,假定是AB,AC,AD都红色,那么B,C,D之间一旦连接一条红线,就会出现一个三边为红色的三角形,B,C,D之间没有出现红线,那么BCD本身为三边为蓝色的三角形.
当5个点时,五边形的边为红色,对角线为蓝色,那么不会出现三边同色的三角形,因此R(3,3)=6.(以上可百度)
R(3,4)≤9,R(3,5)≤14,R(4,4)≤18都可以模仿R(3,3)证明,R(3,6)卡住了,不会.  又,令以下出现的Kn表示出现n个点互相连线是同色的.
------
R(3,4)≤9,如下,即要出现有“3点互相连红线,即出现红色K3”或“4点互相连蓝线,即出现蓝色K4”,至少要9个点,任意选取一点,比如A,若A连了4条(或以上)红线,与A相连的这4点间不能出现红线(否则出现红色K3),那么这四点用蓝线连接了,出现了蓝色K4.若每点红线都小于等于3条,最多有[$\frac{3\times9}{2}$]=13条红线,即至少有$C_9^2=36$-13=23条蓝线,即拥有最多蓝线的点,假定为B,至少有[$\frac{23\times2}{9}$]+1=6条,考虑与B蓝线连接的这6个点,根据R(3,3)=6,必定出现红色K3或蓝色K3,若是蓝色k3加上B,即为蓝色K4.
-----
R(3,5)≤14,如下,14个点中,若有某点A,连接了5条或以上红线,与A相连的这5点之间不能出现红线(否则出现红色K3),那么这5点之间都用蓝线连接了,即出现蓝色K5.若每个点红线都小于等于4条,最多有$\frac{4\times 14}{2}$=28条红线,即至少有$C_{14}^2$-28=63条蓝线,连接蓝线最多的点,假定为B点,至少有$\frac{63\times2}{14}$=9条,考虑与B蓝线连接的这9个点,根据R(3,4)=9,必定出现红色K3或蓝色K4,若是蓝色K4加上B,即为蓝色K5.
------
R(4,4)≤18,如下,18个点中,若有某点A,连接了9条或以上红线,根据R(4,3)=R(3,4)=9,与A相连的这9点中,要么出现红色K3,要么出现蓝色K4.若每个点连接的红线都小于等于8条,最多有$\frac{8\times 18}{2}$=72条红线,即至少有$C_{18}^2$-72=81条蓝线,连接蓝线最多的点,假定为B点,至少有$\frac{81\times2}{18}$=9条,考虑与B蓝线连接的这9个点,根据R(4,3)=9,必定出现红色K4或蓝色K3,若是蓝色K3加上B,即为蓝色K4.
-----
R(3,6)尝试了以上办法,似乎行不通了.
分享到: QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友

本帖最后由 Czhang271828 于 2021-1-29 16:28 编辑

参考了以前不知哪里记来的笔记,总之出处不详。

由某种构造知$R(3,6)\neq 17$(具体参考Ramsey Graphs),下证明$R(3,6)=18$。

将$18$个人对应含有$18$点的图$G$,且规定点$i$与点$j$相邻当且仅当第$i$个人和第$j$个人互相认识。下用反证法证明,即设$G$中既无三角形,亦无$6$个两两独立的点。

引理$1$    $G$中每个顶点有且仅有$5$个邻点,即每个点恰好引出$5$条边。

证明:由$G$中无三角形知任意点$v_0\in G$的邻点互不相邻,再由假设“无$6$个两两独立的点”知$v_0$邻点至多$5$个。记$G'$为在$G$中挖去$v_0$及其邻点的图,同时删掉与上述点相连的边,则$G'$中至少有$12$个点。

1. 若$G'$中有$14$个或以上的点,则由$R(3,5)=14$知$G'$中有$5$个两两独立的点,在原图中连同$v_0$即为$6$个两两独立的点,矛盾。我们进一步得出任意点至少有$4$个邻点。
2. 若$G'$中有$13$个点,则$G'$必须是“既无三角形,亦无$5$个两两独立点”的图,即$R(3,5)$取极值时情形(据@realnumber 的证明即可唯一构造,如所示)。任取$v_0$的邻点$v_1$,$v_1$在$G'$中至少有$3$个邻点,这$3$个点显然两两不相邻,且与$v_1$及$G'$中对应的$4$个点相连(边数已饱和),故不会与$v_0$除$v_1$外的邻点相连。而$v_0$除$v_1$外的邻点与$v_1$在$G'$中的邻点两两独立,故$G$中存在$6$个两两独立的点,矛盾。

综上,$G'$中仅有$12$个点。

引理$2$    对$v_0$及其邻域外的点而言,有且仅有$4$个点与$v_0$仅有$1$个公共邻点,$8$个点与$v_0$仅有$2$个公共邻点。

证明:对任意非相邻点$v$、$u$,两者公共邻点的数量必然为$1$或$2$。反之若$v$与$u$无公共邻点,则$v$与$u$的五个邻点两两独立,矛盾。若$v$与$u$存在至少三个公共邻点,则$G$除去$u$、$v$、$u$的邻点、$v$的邻点,及上述点相连边后的图$G''$至少有$9$个点。注意到$R(3,4)\geq 9$,且$G''$中无三角形,则$G''$中至少有$4$个两两独立的点,连同$u$,$v$即为$6$个两两独立的点,矛盾。

沿用第一问符号。$v_0$邻点向$G'$中$12$点引出$4\times 5=20$条边,由鸡兔同笼原理得引理。

进一步研究$12$个非相邻点的分布。记$p_1$至$p_4$为与$v_0$仅有$1$个公共邻点者,$q_1$至$q_8$为其余者。$p_i$与$p_j$的公共邻点不是$v_0$的邻点,反之$p_i$、$p_j$连同$v_0$邻域中剩余的$4$个点两两独立(需用引理2)。同理,$q_i$与$v_0$的公共邻点($2$个)、$q_j$与$v_0$的公共邻点($2$个)不全等,反之这$2$个邻点有三个公共邻点,矛盾。

引理$3$    $\{p_1,p_2,p_3,p_4\}$成长度为$4$的环。

证明:记$v_0$的邻域为$N(v_0)=\{t,s_1,s_2,s_3,s_4\}$,由引理$2$不妨设$s_1p_1$、$s_2p_2$、$s_3p_3$与$s_4p_4$为连接$N(v)$与$P$的所有边。记$N(t)\setminus\{v_0\}=T=\{t_1,t_2,t_3,t_4\}$,因此$T\subseteq Q$。不妨设$t_i=q_{i+4}$。每一$s_i$的邻域为包含$v_0$、$p_i$、$t_j$、$q_k$与$q_l$五者。据引理$2$,$s_i$与$s_j$至多只有两个公共邻点,其一为$v_0$。同理$q_i$不能在$N(v_0)$中有两个以上的邻点。

不妨设$N(v_0)\cap N(q_1)=\{s_1,s_2\}$,则$\{s_3,s_4,t\}$两两交得的邻域均不包含$\{p_1,p_2,s_1,s_2,q_1\}$中任意一元素。为避免$6$个两两独立的点出现,集合$\{p_1,p_2,s_1,s_2,q_1\}$中无$3$个两两独立的点(也显然无三角形),因此包含一个五元环(易证)。其中$p_1-s_1-q_1-s_2-p_2$为五元环中一者,故$p_1$与$p_2$一定相邻。由于对所有$i=1,2,3,4$,$N(v_0)\cap N(q_i)$两两不同,故$P$中$4$点间连接了$4$条不同的边。再由于不存在三角形,故$\{p_1,p_2,p_3,p_4\}$成长度为$4$的环。

定理:$R(3,6)=18$。

证明:显然$p_i$与$t$均不相邻,故有公共邻点,即$\forall i:N(p_i)\cap\{t_1,t_2,t_3,t_4,v_0\}\neq \emptyset$,其中$v_0$本身不与$p_i$相邻。注意到$\{p_1,p_2,p_3,p_4\}$相邻点无公共邻点(因为无三角形),$\{p_1,p_2,p_3,p_4\}$相对点无公共邻点(因为至多两个公共邻点),我们不妨设$t_1$与$p_1$相邻,同理有$t_2$与$p_2$相邻、$t_3$与$p_3$相邻,及$t_4$与$p_4$相邻。

注意到对每个$p_i$均有边$p_is_i$,$p_it_i$,及$P$-环内的两条边,因此不妨设对任意$i\in\{1,2,3,4\}$均有$p_i$与$q_i$相邻。下求$v_0$与$q_1$的公共点,显然为$\{s_2,s_3,s_4\}$中的两者,同理$t$与$q_1$的公共点为$\{t_2,t_3,t_4\}$中两者。据抽屉原理,存在$i$使得$s_i-q_1-t_i$相连。

1. 若$i=2$或$4$,则$p_i$与$q_1$有三个共同邻点,即$s_i$、$t_i$与$p_1$三者。故矛盾。
2. 若$i=3$,则据对称性不妨设$q_1$与$s_2$相连,则$q_1$与$t_4$相连。而$s_2$与$T$中一者相连:
   1. 若$s_2$与$t_2$相连,则有三角形$s_2p_2t_2$,矛盾;
   2. 若$s_2$与$t_3$相连,则有三角形$s_2t_3q_1$,矛盾;
   3. 若$s_2$与$t_4$相连,则有三角形$s_2t_4q_1$,矛盾;
   4. 若$s_2$与$t_1$相连,则$s_2$与$p_1$有公共点$\{p_2,q_1,t_1\}$,矛盾。

综上, 定理得证。
--------------------------------------

初学图论时,我尝试给出过$R(3,3)$的解析做法,具体如下:

设$n$个点的图的邻接矩阵为$A$。即$a_{ij}=1$当且仅当点$i$与点$j$相邻,反之为$0$。如将所有点间的连线状态改变,则记补图的邻接矩阵为$\overline A$。显然$\overline A=J-I-A$,我们记$J=\mathbf 1\mathbf 1^T$。

一个显而易见的结论是:$A^k$的$i$行$j$列元素表示从点$i$至点$j$的所有长度为$k$的路径的数量。因此$\mathrm{trace}(A^3)$表示三角形数,而$\mathrm{trace}((J-I-A)^3)$表示三个两两不相邻点组的总数。我们下证明对六阶及以上的矩阵有

$$\mathrm{trace}(A^3)+\mathrm{trace}((J-I-A)^3)>0$$

即可。显然

$$
\begin{align*}
\mathrm{trace}(A^3)+\mathrm{trace}((J-I-A)^3)=&\mathrm{trace}((J-I)^3-3(J-I)A(J-I-A))\\
=&n(n-1)(n-2)-3\mathrm{trace}(JA(J-I-A))\\&+3\mathrm{trace}(A(J-I-A))\\
=&n(n-1)(n-2)-3\sum_i(1_j)(n-1-1_j)
\end{align*}
$$

这里$1_j$表示第$j$行/列数字$1$的数量。对每个二次式取极值得:

$$\mathrm{trace}(A^3)+\mathrm{trace}((J-I-A)^3)\geq\left\{\begin{align*}&2k(k-1)(k-2),&& n=2k,\\&(2k+1)k(k-2),&&n=2k+1.\end{align*}\right.$$

因此$R(3,3)=6$。

实际上,对计算三角形、四棱锥等简单完全图的数量有精确公式,只是计算量较大。
1

评分人数

    • realnumber: 感谢,试着学习,总会进步些威望 + 1
无钱佮歹看、无样佮歹生、无汉草佮无文采、无学历佮无能力、无高度无速度无力度共闲无代记。(闽南话)
口号:珍爱生命,远离内卷。

TOP

返回列表 回复 发帖