Hoffman, Alan

Alan Hoffman
Engleză  Alan Jerome Hoffman

Graficul Hoffman-Singleton , 50 de vârfuri, 175 de muchii
Data nașterii 30 mai 1924( 30.05.1924 )
Locul nașterii New York [1]
Data mortii 18 ianuarie 2021 (96 de ani)( 2021-01-18 )
Țară  STATELE UNITE ALE AMERICII
Sfera științifică optimizare combinatorie , teoria grafurilor
Loc de munca Cercetare T. J. Watson
Alma Mater
Grad academic Ph.D
consilier științific Edgar Lorch [d]
Cunoscut ca coautor al lucrării Contele Hoffman-Singleton
Premii și premii Premiul teoretic von Neumann ( 1992 )

Alan Jerome Hoffman ( ing.  Alan Jerome Hoffman ; 30 mai 1924, New York  - 18 ianuarie 2021 [2] ) a fost un matematician american care a lucrat la IBM T. J. Watson Research Center . Redactor și fondator al revistei Algebra liniară și aplicațiile ei . A contribuit la optimizarea combinatorie și la teoria valorilor proprii a graficelor. Hoffman, împreună cu Robert Singleton, a construit graficul Hoffman-Singleton , care este un grafic Moore unic de gradul 7 și diametrul 2 [3] .  

Biografie

Alan Hoffman a intrat la Universitatea Columbia în 1940, primind o bursă Pulitzer în 1940, la vârsta de 16 ani. Al Doilea Război Mondial a întrerupt studiile lui Hoffman, acesta a fost chemat în serviciu în februarie 1943 și a servit în armata SUA din 1943 până în 1946, atât în ​​Europa, cât și în Pacific. În timpul pregătirii de bază la școala de artilerie antiaeriană, a luat în considerare posibilitatea dezvoltării axiomelor geometriei cercurilor [2] .

La întoarcerea sa în Columbia, în toamna anului 1946, și-a finalizat teza de doctorat despre fundamentele geometriei inversării în 1950. După aceea, Hoffman a petrecut un an la Institutul de Studii Avansate din Princeton (biroul de lângă el a fost ocupat de Albert Einstein ) [2] .

Cariera timpurie

Primul loc de muncă al lui Hoffman a fost în Divizia de Matematică Aplicată a Biroului Național de Standarde . La Birou, Hoffman a devenit lider într-un nou domeniu al științei, programarea liniară . Hoffman a fost un organizator cheie al celui de-al doilea simpozion de programare liniară influent ținut la Birou în ianuarie 1955 [2] .

În 1956, Hoffman a părăsit Biroul și s-a mutat în Anglia pentru a lucra ca cercetător în comunicații la filiala din Londra a Biroului de Cercetare Navală. Pe măsură ce anul se apropia în străinătate, lui Hoffman i s-au oferit două poziții la companii industriale din New York: unul într-un mic grup de cercetare matematică de la noul IBM Research Laboratory și celălalt la sediul General Electric Company . Hoffman a ales un rol într-o organizație mai stabilită. Conducerea i-a permis să studieze matematica, dacă acest lucru nu interfera cu îndeplinirea îndatoririlor care i-au fost încredințate, iar Hoffman și-a continuat cercetările matematice, complet fără legătură cu meseria sa principală. În 1961, a acceptat o invitație de a se alătura Centrului de Cercetare T. J. Watson al IBM 2] .

Cariera la IBM

În timpul carierei sale la IBM, Hoffman a publicat peste 200 de lucrări științifice, mai mult de o treime dintre ele fiind coautor. Gama sa matematică acoperea multe domenii ale matematicii, de la algebră până la cercetarea operațională [2] .

Rezumat al contribuțiilor matematice (din notele sale din Selected Papers of Alan Hoffman) [4] .

Lucrarea lui Hoffmann despre geometrie, începând cu teza sa „On the Foundations of Inversion Geometry”, a inclus dovezi ale proprietăților planurilor afine, precum și studiul punctelor de relație ale planurilor proiective finite, condițiile privind regularitățile de unire și intersecție a conurilor ( derivat în mare parte din generalizarea sa a rezultatelor sale anterioare privind rangul matricelor reale). El a prezentat o demonstrație alternativă, bazată pe axiome pentru unele sisteme abstracte de mulțimi convexe, a unui rezultat (Scarf și altele) asupra numărului de inegalități necesare pentru a determina soluția unei probleme de programare cu numere întregi. Teorema despre acest sistem abstract pare a fi strâns legată de antimatroidii (cunoscute și sub numele de geometrii convexe), deși legătura nu a fost pe deplin explorată.

Lucrarea lui Hoffman asupra combinatoriei ne-a extins înțelegerea mai multor clase de grafice. O prelegere din 1956 a lui G. Hajos despre graficele de intervale a condus la caracterizarea graficelor de comparabilitate de către Hoffman și mai târziu, prin colaborarea cu Paul Gilmour, la teorema GH (atribuită și lui A. Guia-Ury). Inspirat de algoritmul de potrivire al lui Edmond, Hoffman a colaborat cu Ray Fulkerson și M. McAndrew Hoffman pentru a caracteriza seturi de numere întregi care ar putea potrivi puterile și limitele pentru fiecare pereche de vârfuri dintr-un astfel de grafic. În plus, ei au considerat care grafice din clasa tuturor graficelor având un set dat de grade și limite ale numărului de muchii pot fi transformate printr-un anumit set de schimburi în orice altă mulțime din clasă. Demonstrațiile sunt strâns legate de noțiunea importantă a bazei Hilbert. Un articol despre pătratele latine auto-ortogonale, scris în colaborare cu co-autori IBM Don Coppersmith și R. Brighton, a fost inspirat de o solicitare de a programa un soț pentru evitarea dublelor mixte pentru un club local de rachete. Are distincția de a fi singura lucrare despre care Hoffman a discutat în afara comunității matematice.

Seturile parțial ordonate au fost un subiect frecvent de studiu pentru Hoffman. O lucrare din 1977 cu D. E. Schwartz folosește dualitatea de programare liniară pentru a generaliza generalizarea lui Green și Kleitman din 1976 a teoremei de descompunere a lui Dilworth pentru posete, un alt exemplu al rolului unificator pe care dualitatea îl joacă în multe rezultate combinatorii.

De-a lungul carierei sale, Hoffman a căutat dovezi alternative simple și elegante ale teoremelor stabilite. Aceste dovezi alternative au condus adesea la generalizări și extensii. La sfârșitul anilor 1990, el a colaborat cu Cao, Chvatal și Vince pentru a dezvolta o demonstrație alternativă folosind metode elementare mai degrabă decât algebra liniară sau teorema matricei pătrate 0-1 a lui Reiser.

Lucrarea lui Hoffman privind inegalitățile matriceale și valorile proprii este fundamentul oricărui curs de teoria matricei. Un farmec deosebit, în conformitate cu pasiunea lui pentru abordări unificatoare, este lucrarea sa din 1975 despre funcțiile G liniare. Deși dovada acestei variații Gershgorin este mai lungă și mai complicată decât celelalte, ea acoperă toate variațiile Ostrovsky și multe variații suplimentare ca cazuri speciale.

Hoffman a fost un bătrân inspirator, dar nu a participat activ la dezvoltarea de către IBM a unui număr de produse pentru programare liniară și întregă. Cu toate acestea, el a continuat să exploreze aspectele combinatorii și algebrice ale programării liniare și ale inegalităților liniare, inclusiv o abstractizare încântătoare a dualității programării liniare (1963). De asemenea, a continuat să folosească proprietățile inegalităților liniare pentru a dovedi (sau, mai elegant, a demonstra) rezultatele convexității.

În colaborare cu Shmuel Winograd, de asemenea, un coleg IBM în departamentul de matematică, a fost dezvoltat un algoritm eficient pentru a găsi toate distanțele cele mai scurte într-o rețea direcționată folosind pseudomultiplicarea matriceală. O serie de lucrări despre poliedre latice (unele cu Don Schwarts) au introdus noțiunea de poliedre latice, conducând la încă un exemplu de dualitate combinatorie.

După colaborarea cu Ray Fulkerson și Rosa Oppenheim pe matrice echilibrată, Hoffman a generalizat rezultatul Ford-Fulkerson-debit maxim-minim tăiat la alte cazuri (debit la noduri, arce nedirecționate etc.), oferind dovada că toate cazurile cunoscute anterior erau Speciale. cazuri. Acest articol a introdus, de asemenea, conceptul (dar din nou, nu numele) de întreg dual complet, ideea din spatele majorității aplicațiilor de programare liniară pentru a demonstra teoreme combinatorii extreme.

De-a lungul carierei sale, Hoffman a studiat o clasă de probleme de programare cu numere întregi care puteau fi rezolvate prin maximizarea succesivă a variabilelor într-o anumită ordine. Un astfel de exemplu este problema completă a transportului când factorul cost prezintă o proprietate specială descoperită cu mai bine de un secol în urmă de matematicianul francez Gaspard Monge. Această abordare, numită pur și simplu „simplu” în lucrarea lui Hoffman, a fost mai târziu considerată „lacomă” de către Edmonds și Fulkerson. Proprietatea Monge generează un antimatroid, iar datorită utilizării acestui antimatroid, rezultatul lui Hoffman poate fi extins cu ușurință în cazul problemelor de transport incomplete. Hoffman a refolosit termenul „lacom” pentru a descrie o subclasă de matrice 0-1 pentru care programul liniar dual poate fi rezolvat printr-un algoritm lacom pentru toate părțile din dreapta și toate funcțiile obiective cu coeficienți descrescători (prin indice variabil). . Împreună cu Kolen și Sakarovich, el a arătat că pentru aceste matrice programul corespunzător de numere întregi are o soluție optimă pentru datele întregi. O lucrare elegantă și concisă din 1992 caracterizează matrice 0-1 pentru care problemele de ambalare și acoperire pot fi rezolvate printr-o abordare lacomă. Oferă unificarea rezultatelor pentru cea mai scurtă cale și probleme de arbore de întindere minim. Lucrarea sa finală pe acest subiect, „Despre algoritmii lacomi, seturile parțial ordonate și funcțiile submodulare”, în colaborare cu Dietrich, a apărut în 2003.

Hoffman, împreună cu Robert Singleton, a construit graficul Hoffman-Singleton [5] , care este un grafic Moore unic de grad 7 și diametru 2 [3] . În 1963, el a construit Graficul Hoffman , care, deși cospectral cu graficul hipercubului cu patru dimensiuni Q 4 [6] , dar a cărui rază este egală cu 3 (există astfel de vârfuri, cea mai scurtă cale către orice alt vârf ). al graficului este format din cel mult trei muchii), în timp ce raza graficului hipercub Q 4 este egală cu 4 [7] .

Premii și recunoaștere

Hoffman a fost ales la Academia Națională de Științe în 1982 [1] , la Academia Americană de Arte și Științe în 1987 [1] și primul membru al Institutului pentru Cercetare Operațională și Științe de Management (INFORMS) în 2002 [8] . În 1992, împreună cu Philip Wolf (tot de la IBM), a primit premiul teoretic John von Neumann [1] . Doctor onorific în știință de la Technion (Institutul de Tehnologie din Israel) din 1986.

Pe parcursul lungii sale cariere, Hoffman a făcut parte din personalul editorial al unsprezece reviste și a fost redactor și fondator al revistei engleze.  Algebra liniară și aplicațiile ei [1] . Într-o biografie publicată în numărul cu aniversarea a 65 de ani a lui Hoffman, Uriel Rothblum a scris că „Pe lângă realizările sale științifice și profesionale, Hoffman are o capacitate de neegalat de a se bucura de tot ceea ce face. Îi place să cânte, să joace ping-pong, jocuri de cuvinte, povești pline de spirit și, poate mai mult decât orice altceva, să facă matematică .

Publicații selectate

O listă completă a publicațiilor este dată pe pagina personală [1] .

Note

  1. ↑ 1 2 3 4 5 6 Pagina personală, IBM. Alan Hoffman  . Cercetare IBM. Consultat la 14 noiembrie 2011. Arhivat din original la 14 martie 2012.
  2. ↑ 1 2 3 4 5 6 7 Biografia lui Alan J. Hoffman
  3. ↑ 12 A.E. _ Brouwer și JH van Lint. Grafice puternic regulate și geometrii parțiale // Enumerare și proiectare  (engleză) / DH Jackson, & SA Vanstone (eds.). – Academic Press Inc. - P. 85-122.
  4. ↑ Hoffman, AJ (Alan Jerome), 1924-. Lucrări alese ale lui Alan Hoffman cu comentarii . - River Edge, NJ: World Scientific, 2003. - ISBN 978-981-279-693-6 .
  5. ↑ Hoffman, AJ, Singleton, R. R. Grafice Moore cu diametrul 2 și 3, 1960 .
  6. ↑ Hoffman, A.J. Despre polinomul unui grafic, 1963 .
  7. ↑ Weisstein, Eric W. Hoffman grafic  pe site- ul Wolfram MathWorld .
  8. ↑ Fellows:  Lista alfabetică . Institutul pentru Cercetare Operațională și Științe de Management. Preluat: 9 octombrie 2019.
  Accesați articolul Wikidata  Site-uri tematice