单色三角形问题，求证！

费奇

平面上有16个点，任意3点不共线。用3种颜色的线将16点两两相连，
证明：存在使16点中任意3点组成的三角形不是单色（边）三角形的连接方法。

gxqcn

如果证明不存在，一般用反证法；
证明存在，那就构造出来一个就可以了。

费奇

如果证明不存在，一般用反证法；
证明存在，那就构造出来一个就可以了。
gxqcn 发表于 2010-11-16 07:41

用计算机构造一个出来，太“粗暴”了。换成65点4色，甚至更多，计算机也会累着的。
目的是希望能找到一个巧妙的通解方法，而不是不动脑子的暴力

zgg___

或许可以参考“http://en.wikipedia.org/wiki/Ramsey%27s_theorem”中的“A Multicolour Example: R(3,3,3) = 17”的那一段。

费奇

4# zgg___


那个只是说明17点很容易证明必然出现单色三角形，可是并没证明16点存在不出现单色三角形的情况啊。。。

zgg___

下面的一段说明了将完全图K16涂3色一共有2种涂法。右面的图我也打不开，呵呵。
“To see that R(3,3,3) >= 17, it suffices to draw an edge colouring on the complete graph on 16 vertices with 3 colours, which avoids monochromatic triangles. It turns out that there are exactly two such colourings on K16, the so-called untwisted and twisted colourings. Both colourings are shown in the figure to the right, with the untwisted colouring on the top, and the twisted colouring on the bottom. In both colourings in the figure, note that the vertices are labeled, and that the vertices v11 through v15 are drawn twice, on both the left and the right, in order to simplify the drawings.
Thus, R(3,3,3) = 17.
If you select any colour of either the untwisted or twisted colouring on K16, and consider the graph whose edges are precisely those edges which have the specified colour, you will get the Clebsch graph.
It is known that there are exactly two edge colourings with 3 colours on K15 which avoid monochromatic triangles, which can be constructed by deleting any vertex from the untwisted and twisted colourings on K16, respectively.
It is also known that there are exactly 115 edge colourings with 3 colours on K14 which avoid monochromatic triangles, provided that we consider edge colourings which differ by a permutation of the colours as being the same.”

费奇

看起来挺复杂的，先学习下。。。

费奇

找了本电子书看了下，上面也只是说，要证明16顶点不具备Ramsey性，就是要给出“临界Ramsey图”。。。
还是相当于“实践法”，而不是从理论上证明呀。。。看来这东西真是挺难得。。。

费奇

而且确定 Ramsey 数很难，目前也并没有精确严谨的理论求解方法 - -#

zgg___

找到了6层提到的图，见下：