Hoffman, Alan

Alan Jerome Hoffman ( Eng.  Alan Jerome Hoffman ; 30. května 1924, New York  – 18. ledna 2021 [2] ) byl americký matematik, který pracoval v IBM T. J. Watson Research Center . Redaktor a zakladatel časopisu Lineární algebra a její aplikace . Přispěl ke kombinatorické optimalizaci a teorii vlastních hodnot grafů. Hoffman spolu s Robertem Singletonem zkonstruoval Hoffman-Singletonův graf , což je jedinečný Moorův graf stupně 7 a průměru 2 [3] .  

Životopis

Alan Hoffman vstoupil na Kolumbijskou univerzitu v roce 1940 a získal Pulitzerovo stipendium v ​​roce 1940 ve věku 16 let. Druhá světová válka přerušila Hoffmanova studia, v únoru 1943 byl povolán do služby a v letech 1943 až 1946 sloužil v americké armádě, a to jak v Evropě, tak v Tichomoří. Při základním výcviku na protiletadlové dělostřelecké škole zvažoval možnost rozvoje axiomů geometrie kružnic [2] .

Po svém návratu do Kolumbie na podzim roku 1946 dokončil v roce 1950 doktorskou disertační práci o základech inverzní geometrie. Poté Hoffman strávil rok v Institutu pro pokročilé studium v ​​Princetonu (kancelář vedle něj byla obsazena Albertem Einsteinem ) [2] .

Raná kariéra

Hoffmanovo první zaměstnání bylo v divizi aplikované matematiky Národního úřadu pro standardy . V předsednictvu se Hoffman stal lídrem v novém oboru vědy, lineárním programování . Hoffman byl klíčovým organizátorem vlivného Second Linear Programming Symposium konaného na předsednictvu v lednu 1955 [2] .

V roce 1956 Hoffman opustil Bureau a přestěhoval se do Anglie, aby pracoval jako komunikační výzkumník v londýnské pobočce Bureau of Naval Research. Jak se rok chýlil ke konci v zahraničí, Hoffmanovi byly nabídnuty dvě pozice u průmyslových společností v New Yorku: jedna v malé matematické výzkumné skupině v rodící se IBM Research Laboratory a druhá v ústředí General Electric Company . Hoffman si vybral roli v zavedenější organizaci. Vedení mu umožnilo studovat matematiku, pokud to nenarušilo plnění povinností, které mu byly přiděleny, a Hoffman pokračoval ve svém matematickém výzkumu, zcela nesouvisejícím s jeho hlavním zaměstnáním. V roce 1961 přijal pozvání do výzkumného centra T. J. Watsona společnosti IBM 2] .

Kariéra u IBM

Během své kariéry v IBM Hoffman publikoval více než 200 vědeckých prací, více než třetina z nich je spoluautorem. Jeho matematický rozsah pokrýval mnoho oblastí matematiky, od algebry po operační výzkum [2] .

Shrnutí matematických příspěvků (z jeho poznámek v Selected Papers of Alana Hoffmana) [4] .

Hoffmannova práce o geometrii, počínaje jeho tezí „O základech inverzní geometrie“, zahrnovala důkazy vlastností afinních rovin, stejně jako studium relačních bodů konečných projektivních rovin, podmínek pravidelnosti sjednocení a průniku kuželů ( odvozeno z velké části z jeho zobecnění jeho dřívějších výsledků o hodnosti skutečných matic). Předložil alternativní důkaz, založený na axiomech pro některé abstraktní systémy konvexních množin, výsledku (Scarf a další) o počtu nerovností potřebných k určení řešení problému celočíselného programování. Zdá se, že teorém o tomto abstraktním systému úzce souvisí s antimatroidy (také známými jako konvexní geometrie), ačkoli toto spojení nebylo plně prozkoumáno.

Hoffmanova práce na kombinatorice rozšířila naše chápání několika tříd grafů. Přednáška G. Hajose o intervalových grafech z roku 1956 vedla k Hoffmanově charakterizaci grafů srovnatelnosti a později, díky spolupráci s Paulem Gilmourem, k GH teorému (také připisovanému A. Guia-Urymu). Inspirován Edmondovým párovacím algoritmem, Hoffman spolupracoval s Rayem Fulkersonem a M. McAndrewem Hoffmanem na charakterizaci množin celých čísel, které by mohly odpovídat mocninám a mezím pro každou dvojici vrcholů v takovém grafu. Kromě toho zvažovali, které grafy ve třídě všech grafů s danou množinou stupňů a hranic počtu hran lze určitou množinou výměn transformovat na jakoukoli jinou množinu ve třídě. Důkazy úzce souvisí s důležitým pojmem Hilbertova základu. Článek o samo-ortogonálních latinských čtvercích, napsaný spolu se spoluautory IBM Donem Coppersmithem a R. Brightonem, byl inspirován požadavkem naplánovat manžela pro vyhýbání se smíšené čtyřhře pro místní raketový klub. Má tu výhodu, že je jediným dokumentem, o kterém Hoffman diskutoval mimo matematickou komunitu.

Částečně uspořádané množiny byly pro Hoffmana častým tématem studia. Článek s D. E. Schwartzem z roku 1977 používá dualitu lineárního programování ke zobecnění Greena a Kleitmana z roku 1976 zobecnění Dilworthovy věty o rozkladu pro posety, což je další příklad sjednocující role, kterou dualita hraje v mnoha kombinatorických výsledcích.

Během své kariéry Hoffman hledal jednoduché a elegantní alternativní důkazy zavedených teorémů. Tyto alternativní důkazy často vedly ke zobecnění a rozšíření. Na konci 90. let spolupracoval s Cao, Chvatalem a Vincem na vývoji alternativního důkazu využívajícího spíše elementární metody než lineární algebru nebo Reiserovu větu o čtvercové matici 0-1.

Hoffmanova práce o maticových nerovnostech a vlastních číslech je základem každého kurzu teorie matic. Zvláštní kouzlo, v souladu s jeho zálibou ve sjednocujících přístupech, je jeho článek z roku 1975 o lineárních G-funkcích. Ačkoli je důkaz této Gershgorinovy ​​variace delší a komplikovanější než ostatní, pokrývá všechny Ostrovského variace a mnoho dalších variací jako speciální případy.

Hoffman byl inspirativním starším, ale aktivně se nepodílel na vývoji řady produktů IBM pro lineární a celočíselné programování. Pokračoval však ve zkoumání kombinatorických a algebraických aspektů lineárního programování a lineárních nerovností, včetně nádherné abstrakce duality lineárního programování (1963). Pokračoval také v používání vlastností lineárních nerovností k prokázání (nebo elegantněji opětovnému prokázání) výsledků konvexnosti.

Ve spolupráci se Shmuelem Winogradem, rovněž spolupracovníkem IBM na katedře matematiky, byl vyvinut účinný algoritmus pro nalezení všech nejkratších vzdáleností v řízené síti pomocí pseudonásobení matic. Série článků o mřížových mnohostěnech (některé s Donem Schwartsem) představila pojem mřížových mnohostěnů, což vedlo k dalšímu příkladu kombinatorické duality.

Po spolupráci s Rayem Fulkersonem a Rosou Oppenheimovou na vyvážených maticích Hoffman zobecnil výsledek Ford-Fulkerson maximální-průtok-minimum-cut na další případy (tok v uzlech, neřízené oblouky atd.), čímž poskytl důkaz, že všechny dříve známé případy byly speciální. případy. Tento článek také představil koncept (ale opět ne název) úplného duálního celého čísla, což je myšlenka, která stojí za většinou aplikací lineárního programování k prokázání extremálních kombinatorických teorémů.

Během své kariéry Hoffman studoval třídu problémů celočíselného programování, které by bylo možné vyřešit postupnou maximalizací proměnných v určitém pořadí. Jedním takovým příkladem je úplný dopravní problém, kdy nákladový faktor vykazuje zvláštní vlastnost, kterou objevil před více než stoletím francouzský matematik Gaspard Monge. Tento přístup, nazvaný jednoduše „jednoduchý“ v Hoffmanově článku, byl později Edmondsem a Fulkersonem považován za „chamtivý“. Mongeova vlastnost generuje antimatroid a díky použití tohoto antimatroidu lze Hoffmanův výsledek snadno rozšířit i na případ neúplných dopravních problémů. Hoffman znovu použil termín "chamtivý" k popisu podtřídy matic 0-1, pro kterou lze duální lineární program vyřešit pomocí hltavého algoritmu pro všechny pravé strany a všechny objektivní funkce s klesajícími (proměnnými indexy) koeficienty. . Spolu s Kolenem a Sakarovičem ukázal, že pro tyto matice má odpovídající celočíselný program celočíselné optimální řešení pro celočíselná data. Elegantní a výstižný článek z roku 1992 charakterizuje matice 0-1, u kterých lze problémy s balením a překrýváním řešit pomocí zištného přístupu. Poskytuje sjednocení výsledků pro nejkratší cestu a minimální problémy s kostrou. Jeho závěrečná práce na toto téma „O chamtivých algoritmech, částečně uspořádaných množinách a submodulárních funkcích“, kterou napsal spolu s Dietrichem, se objevila v roce 2003.

Hoffman společně s Robertem Singletonem zkonstruoval Hoffman-Singletonův graf [5] , což je unikátní Moorův graf stupně 7 a průměru 2 [3] . V roce 1963 sestrojil Hoffmanův graf , který je sice kospektrální ke grafu čtyřrozměrné hyperkrychle Q 4 [6] , ale jehož poloměr je roven 3 (existují takové vrcholy, jejichž nejkratší cesta k jakémukoli jinému vrcholu grafu sestává maximálně ze tří hran), přičemž poloměr grafu hyperkrychle Q 4 je roven 4 [7] .

Ocenění a uznání

Hoffman byl zvolen do Národní akademie věd v roce 1982 [1] , do Americké akademie umění a věd v roce 1987 [1] a do prvního členství v Institute for Operations Research and Management Sciences (INFORMS) v roce 2002 [8] . V roce 1992 mu byla spolu s Philipem Wolfem (také z IBM) udělena teoretická cena Johna von Neumanna [1] . Čestný doktor věd z Technion (Izraelský technologický institut) od roku 1986.

Během své dlouhé kariéry působil Hoffman v redakcích jedenácti časopisů a byl redaktorem a zakladatelem anglického časopisu.  Lineární algebra a její aplikace [1] . V biografii publikované v Hoffmanově vydání k 65. narozeninám Uriel Rothblum napsal, že „Kromě svých vědeckých a profesionálních úspěchů má Hoffman jedinečnou schopnost užívat si všechno, co dělá. Rád zpívá, hraje ping-pong, slovní hříčky, vtipné příběhy a možná víc než cokoli jiného počítá .

Vybrané publikace

• Hoffman AJ, Jacobs W. Hladké vzory výroby  //  Management Science. - 1954. - Sv. 1 , iss. 1 . — S. 86–91 .
• Hoffman, AJ, Singleton, RR Mooreovy grafy s průměrem 2 a 3 // IBM Journal of Research and Development. - 1960. - V. 5 , čís. 4 . — S. 497–504 . - doi : 10.1147/rd.45.0497 .
• Hoffman AJ O polynomu grafu   // Amer . Matematika. Měsíční. - 1963. - Sv. 70 . - str. 30-36 .
• Hoffman AJ, Wolfe P. Historie problému Traveling Salesman // The Traveling Salesman Problem  (Angl.) / Lawler EL, Lenstra JK, Rinnooy Kan AHG, & Shmoys DB, eds. — John Wiley, 1985.

Kompletní seznam publikací je uveden na osobní stránce [1] .

Poznámky

1. ↑ 1 2 3 4 5 6 Osobní stránka, IBM. Alan Hoffman  . Výzkum IBM. Získáno 14. listopadu 2011. Archivováno z originálu dne 14. března 2012.
2. ↑ 1 2 3 4 5 6 7 Životopis Alana J. Hoffmana
3. ↑ 12 A.E. _ Brouwer & JH van Lint. Silně pravidelné grafy a částečné geometrie // Enumeration and Design  (anglicky) / DH Jackson, & SA Vanstone (Eds.). – Academic Press Inc. - S. 85-122.
4. ↑ Hoffman, AJ (Alan Jerome), 1924-. Vybrané články Alana Hoffmana s komentářem . - River Edge, NJ: World Scientific, 2003. - ISBN 978-981-279-693-6 .
5. ↑ Hoffman, AJ, Singleton, R. R. Mooreovy grafy s průměrem 2 a 3, 1960 .
6. ↑ Hoffman, A. J. On the Polynomial of a Graph, 1963 .
7. ↑ Weisstein, Eric W. Hoffman graf  na webu Wolfram MathWorld .
8. ↑ Členové: Abecední  seznam . Ústav pro operační výzkum a management věd. Staženo: 9. října 2019.

Tematické stránky	Matematická genealogie zbMATH Otevřeno
V bibliografických katalozích GND : 1103166549 ISNI : 0000 0001 1463 2648 J9U : 987007431043105171 LCCN : n78042498 NLG : 221689 NTA : 07088692X NUKAT : n2006011297 SUDOC : 164195823 VIAF : 110277368 WorldCat VIAF : 110277368