Hoffmann, Alan

Alan Jerome Hoffman ( Ing.  Alan Jerome Hoffman ; 30 de mayo de 1924, Nueva York  - 18 de enero de 2021 [2] ) fue un matemático estadounidense que trabajó en el IBM T. J. Watson Research Center . Editor y fundador de la revista. Álgebra Lineal y sus Aplicaciones . Contribuyó a la optimización combinatoria y la teoría de valores propios de grafos. Hoffman, junto con Robert Singleton, construyeron el gráfico de Hoffman-Singleton , que es un gráfico de Moore único de grado 7 y diámetro 2 [3] .  

Biografía

Alan Hoffman ingresó a la Universidad de Columbia en 1940 y recibió una beca Pulitzer en 1940 a la edad de 16 años. La Segunda Guerra Mundial interrumpió los estudios de Hoffman, fue llamado a filas en febrero de 1943 y sirvió en el Ejército de los EE. UU. de 1943 a 1946, tanto en Europa como en el Pacífico. Durante el entrenamiento básico en la escuela de artillería antiaérea, consideró la posibilidad de desarrollar los axiomas de la geometría de círculos [2] .

A su regreso a Columbia en el otoño de 1946, completó su tesis doctoral sobre los fundamentos de la geometría de inversión en 1950. Después de eso, Hoffman pasó un año en el Instituto de Estudios Avanzados de Princeton (la oficina contigua a la suya estaba ocupada por Albert Einstein ) [2] .

Carrera temprana

El primer trabajo de Hoffman fue en la División de Matemáticas Aplicadas de la Oficina Nacional de Normas . En la Oficina, Hoffman se convirtió en un líder en un nuevo campo de la ciencia, la programación lineal . Hoffman fue un organizador clave del influyente Segundo Simposio de Programación Lineal celebrado en la Oficina en enero de 1955 [2] .

En 1956, Hoffman dejó la Oficina y se mudó a Inglaterra para trabajar como investigador de comunicaciones en la sucursal de Londres de la Oficina de Investigación Naval. A medida que el año llegaba a su fin en el extranjero, a Hoffman se le ofrecieron dos puestos en empresas industriales de la ciudad de Nueva York: uno en un pequeño grupo de investigación matemática en el incipiente Laboratorio de Investigación de IBM y el otro en la sede de General Electric Company . Hoffman eligió un papel en una organización más establecida. La dirección le permitió estudiar matemáticas, si esto no interfería con el desempeño de las funciones que se le asignaban, y Hoffman continuó con su investigación matemática, completamente ajena a su trabajo principal. En 1961, aceptó una invitación para unirse al Centro de Investigación T. J. Watson de IBM 2 ] .

Carrera en IBM

Durante su carrera en IBM, Hoffman publicó más de 200 artículos científicos, más de un tercio de ellos en coautoría. Su rango matemático cubrió muchas áreas de las matemáticas, desde el álgebra hasta la investigación de operaciones [2] .

Resumen de contribuciones matemáticas (a partir de sus notas en Documentos seleccionados de Alan Hoffman) [4] .

El trabajo de Hoffmann sobre geometría, comenzando con su tesis "Sobre los fundamentos de la geometría de inversión", incluyó pruebas de las propiedades de los planos afines, así como el estudio de puntos de relación de planos proyectivos finitos, condiciones sobre regularidades de unión e intersección de conos ( derivado en gran parte de su generalización de sus primeros resultados sobre el rango de las matrices reales). Presentó una prueba alternativa, basada en axiomas para algunos sistemas abstractos de conjuntos convexos, de un resultado (Scarf y otros) sobre el número de desigualdades necesarias para determinar la solución a un problema de programación entera. El teorema sobre este sistema abstracto parece estar estrechamente relacionado con los antimatroides (también conocidos como geometrías convexas), aunque la conexión no se ha explorado por completo.

El trabajo de Hoffman sobre combinatoria ha ampliado nuestra comprensión de varias clases de gráficos. Una conferencia de 1956 de G. Hajos sobre gráficos de intervalo condujo a la caracterización de gráficos de comparabilidad de Hoffman y más tarde, a través de la colaboración con Paul Gilmour, al teorema de GH (también atribuido a A. Guia-Ury). Inspirándose en el algoritmo de coincidencia de Edmond, Hoffman colaboró ​​con Ray Fulkerson y M. McAndrew Hoffman para caracterizar conjuntos de números enteros que pudieran coincidir con las potencias y los límites de cada par de vértices en dicho gráfico. Además, consideraron qué gráficos en la clase de todos los gráficos que tienen un conjunto dado de grados y límites en el número de aristas pueden transformarse mediante un determinado conjunto de intercambios en cualquier otro conjunto de la clase. Las demostraciones están estrechamente relacionadas con la importante noción de la base de Hilbert. Un artículo sobre cuadrados latinos autoortogonales, coescrito con los coautores de IBM Don Coppersmith y R. Brighton, se inspiró en una solicitud para programar un cónyuge de evitación de dobles mixtos para un club de raqueta local. Tiene la distinción de ser el único artículo que Hoffman ha discutido fuera de la comunidad matemática.

Los conjuntos parcialmente ordenados han sido un tema de estudio frecuente para Hoffman. Un artículo de 1977 con DE Schwartz utiliza la dualidad de programación lineal para generalizar la generalización de 1976 de Green y Kleitman del teorema de descomposición de Dilworth para posets, otro ejemplo del papel unificador que desempeña la dualidad en muchos resultados combinatorios.

A lo largo de su carrera, Hoffman ha buscado pruebas alternativas simples y elegantes de teoremas establecidos. Estas pruebas alternativas a menudo llevaron a generalizaciones y extensiones. A fines de la década de 1990, colaboró ​​​​con Cao, Chvatal y Vince para desarrollar una prueba alternativa utilizando métodos elementales en lugar del álgebra lineal o el teorema de la matriz cuadrada 0-1 de Reiser.

El trabajo de Hoffman sobre desigualdades de matrices y valores propios es la base de cualquier curso de teoría de matrices. De particular encanto, en línea con su afición por unificar enfoques, es su artículo de 1975 sobre funciones G lineales. Aunque la demostración de esta variación de Gershgorin es más larga y complicada que las demás, cubre todas las variaciones de Ostrovsky y muchas variaciones adicionales como casos especiales.

Hoffman fue un anciano inspirador, pero no participó activamente en el desarrollo de IBM de una serie de productos para programación lineal y entera. Sin embargo, continuó explorando los aspectos combinatorios y algebraicos de la programación lineal y las desigualdades lineales, incluida una deliciosa abstracción de la dualidad de la programación lineal (1963). También continuó usando las propiedades de las desigualdades lineales para probar (o volver a probar más elegantemente) los resultados de la convexidad.

En colaboración con Shmuel Winograd, también miembro de IBM en el departamento de matemáticas, se desarrolló un algoritmo eficiente para encontrar todas las distancias más cortas en una red dirigida utilizando pseudomultiplicación de matrices. Una serie de artículos sobre poliedros de celosía (algunos con Don Schwarts) introdujeron la noción de poliedros de celosía, lo que llevó a otro ejemplo más de dualidad combinatoria.

Después de colaborar con Ray Fulkerson y Rosa Oppenheim en matrices balanceadas, Hoffman generalizó el resultado de corte mínimo de flujo máximo de Ford-Fulkerson a otros casos (flujo en nodos, arcos no dirigidos, etc.), proporcionando prueba de que todos los casos conocidos previamente eran especiales. casos. Este artículo también introdujo el concepto (pero de nuevo, no el nombre) de entero dual completo, la idea detrás de la mayoría de las aplicaciones de programación lineal para probar teoremas combinatorios extremos.

A lo largo de su carrera, Hoffman estudió una clase de problemas de programación entera que podían resolverse maximizando sucesivamente las variables en algún orden. Un ejemplo de ello es el problema del transporte completo cuando el factor de costo exhibe una propiedad especial descubierta hace más de un siglo por el matemático francés Gaspard Monge. Este enfoque, llamado simplemente "simple" en el artículo de Hoffman, más tarde fue considerado "codicioso" por Edmonds y Fulkerson. La propiedad de Monge genera un antimatroid, y gracias al uso de este antimatroid, el resultado de Hoffman puede extenderse fácilmente al caso de problemas de transporte incompleto. Hoffman reutilizó el término "codicioso" para describir una subclase de matrices 0-1 para las cuales el programa lineal dual puede resolverse mediante un algoritmo codicioso para todos los lados derechos y todas las funciones objetivo con coeficientes decrecientes (por índice variable). . Junto con Kolen y Sakarovich, demostró que para estas matrices el programa entero correspondiente tiene una solución entera óptima para datos enteros. Un artículo elegante y conciso de 1992 caracteriza las matrices 0-1 para las cuales los problemas de empaquetamiento y cobertura pueden resolverse utilizando un enfoque codicioso. Proporciona unificación de resultados para los problemas de árbol de expansión mínimo y ruta más corta. Su último artículo sobre el tema, "Sobre algoritmos codiciosos, conjuntos parcialmente ordenados y funciones submodulares", en coautoría con Dietrich, apareció en 2003.

Hoffman, junto con Robert Singleton, construyó el gráfico de Hoffman-Singleton [5] , que es un gráfico de Moore único de grado 7 y diámetro 2 [3] . En 1963, construyó el Hoffman Graph , que, aunque coespectral al gráfico del hipercubo de cuatro dimensiones Q 4 [6] , pero cuyo radio es igual a 3 (existen tales vértices, cuyo camino más corto a cualquier otro vértice del gráfico consta de no más de tres aristas), mientras que el radio del gráfico hipercubo Q 4 es igual a 4 [7] .

Premios y reconocimientos

Hoffman fue elegido miembro de la Academia Nacional de Ciencias en 1982 [1] , de la Academia Estadounidense de las Artes y las Ciencias en 1987 [1] y de la primera membresía del Instituto de Investigación de Operaciones y Ciencias Administrativas (INFORMS) en 2002 [8] . En 1992, junto con Philip Wolf (también de IBM), fue galardonado con el Premio Teórico John von Neumann [1] . Doctor Honorario en Ciencias del Technion (Instituto de Tecnología de Israel) desde 1986.

Durante su larga carrera, Hoffman formó parte del equipo editorial de once revistas y fue editor y fundador de la revista inglesa.  Álgebra lineal y sus aplicaciones [1] . En una biografía publicada en la edición del 65 cumpleaños de Hoffman, Uriel Rothblum escribió que “Además de sus logros científicos y profesionales, Hoffman tiene una habilidad sin igual para disfrutar todo lo que hace. Le encanta cantar, jugar al ping-pong, los juegos de palabras, las historias ingeniosas y, quizás más que cualquier otra cosa, las matemáticas .

Publicaciones seleccionadas

• Hoffman AJ, Jacobs W. Patrones suaves de producción  //  Management Science. - 1954. - vol. 1 , edición. 1 . — págs. 86–91 .
• Hoffman, AJ, Singleton, RR Gráficos de Moore con diámetro 2 y 3 // IBM Journal of Research and Development. - 1960. - V. 5 , núm. 4 . — S. 497–504 . -doi : 10.1147/ rd.45.0497 .
• Hoffman AJ Sobre el polinomio de un gráfico   // Amer . Matemáticas. Mensual. - 1963. - vol. 70 . - P. 30-36 .
• Hoffman AJ, Wolfe P. Historia del problema del viajante de comercio // El problema del viajante de comercio  (ing.) / Lawler EL, Lenstra JK, Rinnooy Kan AHG y Shmoys DB, eds. —John Wiley, 1985.

Una lista completa de publicaciones se da en la página personal [1] .

Notas

1. ↑ 1 2 3 4 5 6 Página personal, IBM. Alan Hoffmann  . Investigación de IBM. Consultado el 14 de noviembre de 2011. Archivado desde el original el 14 de marzo de 2012.
2. ↑ 1 2 3 4 5 6 7 Biografía de Alan J. Hoffman
3. ↑ 12 d.E. _ Brouwer y JH van Lint. Gráficos muy regulares y geometrías parciales // Enumeración y diseño  (inglés) / DH Jackson, & SA Vanstone (Eds.). – Prensa Académica Inc. - Pág. 85-122.
4. ↑ Hoffman, AJ (Alan Jerome), 1924-. Documentos seleccionados de Alan Hoffman con comentarios . - River Edge, Nueva Jersey: World Scientific, 2003. - ISBN 978-981-279-693-6 .
5. ↑ Hoffman, AJ, Singleton, R. R. Moore gráficos con diámetro 2 y 3, 1960 .
6. ↑ Hoffman, A.J. Sobre el polinomio de un gráfico, 1963 .
7. ↑ Gráfico de Weisstein, Eric W. Hoffman  en el sitio web Wolfram MathWorld .
8. ↑ Fellows:  Lista alfabética . Instituto de Investigación Operativa y Ciencias Administrativas. Consultado: 9 de octubre de 2019.

sitios temáticos	genealogía matemática zbMATH Abierto
En catálogos bibliográficos TIERRA : 1103166549 ISNI : 0000 0001 1463 2648 J9U : 987007431043105171 LCCN : n78042498 NLG : 221689 NTA : 07088692X NUKAT : n2006011297 SUDOC : 164195823 VIAF : 110277368 WorldCat VIAF : 110277368