Ronald graham
Ronald Lewis Graham (31 de octubre de 1935 - 6 de julio de 2020) fue un matemático estadounidense reconocido por la American Mathematical Society como "uno de los principales arquitectos del rápido desarrollo mundial de matemáticas discretas en los últimos años". Fue presidente tanto de la Sociedad Matemática Estadounidense 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 Bell Labs y más tarde en la Universidad de California, San Diego. Hizo un trabajo importante en teoría de programación, geometría computacional, teoría de Ramsey y cuasi-aleatoriedad, 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 Ripley's Believe It or Not! por ser no solo "uno de los matemáticos más destacados del mundo", sino también un consumado trampolinista y malabarista. Se desempeñó como presidente de la International Jugglers' Asociación.
Biografía
Graham nació en Taft, California, el 31 de octubre de 1935; su padre era trabajador de un campo petrolero y más tarde marino mercante. A pesar del interés posterior de Graham por la gimnasia, era pequeño y no atlético. Creció mudándose con frecuencia entre California y Georgia, saltándose varios grados de la escuela en estas mudanzas y nunca permaneciendo en ninguna escuela más de un año. 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.
Después de tres años, cuando expiró su beca, se mudó a la Universidad de California, Berkeley, oficialmente como estudiante de ingeniería eléctrica, pero también estudió teoría de números con Derrick Henry Lehmer y ganó un título como campeón de trampolín del estado de California. Se alistó en la Fuerza Aérea de los Estados Unidos en 1955, cuando alcanzó la edad de elegibilidad, salió de Berkeley sin un título y estuvo estacionado en Fairbanks, Alaska, donde finalmente completó una licenciatura en física en 1959 en la Universidad de Alaska Fairbanks. Al regresar a la Universidad de California, Berkeley para realizar estudios de posgrado, recibió su Ph.D. en matemáticas en 1962. Su disertación, supervisada por Lehmer, fue Sobre sumas finitas de números racionales. Mientras era estudiante de posgrado, se mantuvo actuando en un trampolín en un circo y se casó con Nancy Young, una estudiante de matemáticas de pregrado en Berkeley; tuvieron dos hijos.
Después de completar su doctorado, Graham comenzó a trabajar en 1962 en Bell Labs y luego 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 prolífico matemático húngaro Paul Erdős (1913–1996), quien se convirtió en un amigo cercano y frecuente colaborador de investigación. Graham estaba disgustado por haber sido 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. Graham luego popularizó el concepto del número de Erdős, una medida de distancia de Erdős en la red de colaboración de matemáticos; 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 frecuente coautor Fan Chung.
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 fue presidente de la American Mathematical Society de 1993 a 1994. Se convirtió en científico jefe de los laboratorios en 1995 Se retiró de AT&T en 1999 después de 37 años de servicio allí, y se mudó a la Universidad de California, San Diego (UCSD), como profesor de Informática y Ciencias de la Información de Irwin and Joan Jacobs. En UCSD, también se convirtió en científico jefe del Instituto de Telecomunicaciones y Tecnología de la Información de California. En 2003–04, fue presidente de la Asociación Matemática de América.
Graham murió de bronquiectasias el 6 de julio de 2020, a los 84 años, en La Jolla, California.
Contribuciones
Graham hizo contribuciones importantes en múltiples áreas de las matemáticas y la informática teórica. Publicó unos 400 artículos, una cuarta parte de ellos con Chung, y seis libros, incluido Concrete Mathematics con Donald Knuth y Oren Patashnik.[B4] The Erdős Number Project lo enumera con casi 200 coautores. Fue el asesor de doctorado de nueve estudiantes, uno en la Universidad de la Ciudad de Nueva York y la Universidad de Rutgers mientras estuvo en Bell Labs, y siete en UC San Diego.
Los temas matemáticos notables que llevan el nombre de Graham incluyen el problema de Erdős-Graham sobre las 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 Graham& # 39; la conjetura de pebbling en la teoría de grafos, el algoritmo Coffman-Graham para la programación aproximada y el dibujo de gráficos, y el algoritmo de exploración de Graham para cascos convexos. También comenzó el estudio de secuencias sin números primos, el problema de los triples pitagóricos booleanos, el polígono pequeño más grande y el empaquetamiento de cuadrados en un cuadrado.
Graham fue uno de los colaboradores de las publicaciones de G. W. Peck, una colaboración matemática seudónima llamada así por las iniciales de sus miembros, con Graham como "G".
Teoría de números
La tesis doctoral de Graham versó sobre teoría de números, sobre fracciones egipcias, al igual que el problema de Erdős-Graham sobre si cada partición de los números enteros en un número finito de clases tiene una clase cuyos recíprocos suman uno. Ernie Croot publicó una prueba en 2003. 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 de los artículos de Erdős que se publicó, lo que convierte a Butler en su coautor número 512.[A15]
En un artículo de 1964, Graham comenzó el estudio de las sucesiones sin números primos al observar que existen sucesiones 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] Donald Knuth y otros aceptaron más tarde el desafío de construir más secuencias de este tipo. El libro de Graham de 1980 con Erdős, Resultados antiguos y nuevos en la teoría de números combinatorios, proporciona una colección de problemas abiertos de una amplia gama de subáreas dentro de la teoría de números. [B1]
Teoría de Ramsey
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 una instancia de este teorema, ahora conocido como el número de Graham, que figura en el Libro Guinness de los Récords como el número más grande jamás utilizado en una prueba matemática, aunque desde entonces ha sido superado por números aún mayores como TREE(3).
Graham ofreció un premio monetario por resolver el problema de los triples pitagóricos booleanos, otro problema en la teoría de Ramsey; el premio fue reclamado en 2016. Graham también publicó dos libros sobre la teoría de Ramsey.[B2][B3]
Teoría de grafos
The Graham-Pollak theorem, which Graham published with Henry O. Pollak in two papers in 1971 and 1972,[A71b][A72a] dice que si los bordes de un n{displaystyle n}- el gráfico completo devertex se divide en subgrafos bipartitos completos, luego al menos n− − 1{displaystyle n-1} subgrafos son necesarios. Graham y Pollak proporcionaron una prueba simple usando álgebra lineal; a pesar de la naturaleza combinatoria de la declaración y múltiples publicaciones de pruebas alternativas desde su trabajo, todas las pruebas conocidas requieren álgebra lineal.
Poco después de que comenzara la investigación en grafos cuasi-aleatorios con el trabajo de Andrew Thomason, Graham publicó en 1989 un resultado con Chung y R. M. Wilson que se ha denominado "teorema fundamental de los gráficos cuasi-aleatorios", indicando que muchas definiciones diferentes de estos gráficos son equivalentes.[A89a]
La conjetura del guijarro de Graham, que aparece en un artículo de Chung de 1989, se refiere al número de guijarros de los productos cartesianos de las gráficas. A partir de 2019, sigue sin resolverse.
Algoritmos de empaquetado, programación y aproximación
Los primeros trabajos de Graham sobre la programación del taller de trabajo[A66][A69] introdujeron la aproximación del peor de los casos ratio en el estudio de los algoritmos de aproximación, y sentó las bases para el desarrollo posterior del análisis competitivo de los algoritmos en línea. Posteriormente, se reconoció que este trabajo era importante también para la teoría del empaque en contenedores, un área en la que Graham trabajó más adelante 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 una garantía algoritmo de aproximación para un mayor número de máquinas. También se ha aplicado en el dibujo de gráficos en capas.
En un artículo de encuesta 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 deben ejecutarse, las características de las tareas y recursos como requisitos de sincronización o no interrupción, y la medida de rendimiento que se optimizará. o "notación de Graham".
Geometría discreta y computacional
La exploración de Graham es un algoritmo práctico y ampliamente utilizado para cascos convexos de conjuntos de puntos bidimensionales, que se basa en ordenar los puntos y luego insertarlos en el casco en orden ordenado. Graham publicó el algoritmo en 1972.[A72c]
El problema del pequeño polígono más grande pide el polígono de mayor área 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.
En otra publicación de 1975, Graham y Erdős observaron que para empaquetar cuadrados unitarios en un cuadrado más grande con lados de longitud no entera, 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 se puede necesitar un área descubierta al menos proporcional a la raíz cuadrada de la longitud del lado; probar un límite estrecho en el área descubierta sigue siendo un problema abierto.
Probabilidad y estadística
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 elemento, la distancia entre las posiciones de la elemento 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"
- I+E≤ ≤ D≤ ≤ 2I{displaystyle I+Eleq Dleq 2I
Donde D{displaystyle D} Es la columna de Spearman, I{displaystyle Yo... 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 E{displaystyle E} es el número mínimo de intercambios de dos elementos necesarios para obtener una permutación del otro.
El proceso aleatorio Chung-Diaconis-Graham es un paseo aleatorio en los enteros modulo un extraño entero p{displaystyle p}, en el que en cada paso uno duplica el número anterior y luego añade aleatoriamente cero, 1{displaystyle 1}, o − − 1{displaystyle -1} (modulo) p{displaystyle p}). En un periódico de 1987, Chung, Diaconis y Graham estudiaron el tiempo de mezcla de este proceso, motivado por el estudio de generadores de número de seudónimos.[A87]
Malabares
Graham se convirtió en un hábil malabarista a partir de los 15 años y tenía experiencia en hacer malabarismos con hasta seis pelotas. (Aunque una foto publicada lo muestra haciendo malabares con doce pelotas, es una imagen manipulada). Le enseñó a Steve Mills, un ganador repetido del International Jugglers' Los campeonatos de la asociación, cómo hacer malabares y su trabajo con Mills ayudaron a inspirar a Mills a desarrollar el Mills' Patrón de malabarismo desordenado. Además, Graham hizo contribuciones significativas a la teoría del malabarismo, incluida una secuencia de publicaciones sobre intercambios de sitios. En 1972 fue elegido presidente de la International Jugglers' Asociación.
Premios y distinciones
En 2003, Graham ganó el premio anual Leroy P. Steele Award for Lifetime Achievement de la American Mathematical Society. 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. Fue uno de los cinco ganadores inaugurales del Premio George Pólya de la Sociedad de Matemáticas Industriales y Aplicadas, compartiéndolo con los teóricos de Ramsey Klaus Leeb, Bruce Rothschild, Alfred Hales y Robert I. Jewett. 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.
Graham fue elegido miembro de la Academia Nacional de Ciencias en 1985. En 1999 fue admitido como miembro de ACM "por sus contribuciones fundamentales al análisis de algoritmos, en particular, el análisis heurístico del peor de los casos, la teoría de programación y geometría computacional". Se convirtió en miembro de la Sociedad de Matemáticas Industriales y Aplicadas en 2009; el premio de compañero citó sus "contribuciones a las matemáticas discretas y sus aplicaciones". En 2012 se convirtió en miembro de la American Mathematical Society.
Graham fue un orador invitado en el Congreso Internacional de Matemáticos de 1982 (celebrado en Varsovia en 1983), hablando sobre "Desarrollos recientes en la teoría de Ramsey".[A84] Fue dos veces Josiah Willard Gibbs Lecturer, en 2001 y 2015. La Asociación Matemática de América le otorgó el Premio Carl Allendoerfer por su trabajo "Steiner Trees on a Checkerboard" con Chung y Martin Gardner en Mathematics Magazine (1989),[A89b] y el premio Lester R. Ford por su artículo "A whirlwind recorrido por la geometría computacional" con Frances Yao en el American Mathematical Monthly (1990).[A90] Su libro Magical Mathematics con Persi Diaconis[B6] ganó el Euler Book Prize.
Las actas de la conferencia Integers 2005 se publicaron como celebración del 70 cumpleaños de Ron Graham. 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.
Publicaciones seleccionadas
Libros
| B1. | Resultados antiguos y nuevos en la teoría de números combinatorios. Con Paul Erdős. Monographie 28, L'Enseignement Mathématique, 1980. |
| B2. | Ramsey Theory. Con Bruce Rothschild y Joel Spencer. Wiley, 1980; 2a edición, 1990. |
| B3. | Rudimentos de la Teoría Ramsey. American Mathematical Society, 1981; 2a edición, con Steve Butler, 2015. |
| B4. | Matemáticas concretas: una base para la ciencia informática. Con Donald Knuth y Oren Patashnik. Addison-Wesley, 1989; 2a edición, 1994. |
| B5. | Erdős en Graphs. Su legado de problemas sin resolver. Con Fan Chung. A K Peters, 1998. |
| B6. | Matemáticas Mágicas: las ideas matemáticas que animan grandes trucos mágicos. Con Persi Diaconis. Princeton University Press, 2011. |
Volúmenes editados
| V1. | Handbook of Combinatorics. Editado con Martin Grötschel y László Lovász. MIT Press, 1995. |
| V2. | Las matemáticas de Paul Erdős. Editado con Jaroslav Nešetřil. 2 volúmenes. Springer, 1997; 2nd ed., 2013. |
Artículos
| A64. | Graham, Ronald L. (1964). "Una secuencia tipo Fibonacci de números compuestos" (PDF). Revista Matemática. 37 (5): 322-324. doi:10.2307/2689243. JSTOR 2689243. MR 1571455. Zbl 0125.02103. |
| A66. | Graham, R. L. (1966). "Bounds for certain multiprocessing anomalies" (PDF). Bell System Technical Journal. 45 (9): 1563–1581. doi:10.1002/j.1538-7305.1966.tb01709.x. Zbl 0168.40703. |
| A69. | Graham, R. L. (1969). "Bounds on multiprocessing timing anomalies" (PDF). SIAM Journal on Applied Mathematics. 17 (2): 416-429. doi:10.1137/0117039. MR 0249214. Zbl 0188.23101. |
| A71a. | Graham, R. L.; Rothschild, B. L. (1971). "Teorema de Ramsey para conjuntos de n-parameter" (PDF). Transacciones de la Sociedad Americana de Matemáticas. 159: 257–292. doi:10.1090/S0002-9947-1971-0284352-8. JSTOR 1996010. MR 0284352. Zbl 0233.05003. |
| A71b. | Graham, R. L.; Pollak, H. O. (1971). "En el problema de la solución para el cambio de bucle" (PDF). Bell System Technical Journal. 50 (8): 2495–2519. doi:10.1002/j.1538-7305.1971.tb02618.x. MR 0289210. Zbl 0228.94020. |
| A72a. | Graham, R. L.; Pollak, H. O. (1972). "En la incrustación de gráficos en cubos aplastados". Graph theory and applications (Proc. Conf., Western Michigan Univ., Kalamazoo, Mich., 1972; dedicated to the memory of J. W. T. Youngs) (PDF). Conferencia Notas en Matemáticas. Vol. 303. pp. 99–110. MR 0332576. Zbl 0251.05123. |
| A72b. | Coffman, E. G. Jr.; Graham, R. L. (1972). "Optimal scheduling for two-processor systems" (PDF). Acta Informatica. 1 (3): 200–213. doi:10.1007/bf00288685. MR 0334913. S2CID 40603807. Zbl 0248.68023. |
| A72c. | Graham, R. L. (1972). "Un algoritmo eficiente para determinar el casco convexo de un conjunto plano finito" (PDF). Cartas de procesamiento de información. 1 (4): 132–133. doi:10.1016/0020-0190(72)90045-2. Zbl 0236.68013. |
| A74. | Johnson, D. S.; Demers, A.; Ullman, J. D.; Garey, M. R.; Graham, R. L. (1974). "El mejor rendimiento de la maleta se limita a simples algoritmos de embalaje unidimensional" (PDF). SIAM Journal on Computing. 3 (4): 299-325. doi:10.1137/0203025. MR 0434396. Zbl 0297.68028. |
| A75a. | Graham, R. L. (1975). "El hexágono pequeño más grande" (PDF). Journal of Combinatorial Teoría. Serie A. 18 (2): 165–170. doi:10.1016/0097-3165(75)90004-7MR 0360353. Zbl 0299.52006. |
| A75b. | Erdős, P.; Graham, R. L. (1975). "En los cuadrados de embalaje con cuadrados iguales" (PDF). Journal of Combinatorial Teoría. Serie A. 19: 119–123. doi:10.1016/0097-3165(75)90099-0MR 0370368. Zbl 0324.05018. |
| A77. | Diaconis, Persi; Graham, R. L. (1977). "Spearman's footrule as a measure of disarray". Journal of the Royal Statistical Society. 39 (2): 262–268. doi:10.1111/j.2517-6161.1977.tb01624.x. JSTOR 2984804. MR 0652736. Zbl 0375.62045. |
| A79. | Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H. G. (1979). "Optimización y aproximación en secuenciación y programación determinística: una encuesta" (PDF). Annals of Discrete Mathematics. 5: 287–326. doi:10.1016/S0167-5060(08)70356-X. ISBN 9780080867670. MR 0558574. Zbl 0411.90044. |
| A84. | Graham, R. L. (1984). "Acontecimientos recientes en la teoría de Ramsey" (PDF). Proceedings of the International Congress of Mathematicians, Vol. 1, 2 (Warsaw, 1983). Varsovia: PWN. pp. 1555–1567. MR 0804796. Zbl 0572.05009. |
| A87. | Chung, F. R. K.; Diaconis, Persi; Graham, R. L. (1987). "Caminos de baile que surgen en la generación de números aleatorios" (PDF). Annals of Probability. 15 (3): 1148–1165. doi:10.1214/aop/1176992088. JSTOR 2244046. MR 0893921. Zbl 0622.60016. |
| A89a. | Chung, F. R. K.; Graham, R. L.; Wilson, R. M. (1989). "Gígrafos de cuasi aleatorio" (PDF). Combinatorica. 9 (4): 345–362. doi:10.1007/BF02125347. MR 1054011. S2CID 17166765. Zbl 0715.05057. |
| A89b. | Chung, Fan; Gardner, Martin; Graham, Ron (1989). "Steiner trees on a checkerboard" (PDF). Revista Matemática. 62 (2): 83–96. doi:10.2307/2690388. JSTOR 2690388. MR 0991536. Zbl 0681.05018. |
| A90. | Graham, Ron; Yao, Frances (1990). "Una gira de torbellino de geometría computacional" (PDF). American Mathematical Mensual. 97 (8): 687–701. doi:10.2307/2324575. JSTOR 2324575. MR 1072812. Zbl 0712.68097. |
| A15. | Butler, Steve; Erdős, Paul; Graham, Ron (2015). "Facciones egipcias con cada denominador que tiene tres divisores principales distintos" (PDF). Integers. 15: A51. MR 3437526. Zbl 1393.11030. |
Contenido relacionado
Ernesto thayer
Abadía de Edwin Austin
Alberto Altdorfer