El origen del teorema de la amistad

El contenido principal del teorema de la amistad es el siguiente: en un grupo de no menos de tres personas, si dos personas están exactamente a un sexo de distancia, entonces siempre habrá una persona en el grupo que todos conocen.

Puntos clave

Desde la perspectiva de la teoría de grafos, si cada vértice de un gráfico es adyacente a otro vértice y cada vértice es adyacente a otro vértice, la distancia es exactamente uno *** *, entonces siempre hay un vértice en el gráfico adyacente a cada otro vértice.

El teorema de la amistad en realidad se deriva del teorema de Ramsey y es una versión generalizada del teorema de Ramsey. El teorema original es el siguiente: Encuentre un número mínimo n tal que k de n individuos deban conocerse entre sí, o l no deba conocerse entre sí.

En combinatoria, el problema que resuelve el teorema de Ramsey es encontrar el número más pequeño n tal que k o l individuos entre n individuos deben conocerse entre sí.

El teorema lleva el nombre de Frank Plumpton Ramsey, quien demostró R(3 en su artículo de 1930 "Sobre un problema de lógica formal", 3)=6.

La definición del número de Ramsey

Hay dos formas de describir el número de Ramsey en el lenguaje de la teoría de grafos:

Para todos los gráficos con N vértices, un grupo contiene k vértices o un conjunto independiente de l vértices. El número natural más pequeño N con esta propiedad se llama número de Ramsey, registrado como R(k,l);

La teoría de la coloración lo describe de la siguiente manera: Para cualquier coloración de dos lados del gráfico completo Kn ( e1, e2), de modo que Kn[e2] contiene un lado k y Kn[e1] contiene un lado l. El mínimo n que satisface esta condición se llama número de Ramsey. (Nota: según la notación de la teoría de grafos, Ki representa una gráfica completa de orden i)

Ramsey demostró que para enteros positivos k y l dados, la respuesta a R(k,l) es única y limitada.

Los números de Ramsey también se pueden extender a más de dos números:

Para cada arista de un gráfico completo Kn, se pintan r colores de forma arbitraria y se representan como e1, e2,e3. ,...er, Kn debe tener un borde l1 con color e1, o un borde l2 con color e2..., o un borde lr con color er. El número más pequeño n que satisface la condición se denota por R(l1,l2,l3,...,lr;r).

El valor o límites superior e inferior del número de Ramsey

Hay muy pocos números de Ramsey conocidos. Paul Eldershot describió una vez la búsqueda de Ram en dificultad uniforme: "Imagínate. Un ejército de extraterrestres aterriza en la Tierra y exige el valor de R (5,5) o destruirán la Tierra. En este caso, deberíamos concentrar todas nuestras computadoras y matemáticos. Intentemos encontrar este valor si piden el valor de. R(6,6), intentaremos eliminar este tipo de alienígenas."

Si preguntan por el valor de R(6,6). Si merece la pena, debemos intentar eliminar este tipo de extraterrestres.

Obviamente, esta fórmula es fácil de entender:

1°R(1,s)=1

2°R(2,s)=s R(l1,l2,l3,... ,lr;r)=R(l2,l1,l3,... ,lr;r)=R(l3,l1,l2,... ,lr;r) (Cambiar el orden de li no cambiará el valor de Ramsey)