Alguien puede explicar de una manera sencilla, ¿por qué hay tan pocos conocidos exacta de Números de Ramsey? Supongo que es porque no existen algoritmos eficientes para esta tarea, pero hay tantas combinaciones para probar?
Y una pregunta adicional: ¿Cómo son los límites determinado? ¿Por qué los límites, que son conocidos, tienen esos valores? Por qué no decir, trate de tomar un número menor para el límite superior para algunos 2-colorear?
Por un lado, nuestro interés en Ramsey números surgió a partir de un increíblemente no-constructiva de la prueba. I. e. el original de la prueba, lo que hizo poco más que mostrar que el $R(s, t)<\infty$. A la derecha del palo, estamos trabajando con muy poco.
Considere la posibilidad de la diagonal números de Ramsey $R(s, s)$. Ahora, la más desconocida de la diagonal de Ramsey número es $R(5, 5)$. Digamos que tenemos la sospecha de $R(5, 5) = 43$, que es el actual límite inferior. Nos tendría que confirmar que la propiedad tiene todas las $2$colorear en $K_{43}$. Dado que no se $\binom{43}{2} = 903$ bordes, entonces debemos de alguna manera de confirmar la propiedad tiene para todos los $2^{903}$ posible de colores. Esta es una $272$ número de dígitos! Para la comparación, este número es muchos órdenes de magnitud mayor que el número de protones, neutrones, y electrones en todo el universo observable. Por supuesto, es posible que podamos ir bajando este número significativamente, pero todavía sería increíblemente gigantesco.
La fuerza bruta es, obviamente, fuera de la cuestión, incluso para el más poderoso de los superordenadores.
Límites:
El trabajar en la reducción de los límites para la diagonal de Ramsey números de mejora sobre el original límite inferior Paul Erdős encuentra utilizando su método de probabilidades. Con este método, es posible demostrar (más fácilmente) que $R(s, s) \geq \lfloor 2^{\frac{s}{2}} \rfloor$. Por supuesto, el general límite inferior desde entonces ha sido mejorado, pero todavía tiene un crecimiento exponencial del factor de $\sqrt{2}$.
Relativamente decente límite superior de la diagonal de Ramsey números pueden ser probados utilizando el mismo enfoque que en la prueba de que $R(s, t) < \infty$. Es decir, podemos mostrar a $\displaystyle R(s, t) \leq \binom{s+t-2}{s-1}$. Al $s=t$, obtenemos $\displaystyle R(s, s) \leq \binom{2s-2}{s-1}$, que crece de manera exponencial con un factor de crecimiento de $4$. El actual límite superior se ha mejorado un poco, pero todavía tiene el mismo exponencial del factor de crecimiento.
Nota: Si usted está interesado, le recomiendo buscar en Erdős " prueba del límite inferior (es uno de mis favoritos). La idea de que uno usa la probabilidad de llegar a una determinada conclusión, es realmente fascinante.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
