Ronald Lewis Graham (31 de octubre de 1935 - 6 de julio de 2020) [1] fue un matemático estadounidense reconocido por la American Mathematical Society como "uno de los principales arquitectos del rápido desarrollo mundial de las matemáticas discretas en los últimos años". [2] Fue presidente tanto de la American Mathematical Society como de la Mathematical Association of America , y entre sus honores se incluyen el premio Leroy P. Steele por su trayectoria y la elección a la Academia Nacional de Ciencias .
Después de realizar estudios de posgrado en la Universidad de California, Berkeley , Graham trabajó durante muchos años en Bell Labs y más tarde en la Universidad de California, San Diego . Realizó un trabajo importante en teoría de programación , geometría computacional , teoría de Ramsey y cuasialeatoriedad , [3] y muchos temas de matemáticas llevan su nombre. Publicó seis libros y alrededor de 400 artículos, y tuvo casi 200 coautores, incluidos muchos trabajos en colaboración con su esposa Fan Chung y con Paul Erdős .
Graham ha aparecido en ¡ Aunque usted no lo crea! de Ripley por ser no sólo "uno de los matemáticos más destacados del mundo", sino también un trampolín y malabarista consumado. Fue presidente de la Asociación Internacional de Malabaristas . [3] [4] [5]
Graham nació en Taft, California , el 31 de octubre de 1935; [6] su padre era un trabajador de un campo petrolífero y más tarde un marino mercante. A pesar del interés posterior de Graham por la gimnasia, era pequeño y no atlético. [7] Creció mudándose con frecuencia entre California y Georgia, saltándose varios grados de la escuela en estos traslados y nunca permaneciendo en ninguna escuela más de un año. [1] [7] Cuando era adolescente, se mudó a Florida con su madre, entonces divorciada, donde asistió pero no terminó la escuela secundaria. En cambio, a la edad de 15 años, ganó una beca de la Fundación Ford para la Universidad de Chicago , donde aprendió gimnasia pero no tomó cursos de matemáticas. [1]
Después de tres años, cuando su beca expiró, se trasladó a la Universidad de California, Berkeley , oficialmente como estudiante de ingeniería eléctrica, pero también estudiando teoría de números con DH Lehmer , [1] y ganando un título como campeón de trampolín del estado de California. [7] Se alistó en la Fuerza Aérea de los Estados Unidos en 1955, cuando alcanzó la edad de elegibilidad, [8] dejó Berkeley sin un título y fue destinado a Fairbanks, Alaska , donde finalmente completó una licenciatura en física en 1959 en la Universidad de Alaska Fairbanks . [1] Al regresar a Berkeley para realizar estudios de posgrado, recibió su doctorado en matemáticas en 1962. Su disertación, supervisada por Lehmer, fue Sobre sumas finitas de números racionales . [9] Mientras era estudiante de posgrado, se mantuvo actuando en el trampolín en un circo, [8] y se casó con Nancy Young, una estudiante de matemáticas de pregrado en Berkeley; tuvieron dos hijos. [1]
Después de completar su doctorado, Graham comenzó a trabajar en 1962 en Bell Labs y más tarde como Director de Ciencias de la Información en AT&T Labs , ambos en Nueva Jersey . En 1963, en una conferencia en Colorado, conoció al matemático húngaro Paul Erdős (1913-1996), [1] quien se convirtió en un amigo cercano y colaborador frecuente de investigación. Graham se sintió apenado por ser derrotado en ping-pong por Erdős, entonces ya de mediana edad; regresó a Nueva Jersey decidido a mejorar su juego, y finalmente se convirtió en campeón de Bell Labs y ganó un título estatal en el juego. [1] Graham popularizó más tarde el concepto del número de Erdős , una medida de distancia de Erdős en la red de colaboración de matemáticos; [10] [8] sus muchos trabajos con Erdős incluyen dos libros de problemas abiertos [B1] [B5] y el artículo póstumo final de Erdős. [A15] Graham se divorció en la década de 1970; en 1983 se casó con su colega de Bell Labs y frecuente coautor Fan Chung . [1]
Mientras estaba en Bell Labs, Graham también ocupó un puesto en la Universidad Rutgers como profesor universitario de Ciencias Matemáticas en 1986, y sirvió como presidente de la Sociedad Matemática Americana de 1993 a 1994. Se convirtió en el científico jefe de los laboratorios en 1995. [1] Se retiró de AT&T en 1999 después de 37 años de servicio, [11] y se trasladó a la Universidad de California, San Diego (UCSD), como profesor titular de Irwin y Joan Jacobs de Informática y Ciencias de la Información. [1] [8] En la UCSD, también se convirtió en el científico jefe del Instituto de Telecomunicaciones y Tecnología de la Información de California . [8] [5] En 2003-04, fue presidente de la Asociación Matemática de América . [1]
Graham murió de bronquiectasia [12] el 6 de julio de 2020, a los 84 años, en La Jolla , California. [6] [13]
Graham hizo importantes contribuciones en múltiples áreas de las matemáticas y la informática teórica. Publicó alrededor de 400 artículos, una cuarta parte de ellos con Chung, [14] y seis libros, incluido Concrete Mathematics con Donald Knuth y Oren Patashnik . [B4] El Erdős Number Project lo enumera como coautor de casi 200 trabajos. [15] Fue asesor de doctorado de nueve estudiantes, uno en la City University de Nueva York y otro en la Rutgers University mientras estaba en Bell Labs, y siete en la UC San Diego. [9]
Entre los temas matemáticos más destacados que llevan el nombre de Graham se encuentran el problema de Erdős-Graham sobre fracciones egipcias , el teorema de Graham-Rothschild en la teoría de Ramsey de palabras paramétricas y el número de Graham derivado de él, el teorema de Graham-Pollak y la conjetura de Graham en la teoría de grafos , el algoritmo de Coffman-Graham para la programación aproximada y el dibujo de grafos, y el algoritmo de barrido de Graham para envolventes convexas . También comenzó el estudio de las sucesiones sin primos , el problema de las ternas pitagóricas de Boole , el polígono más pequeño y el empaquetamiento de cuadrados en un cuadrado .
Graham fue uno de los colaboradores de las publicaciones de GW Peck , una colaboración matemática seudónima llamada así por las iniciales de sus miembros, con Graham como la "G". [16]
La tesis doctoral de Graham fue sobre teoría de números , sobre fracciones egipcias , [7] [9] como lo es el problema de Erdős-Graham sobre si, para cada partición de los números enteros en un número finito de clases, una de estas clases tiene una subclase finita cuyos recíprocos suman uno. Ernie Croot publicó una prueba en 2003. [17] Otro de los artículos de Graham sobre fracciones egipcias fue publicado en 2015 con Steve Butler y (casi 20 años después de su muerte) Erdős; fue el último de los artículos de Erdős en ser publicado, convirtiendo a Butler en su coautor número 512. [A15] [18]
En un artículo de 1964, Graham comenzó el estudio de las secuencias sin primos observando que existen secuencias de números, definidas por la misma relación de recurrencia que los números de Fibonacci , en las que ninguno de los elementos de la secuencia es primo. [A64] El desafío de construir más secuencias de este tipo fue asumido más tarde por Donald Knuth y otros. [19] El libro de Graham de 1980 con Erdős, Old and new results in combinatorial number theory, proporciona una colección de problemas abiertos de una amplia gama de subáreas dentro de la teoría de números. [B1]
El teorema de Graham-Rothschild en la teoría de Ramsey fue publicado por Graham y Bruce Rothschild en 1971, y aplica la teoría de Ramsey a los cubos combinatorios en la combinatoria de palabras . [A71a] Graham dio un número grande como límite superior para una instancia de este teorema, ahora conocido como el número de Graham , que fue incluido en el Libro Guinness de los Récords como el número más grande jamás utilizado en una prueba matemática, [20] aunque desde entonces ha sido superado por números aún mayores como TREE(3) . [21]
Graham ofreció un premio monetario por resolver el problema de las ternas pitagóricas de Boole , otro problema en la teoría de Ramsey; el premio fue reclamado en 2016. [22] Graham también publicó dos libros sobre la teoría de Ramsey. [B2] [B3]
El teorema de Graham-Pollak , que Graham publicó con Henry O. Pollak en dos artículos en 1971 y 1972, [A71b] [A72a] establece que si las aristas de un grafo completo de vértice se dividen en subgrafos bipartitos completos , entonces se necesitan al menos subgrafos. Graham y Pollak proporcionaron una prueba simple utilizando álgebra lineal ; a pesar de la naturaleza combinatoria del enunciado y de las múltiples publicaciones de pruebas alternativas desde su trabajo, todas las pruebas conocidas requieren álgebra lineal. [23]
Poco después de que comenzara la investigación en grafos cuasialeatorios con el trabajo de Andrew Thomason, Graham publicó en 1989 un resultado con Chung y RM Wilson que se ha llamado el "teorema fundamental de los grafos cuasialeatorios", afirmando que muchas definiciones diferentes de estos grafos son equivalentes. [A89a] [24]
La conjetura de guijarros de Graham , que aparece en un artículo de Chung de 1989, [25] es un problema abierto sobre el número de guijarros de productos cartesianos de grafos . [26]
Los primeros trabajos de Graham sobre la programación de talleres de trabajo [A66] [A69] introdujeron la relación de aproximación del peor caso en el estudio de los algoritmos de aproximación y sentaron las bases para el desarrollo posterior del análisis competitivo de los algoritmos en línea . [27] Más tarde se reconoció que este trabajo era importante también para la teoría del empaquetamiento de contenedores , [28] un área en la que Graham trabajó más explícitamente más adelante. [A74]
El algoritmo Coffman–Graham , que Graham publicó con Edward G. Coffman Jr. en 1972, [A72b] proporciona un algoritmo óptimo para la programación de dos máquinas y un algoritmo de aproximación garantizada para un mayor número de máquinas. También se ha aplicado en el dibujo de gráficos en capas . [29]
En un artículo de investigación sobre algoritmos de programación publicado en 1979, Graham y sus coautores introdujeron una notación de tres símbolos para clasificar los problemas teóricos de programación según el sistema de máquinas en el que se ejecutarán, las características de las tareas y los recursos, como los requisitos de sincronización o no interrupción, y la medida de rendimiento que se va a optimizar. [A79] Esta clasificación a veces se ha denominado "notación de Graham" o "notación de Graham". [30]
El escaneo de Graham es un algoritmo ampliamente utilizado y práctico para envolturas convexas de conjuntos de puntos bidimensionales, basado en la clasificación de los puntos y su posterior inserción en la envoltura en orden ordenado. [31] Graham publicó el algoritmo en 1972. [A72c]
El problema del polígono más pequeño pide el polígono de área más grande para un diámetro dado. Sorprendentemente, como observó Graham, la respuesta no siempre es un polígono regular . [A75a] La conjetura de Graham de 1975 sobre la forma de estos polígonos finalmente se demostró en 2007. [32]
En otra publicación de 1975, Graham y Erdős observaron que para empaquetar cuadrados unitarios en un cuadrado más grande con longitudes laterales no enteras, se pueden usar cuadrados inclinados para dejar un área descubierta que es sublineal en la longitud lateral del cuadrado más grande, a diferencia del empaquetamiento obvio con cuadrados alineados con el eje. [A75b] Klaus Roth y Bob Vaughan demostraron que a veces puede ser necesario un área descubierta al menos proporcional a la raíz cuadrada de la longitud lateral; probar un límite estricto en el área descubierta sigue siendo un problema abierto. [33]
En estadística no paramétrica , un artículo de 1977 de Persi Diaconis y Graham estudió las propiedades estadísticas de la regla de Spearman, una medida de correlación de rango que compara dos permutaciones sumando, sobre cada elemento, la distancia entre las posiciones del elemento en las dos permutaciones. [A77] Compararon esta medida con otros métodos de correlación de rango, lo que dio como resultado las "desigualdades de Diaconis-Graham".
donde es la regla de Spearman, es el número de inversiones entre las dos permutaciones (una versión no normalizada del coeficiente de correlación de rango de Kendall ), y es el número mínimo de intercambios de dos elementos necesarios para obtener una permutación de la otra. [34]
El proceso aleatorio de Chung-Diaconis-Graham es un recorrido aleatorio sobre los números enteros módulo un número entero impar , en el que en cada paso se duplica el número anterior y luego se suma aleatoriamente cero, , o (módulo ). En un artículo de 1987, Chung, Diaconis y Graham estudiaron el tiempo de mezcla de este proceso, motivados por el estudio de los generadores de números pseudoaleatorios . [A87] [35]
Graham se convirtió en un hábil malabarista a partir de los 15 años, y se ejercitó en hacer malabarismos con hasta seis pelotas. [4] (Aunque una foto publicada lo muestra haciendo malabarismos con doce pelotas, [5] es una imagen manipulada. [3] ) Le enseñó a hacer malabarismos a Steve Mills , un ganador repetido de los campeonatos de la Asociación Internacional de Malabaristas, y su trabajo con Mills ayudó a inspirar a Mills a desarrollar el patrón de malabarismo Mills' Mess . Además, Graham hizo importantes contribuciones a la teoría del malabarismo, incluida una secuencia de publicaciones en siteswaps . En 1972 fue elegido presidente de la Asociación Internacional de Malabaristas . [4]
En 2003, Graham ganó el Premio anual Leroy P. Steele de la American Mathematical Society por su trayectoria. El premio citó sus contribuciones a las matemáticas discretas , su popularización de las matemáticas a través de sus charlas y escritos, su liderazgo en Bell Labs y su servicio como presidente de la sociedad. [2] Fue uno de los cinco ganadores inaugurales del Premio George Pólya de la Sociedad de Matemáticas Industriales y Aplicadas , compartiéndolo con sus compañeros teóricos de Ramsey Klaus Leeb, Bruce Rothschild , Alfred Hales y Robert I. Jewett. [36] También fue uno de los dos ganadores inaugurales de la Medalla Euler del Instituto de Combinatoria y sus Aplicaciones , el otro fue Claude Berge . [37]
Graham fue elegido miembro de la Academia Nacional de Ciencias en 1985. [38] En 1999 fue incluido como miembro de la ACM "por sus contribuciones fundamentales al análisis de algoritmos, en particular el análisis del peor caso de heurísticas, la teoría de la programación y la geometría computacional". [39] Se convirtió en miembro de la Sociedad de Matemáticas Industriales y Aplicadas en 2009; el premio al miembro citó sus "contribuciones a las matemáticas discretas y sus aplicaciones". [40] En 2012 se convirtió en miembro de la Sociedad Matemática Estadounidense . [41]
Graham fue un orador invitado en el Congreso Internacional de Matemáticos de 1982 (celebrado en 1983 en Varsovia), [13] hablando sobre "Desarrollos recientes en la teoría de Ramsey". [A84] Fue dos veces profesor de Josiah Willard Gibbs , en 2001 y 2015. [13] La Asociación Matemática de América le otorgó tanto el Premio Carl Allendoerfer por su artículo "Steiner Trees on a Checkerboard" con Chung y Martin Gardner en Mathematics Magazine (1989), [A89b] [42] y el Premio Lester R. Ford por su artículo "A whirlwind tour of computational geometry" con Frances Yao en American Mathematical Monthly (1990). [A90] [43] Su libro Magical Mathematics con Persi Diaconis [B6] ganó el Premio Euler del Libro . [44]
Las actas de la conferencia Integers 2005 se publicaron como un homenaje por el 70.º cumpleaños de Ron Graham. [45] Otro homenaje, derivado de una conferencia celebrada en 2015 en honor del 80.º cumpleaños de Graham, se publicó en 2018 como el libro Connections in discrete mathematics: a celebration of the work of Ron Graham . [46]
{{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace ){{cite journal}}: CS1 maint: publicación periódica sin título ( enlace ) Kleitman, Daniel (diciembre de 2019). “Solo conectar”. Inferencias . 5 (1).{{cite journal}}: CS1 maint: publicación periódica sin título ( enlace ){{cite journal}}: CS1 maint: publicación periódica sin título ( enlace )Actualizado para la 2da ed., Zbl 0705.05061.{{cite journal}}: CS1 maint: publicación periódica sin título ( enlace ){{cite journal}}: CS1 maint: publicación periódica sin título ( enlace ){{cite journal}}: CS1 maint: publicación periódica sin título ( enlace ){{cite journal}}: CS1 maint: publicación periódica sin título ( enlace ){{cite journal}}: CS1 maint: publicación periódica sin título ( enlace ){{cite journal}}: CS1 maint: publicación periódica sin título ( enlace ){{cite journal}}: CS1 maint: publicación periódica sin título ( enlace ){{cite journal}}: CS1 maint: publicación periódica sin título ( enlace ){{cite journal}}: CS1 maint: publicación periódica sin título ( enlace )Reseña de la 2da ed, Zbl 0836.00001.{{cite journal}}: CS1 maint: publicación periódica sin título ( enlace )Revisión de 2da ed (1997), MR 1397498.{{cite journal}}: CS1 maint: publicación periódica sin título ( enlace ){{cite journal}}: CS1 maint: publicación periódica sin título ( enlace ){{cite journal}}: CS1 maint: publicación periódica sin título ( enlace ){{cite journal}}: CS1 maint: publicación periódica sin título ( enlace ){{cite journal}}: CS1 maint: publicación periódica sin título ( enlace ){{cite journal}}: CS1 maint: publicación periódica sin título ( enlace ){{cite journal}}: CS1 maint: publicación periódica sin título ( enlace ){{cite journal}}: CS1 maint: publicación periódica sin título ( enlace ){{cite journal}}: CS1 maint: publicación periódica sin título ( enlace ){{cite journal}}: CS1 maint: publicación periódica sin título ( enlace ){{cite journal}}: CS1 maint: publicación periódica sin título ( enlace ){{cite journal}}: CS1 maint: publicación periódica sin título ( enlace ){{cite journal}}: CS1 maint: publicación periódica sin título ( enlace ){{cite journal}}: CS1 maint: publicación periódica sin título ( enlace )