AN EXTREMAL PROBLEM IN GRAPH THEORY
AN EXTREMAL PROBLEM IN GRAPH THEORY
复制标题
DOI：
10.1093/qmath/31.1.1
复制
发表时间：
1980-03
影响因子：
0.7
通讯作者：
H. L. Abbott;D. Hanson;A. Liu
中科院分区：
文献类型：
--
作者：
H. L. Abbott;D. Hanson;A. Liu
下面的问题是由克拉姆金教授在一次大学生数学竞赛中提出来的：假设一组7人中的每个人最多能说两种语言，并且每三个人中至少有两个人能交流。证明有三个人说同一种语言。解如下：设A是七个人中的一个。如果A可以和三个或更多的人说话，其中至少有两个人说A的一种语言，我们就完成了。因此，我们可以假设有四个人，比如说B、C、D和E，A不能与他们交流。同样，B不能与四个人交流，其中一个必须是C、D或E中的一个，比如C。那么，与我们的假设相反，在A、B和C之间，没有两个人可以交流。如果用”six”代替”seven”，很容易验证结论不成立。更一般地说，设t，m和p为正整数，且m^ 2和p 2= 3。用N= N（t，m，p）表示最大整数，使得存在满足以下条件的N个人的集合：（a）每个人最多说t种语言;（B）在任意m个人中，两个人说共同语言;（c）没有p个人说共同语言。Klamkin问题要求证明N（2，3，3）< 7。本文研究了N（t，m，p）的行为.我们对所有的t和m求N（t，m，3），对所有的m和p求7V（1，m，p）和N（2，m，p）.此外，我们还得到了一些其他的精确值，并建立了一些上下界.我们使用各种技术。特别是，我们利用图兰定理和其他各种结果，从图论和呼吁一些定理区组设计。然而，我们的研究结果还远远没有确定，似乎很难彻底解决这个问题。
THE following problem was brought to our attention by Professor MS Klamkin who posed it in an undergraduate mathematics competition: Suppose that each person in a group of seven people speaks at most two languages and that among every three people there are at least two who can communicate. Prove that there are three people who speak a common language. A solution runs as follows: Let A be one of the seven people. If A can speak to three or more people, at least two of these speak one of A's languages and we have finished. We may therefore suppose that there are four people, say B, C, D and E with whom A cannot communicate. Similarly, there must be four people with whom B cannot communicate and one of these must be one of C, D or E, say C. Then among A, B and C no two can communicate, contrary to our assumption. It is easy to verify that the conclusion does not follow if" seven" is replaced by" six".More generally, let t, m and p be positive integers with m^ 2 and p 2= 3. Denote by N= N (t, m, p) the largest integer such that there exists a set of N people satisfying the following conditions:(a) each speaks at most t languages;(b) among any m, two speak a common language;(c) no p speak a common language. Klamkin's problem calls for showing that N (2, 3, 3)< 7. We propose in this paper to investigate the behavior of N (t, m, p). We evaluate N (t, m, 3) for all t and m and 7V (1, m, p) and N (2, m, p) for all m and p. In addition, we obtain some other exact values and establish some upper and lower bounds. We use a variety of techniques. In particular, we make use of Turan's Theorem and various other results from graph theory and appeal to some theorems on block designs. However, our results are still far from being definitive and it seems that a complete solution to the problem may be difficult to achieve.