main content
From the perspective of graph theory, if each vertex of a graph happens to be adjacent to another vertex, then there is always a vertex adjacent to other vertices in this graph.
Friendship theorem is actually derived from Ramsey theorem, which is a popular version of Ramsey theorem. The original theorem is as follows: to require such a minimum number n, there must be k people who know each other or l people who don't know each other.
In combinatorial mathematics, Ramsey theorem is to solve the following problem: to find such a minimum number n, there must be K people who know each other or L people who don't know each other.
This theorem is named after frank ramsey. 1930, he proved that r (3,3) = 6 in A Problem in Formal Logic.
The definition of Ramsey number
Ramsey number, in the language of graph theory, has two descriptions:
For all n-vertex graphs, it refers to a group containing k vertices or a set of l independent vertices. The smallest natural number n with this property is called Ramsey number, which is denoted as r (k, l);
In the coloring theory, it is described as follows: If any two edges of a complete graph Kn are colored (e 1, e2) so that Kn[e2] contains a k edge and Kn[e 1] contains an l edge, then the minimum n satisfying this condition is called a Ramsey number. (Note: Ki represents the I-order complete graph of symbols according to graph theory)
Ramsey proved that the answer of R(k, l) is unique and finite for given positive integers k and l.
Ramsey number can also be extended to more than two numbers:
Each side of the complete graph Kn is painted with one of R colors, namely e 1, e2, e3, ..., er. In Kn, there must be an l 1 polygon with the color e 1, an l2 polygon with the color e2 ... or an lr polygon with the color er. Meet the requirements and the least number n is R(l 1, l2, l3, ..., lr; r).
The numerical value or upper and lower bounds of Ramsey number
There are very few known Ramsey numbers. Paul Edith once described the difficulty in finding Ramsey numbers with a story: "Imagine a team of alien troops landing on the earth and demanding the value of r (5,5), otherwise it will destroy the earth. In this case, we should concentrate all computers and mathematicians to try to find this value. If they demand the value of R (6,6), we will try to destroy these aliens. "
The obvious formula:
1 R( 1，s)= 1
2 R(2，s)=s R(l 1，l2，l3，...，lr； r)=R(l2，l 1，l3，...，lr； r)=R(l3，l 1，l2，...，lr； R) (Changing the order of Lee does not change the value of Ramsey)