Diferencia entre revisiones de «Teoría de Ramsey»
Contenido eliminado Contenido añadido
m r2.7.1) (robot Añadido: he:תורת רמזי |
|||
Línea 11:
Por ejemplo, consideremos un [[grafo completo]] de orden ''n'', es decir, hay ''n'' vértices y cada vértice está conectado a todos los otros vértices por medio de una arista. Un grafo completo de orden 3 se llama [[triángulo]]. Ahora bien, cada arista puede tener uno de los siguientes colores: rojo o azul. ¿Qué tan grande debe ser ''n'' con el fin de garantizar que exista un triángulo azul o un triángulo rojo?. Resulta que la respuesta es 6. Véase el artículo sobre el [[teorema de Ramsey]] para una prueba rigurosa.
Otra manera de expresar este resultado es el siguiente: en cualquier actividad con al menos seis personas, hay tres personas que son mutuamente conocidas o mutuamente desconocidas. Véase el [[teorema de la amistad]].
Este es un caso especial del [[teorema de Ramsey]], que dice que para cualquier entero dado ''c'', y dado los enteros ''n''<sub>1</sub>,...,''n''<sub>''c''</sub>, existe el número: ''R''(''n''<sub>1</sub>,...,''n''<sub>''c''</sub>), llamado número de Ramsey, tal que si las aristas de un grafo completo de orden ''R''(''n''<sub>1</sub>,...,''n''<sub>''c''</sub>) se colorean con ''c'' colores distintos, entonces para algún ''i'' entre 1 y ''c'', debe contener un subgrafo completo de orden ''n<sub>i</sub>'' cuyas aristas están todas coloreadas con el color ''i''. El caso especial de arriba tiene ''c = 2'' y ''n''<sub>1</sub> = ''n''<sub>2</sub> = 3.
| |||