Encuentra los números de Ramsay!
Deje (n, k) ser dos enteros. ¿Cuál es el tamaño mínimo de un grupo de personas? Por ejemplo, en la imagen, 1,2,5 forman una camarilla (hay un borde que conecta cualquiera de estos dos puntos) y 3,5,6 forman un anticiclón (no puede encontrar un borde entre ninguno de estos dos puntos) .
- ¿Qué es un gráfico bipartito?
- ¿Con qué tipo de matemáticas debería estar familiarizado un estudiante de CS?
- ¿Qué tan buena o mala es una idea para comenzar un doctorado teórico de CS a la edad de 27 años?
- ¿P es igual a DTIME (2 ^ n)?
- ¿Qué es una explicación intuitiva del teorema de Rice?
Este problema, a pesar de ser muy simple de explicar y representar, en realidad es muy difícil. Incluso para pequeños números. No sabemos el número de Ramsay para (5,5). Aquí hay una cita de Joel Spencer que puede encontrar en la página de Wikipedia sobre el teorema de Ramsey:
Erdős nos pide que imaginemos una fuerza alienígena, mucho más poderosa que nosotros, aterrizando en la Tierra y exigiendo el valor de R (5, 5) o destruirán nuestro planeta. En ese caso, afirma, deberíamos ordenar todas nuestras computadoras y todos nuestros matemáticos e intentar encontrar el valor. Pero supongamos, en cambio, que piden R (6, 6). En ese caso, él cree, deberíamos intentar destruir a los alienígenas.
Así es como se ven:
(Aparentemente no puedo hacer una tabla de látex en quora, así que esta es una captura de pantalla de la página de Wikipedia vinculada anteriormente)
El número de Ramsay de (n, k) es el mismo que el de (k, n), así que solo di la mitad inferior. El 43-49 en la intersección 5,5 significa que sabemos que es más de 43 y menos de 49. Como puede ver, no parece haber ninguna progresión lógica en los números y todavía nos desconcierta a la mayoría de nosotros hoy.
