Ronald Lewis Graham (31 de octubre de 1935 - 6 de julio de 2020) [1] fue un matemático estadounidense acreditado por la Sociedad Estadounidense de Matemáticas 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 Sociedad Estadounidense de Matemáticas como de la Asociación Matemática de América , y sus honores incluyeron 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 los Laboratorios Bell y más tarde en la Universidad de California, San Diego . Hizo un trabajo importante en teoría de la programación , geometría computacional , teoría de Ramsey y cuasi-aleatoriedad , [3] y muchos temas de matemáticas llevan su nombre. Publicó seis libros y alrededor de 400 artículos, y tuvo cerca de 200 coautores, incluidos muchos trabajos en colaboración con su esposa Fan Chung y con Paul Erdős .
Graham ha aparecido en Ripley's Believe It or Not! por ser no sólo "uno de los matemáticos más destacados del mundo", sino también un consumado trampolinista y malabarista. Se desempeñó como 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 petrolero y más tarde de la marina mercante. A pesar del interés posterior de Graham por la gimnasia, era pequeño y no deportista. [7] Creció movié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 fue 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 mudó a la Universidad de California, Berkeley , oficialmente como estudiante de ingeniería eléctrica pero también estudiando teoría de números con Derrick Henry 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 estuvo destinado en Fairbanks, Alaska , donde finalmente completó una licenciatura en física en 1959. en la Universidad de Alaska Fairbanks . [1] Al regresar a la Universidad de California, 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 un trampolín en un circo, [8] y se casó con Nancy Young, una estudiante universitaria de matemáticas en Berkeley; tuvieron dos hijos. [1]
Tras completar su doctorado, Graham empezó a trabajar en 1962 en los Laboratorios Bell y posteriormente como Director de Ciencias de la Información en los Laboratorios AT&T , ambos en Nueva Jersey . En 1963, en una conferencia en Colorado, conoció al prolífico matemático húngaro Paul Erdős (1913-1996), [1] quien se convirtió en un amigo cercano y frecuente colaborador de investigación. A Graham le disgustó que Erdős, que entonces ya era de mediana edad, lo golpeara en ping-pong ; 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 más tarde popularizó el concepto de número de Erdős , una medida de distancia de Erdős en la red de colaboración de matemáticos; [10] [8] sus numerosos trabajos con Erdős incluyen dos libros de problemas abiertos [B1] [B5] y el último artículo póstumo de Erdős. [A15] Graham se divorció en la década de 1970; en 1983 se casó con su colega de Bell Labs y coautor frecuente Fan Chung . [1]
Mientras estuvo en Bell Labs, Graham también ocupó un puesto en la Universidad de Rutgers como profesor universitario de Ciencias Matemáticas en 1986, y sirvió como presidente de la Sociedad Estadounidense de Matemáticas de 1993 a 1994. Se convirtió en científico jefe de los laboratorios en 1995. [1 ] Se retiró de AT&T en 1999 después de 37 años de servicio allí, [11] y se mudó a la Universidad de California, San Diego (UCSD), como Profesor Dotado Irwin y Joan Jacobs de Informática y Ciencias de la Información. [1] [8] En UCSD, también se convirtió en científico jefe del Instituto de Telecomunicaciones y Tecnología de la Información de California . [8] [5] En 2003-2004, fue presidente de la Asociación Matemática de América . [1]
Graham murió de bronquiectasias [12] el 6 de julio de 2020, a la edad de 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 los de Chung, [14] y seis libros, incluido Concrete Mathematics , con Donald Knuth y Oren Patashnik . [B4] El Proyecto Número Erdős lo enumera con casi 200 coautores. [15] Fue asesor de doctorado de nueve estudiantes, uno en la City University de Nueva York y uno en la Universidad de Rutgers mientras estaba en Bell Labs, y siete en UC San Diego. [9]
Los temas notables en matemáticas que llevan el nombre de Graham incluyen 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 del guijarro de Graham en teoría de grafos , el Algoritmo de Coffman-Graham para programación aproximada y dibujo de gráficos, y algoritmo de escaneo de Graham para cascos convexos . También comenzó el estudio de las secuencias libres primos , el problema de los triples pitagóricos booleanos , el polígono pequeño más grande y el empaquetado de cuadrados en un cuadrado .
Graham fue uno de los contribuyentes a las publicaciones de GW Peck , una colaboración matemática seudónima llamada así por las iniciales de sus miembros, con Graham como "G". [dieciséis]
La tesis doctoral de Graham fue sobre teoría de números , sobre fracciones egipcias , [7] [9] al igual que el problema de Erdős-Graham sobre si, para cada partición de números enteros en un número finito de clases, una de estas clases tiene una subclase finita cuyos recíprocos suman a uno. Ernie Croot publicó una prueba en 2003. [17] Otro de los artículos de Graham sobre fracciones egipcias se publicó en 2015 con Steve Butler y (casi 20 años póstumamente) Erdős; fue el último artículo de Erdős que se publicó, lo que convirtió a Butler en su coautor número 512. [A15] [18]
En un artículo de 1964, Graham comenzó el estudio de las secuencias libres de 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, Resultados antiguos y nuevos en teoría combinatoria de números, 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 cubos combinatorios en combinatoria de palabras . [A71a] Graham dio un número grande como límite superior para un ejemplo de este teorema, ahora conocido como número de Graham , que figuraba en el Libro Guinness de los Récords como el número más grande jamás utilizado en una demostración 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 los triples pitagóricos booleanos , otro problema de la teoría de Ramsey; el premio se reclamó 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 los bordes de un gráfico completo de vértice se dividen en subgrafos bipartitos completos , entonces al menos subgrafos Se necesitan. Graham y Pollak proporcionaron una prueba sencilla utilizando álgebra lineal ; A pesar de la naturaleza combinatoria del enunciado y 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 gráficos cuasi aleatorios con el trabajo de Andrew Thomason, Graham publicó en 1989 un resultado con Chung y RM Wilson que ha sido llamado el "teorema fundamental de los gráficos cuasi aleatorios", afirmando que muchas definiciones diferentes de estos gráficos son equivalentes. [A89a] [24]
La conjetura del guijarro de Graham , que aparece en un artículo de Chung de 1989, [25] se refiere al número de guijarros de productos cartesianos de gráficos . A partir de 2019 [actualizar], sigue sin resolverse. [26]
Los primeros trabajos de Graham sobre la programación de talleres [A66] [A69] introdujeron la relación de aproximación del peor de los casos 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] Posteriormente se reconoció que este trabajo era importante también para la teoría del embalaje de contenedores , [28] un área en la que Graham trabajó más tarde de manera más explícita. [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 estudio sobre algoritmos de programación publicado en 1979, Graham y sus coautores introdujeron una notación de tres símbolos para clasificar los problemas de programación teórica según el sistema de máquinas en las que deben ejecutarse, las características de las tareas y los recursos, como los requisitos de sincronización. o no interrupción, y la medida de desempeño 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 práctico y ampliamente utilizado para cascos convexos de conjuntos de puntos bidimensionales, que se basa en clasificar los puntos y luego insertarlos en el casco en orden. [31] Graham publicó el algoritmo en 1972. [A72c]
El problema del polígono pequeño más grande solicita el polígono de mayor área para un diámetro determinado. 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 fue finalmente probada 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 de lados no enteras, se pueden usar cuadrados inclinados para dejar un área descubierta que es sublineal en la longitud de los lados del cuadrado más grande, a diferencia de lo obvio. embalaje 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 del lado; demostrar 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 pie de Spearman, una medida de correlación de rango que compara dos permutaciones sumando, sobre cada ítem, la distancia entre las posiciones del ítem en las dos permutaciones. [A77] Compararon esta medida con otros métodos de correlación de rangos, lo que resultó en 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 paseo aleatorio sobre números enteros módulo un 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 generadores de números pseudoaleatorios . [A87] [35]
Graham se convirtió en un malabarista capaz a partir de los 15 años y tenía práctica en hacer malabarismos con hasta seis pelotas. [4] (Aunque una foto publicada lo muestra haciendo malabares con doce bolas, [5] es una imagen manipulada. [3] ) Le enseñó a Steve Mills , ganador repetido de los campeonatos de la Asociación Internacional de Malabaristas, cómo hacer malabarismos 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 sobre siteswaps . En 1972 fue elegido presidente de la Asociación Internacional de Malabaristas . [4]
En 2003, Graham ganó el premio anual Leroy P. Steele a la trayectoria de la Sociedad Estadounidense de Matemáticas . 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 colegas 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 , siendo el otro Claude Berge . [37]
Graham fue elegido miembro de la Academia Nacional de Ciencias en 1985. [38] En 1999 fue admitido como miembro de la ACM "por sus contribuciones fundamentales al análisis de algoritmos, en particular el análisis de heurísticas en el peor de los casos, la teoría de la programación y geometría Computacional". [39] Se convirtió en miembro de la Sociedad de Matemáticas Industriales y Aplicadas en 2009; El becario 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ó el premio Carl Allendoerfer por su artículo "Steiner Trees on a Checkerboard" con Chung y Martin Gardner en la revista Mathematics ( 1989), [A89b] [42] y el premio Lester R. Ford por su artículo "Un recorrido relámpago por la geometría computacional" con Frances Yao en el American Mathematical Monthly (1990). [A90] [43] Su libro Magical Mathematics con Persi Diaconis [B6] ganó el Euler Book Prize . [44]
Las actas de la conferencia Integers 2005 se publicaron como celebración del 70 cumpleaños de Ron Graham. [45] Otro festschrift, derivado de una conferencia celebrada en 2015 en honor al 80 cumpleaños de Graham, se publicó en 2018 como el libro Conexiones en matemáticas discretas: una celebración del trabajo de Ron Graham . [46]
{{cite journal}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace ){{cite journal}}: Mantenimiento CS1: publicación periódica sin título ( enlace ) Kleitman, Daniel (diciembre de 2019). "Sólo conectar". Inferencias . 5 (1).{{cite journal}}: Mantenimiento CS1: publicación periódica sin título ( enlace ){{cite journal}}: Mantenimiento CS1: publicación periódica sin título ( enlace )Actualizado para la 2.ª ed., Zbl 0705.05061.{{cite journal}}: Mantenimiento CS1: publicación periódica sin título ( enlace ){{cite journal}}: Mantenimiento CS1: publicación periódica sin título ( enlace ){{cite journal}}: Mantenimiento CS1: publicación periódica sin título ( enlace ){{cite journal}}: Mantenimiento CS1: publicación periódica sin título ( enlace ){{cite journal}}: Mantenimiento CS1: publicación periódica sin título ( enlace ){{cite journal}}: Mantenimiento CS1: publicación periódica sin título ( enlace ){{cite journal}}: Mantenimiento CS1: publicación periódica sin título ( enlace ){{cite journal}}: Mantenimiento CS1: publicación periódica sin título ( enlace ){{cite journal}}: Mantenimiento CS1: publicación periódica sin título ( enlace )Revisión de la 2.ª ed., Zbl 0836.00001.{{cite journal}}: Mantenimiento CS1: publicación periódica sin título ( enlace )Revisión de la 2.ª ed. (1997), MR 1397498.{{cite journal}}: Mantenimiento CS1: publicación periódica sin título ( enlace ){{cite journal}}: Mantenimiento CS1: publicación periódica sin título ( enlace ){{cite journal}}: Mantenimiento CS1: publicación periódica sin título ( enlace ){{cite journal}}: Mantenimiento CS1: publicación periódica sin título ( enlace ){{cite journal}}: Mantenimiento CS1: publicación periódica sin título ( enlace ){{cite journal}}: Mantenimiento CS1: publicación periódica sin título ( enlace ){{cite journal}}: Mantenimiento CS1: publicación periódica sin título ( enlace ){{cite journal}}: Mantenimiento CS1: publicación periódica sin título ( enlace ){{cite journal}}: Mantenimiento CS1: publicación periódica sin título ( enlace ){{cite journal}}: Mantenimiento CS1: publicación periódica sin título ( enlace ){{cite journal}}: Mantenimiento CS1: publicación periódica sin título ( enlace ){{cite journal}}: Mantenimiento CS1: publicación periódica sin título ( enlace ){{cite journal}}: Mantenimiento CS1: publicación periódica sin título ( enlace ){{cite journal}}: Mantenimiento CS1: publicación periódica sin título ( enlace )