11.2: Números Ramsey pequeños

Última actualización
Guardar como PDF

Page ID: 118358

Mitchel T. Keller & William T. Trotter
Georgia Tech & Morningside College

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

En realidad determinar los números de Ramsey a los que se\(R(m,n)\) hace referencia en el Teorema 11.2 parece ser un problema notoriamente difícil, y sólo un puñado de estos valores se conocen con precisión. En particular,\(R(3,3)=6\) y\(R(4,4)=18\), mientras\(43 \leq R(5,5) \leq 49\). El distinguido matemático húngaro Paul Erdős dijo en muchas ocasiones que podría ser posible determinar\(R(5,5)\) exactamente, si todo el talento matemático del mundo iba a centrarse en el problema. Pero también dijo que encontrar el valor exacto de\(R(6,6)\) podría estar más allá de nuestras capacidades colectivas.

En la siguiente tabla, proporcionamos información sobre los números de Ramsey\(R(m,n)\) cuando\(m\) y\(n\) son al menos 3 y como máximo 9. Cuando una celda contiene un solo número, esa es la respuesta precisa. Cuando hay dos números, representan límites inferior y superior.

Screen Shot 2022-03-10 a las 9.15.53 PM.png — Figura **11.3.** Números pequeños de Ramsey\(R(m,n)\)

Para obtener datos adicionales (o más actuales), consulte Dynamic Survey #DS1: “Small Ramsey Numbers” de Stanisław Radziszowski en la Revista Electrónica de Combinatoria. (La Figura 11.3 se actualizó por última vez utilizando la versión 12 de enero de 2014 de ese artículo.)