|
|
Last edited by Czhang271828 at 2021-1-29 16:28:00参考了以前不知哪里记来的笔记，总之出处不详。
由某种构造知$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$。
实际上，对计算三角形、四棱锥等简单完全图的数量有精确公式，只是计算量较大。 |
Rate
-
View Rating Log
|
Czhang271828
Posted at 2021-1-29 15:36:18
