Hoffman, Alan

Alan Hoffman
angol  Alan Jerome Hoffman

Hoffman-Singleton gráf , 50 csúcs, 175 él
Születési dátum 1924. május 30( 1924-05-30 )
Születési hely New York [1]
Halál dátuma 2021. január 18. (96 éves)( 2021-01-18 )
Ország  USA
Tudományos szféra kombinatorikus optimalizálás , gráfelmélet
Munkavégzés helye T. J. Watson
alma Mater
Akadémiai fokozat Ph.D
tudományos tanácsadója Edgar Lorch [d]
Ismert, mint Count Hoffman-Singleton társszerzője
Díjak és díjak Neumann Elméleti Díj ( 1992 )

Alan Jerome Hoffman ( ang.  Alan Jerome Hoffman ; 1924. május 30., New York  – 2021. január 18. [2] ) amerikai matematikus , az IBM T. J. Watson Kutatóközpontban dolgozott . A folyóirat szerkesztője és alapítója Lineáris algebra és alkalmazásai . Hozzájárult a gráfok kombinatorikus optimalizálásához és sajátérték-elméletéhez. Hoffman Robert Singletonnal együtt megalkotta a Hoffman-Singleton gráfot , amely egy egyedülálló 7- es fokozatú és 2 - es átmérőjű Moore-gráf [3] .  

Életrajz

Alan Hoffman 1940-ben lépett be a Columbia Egyetemre , és 16 évesen Pulitzer-ösztöndíjat kapott 1940-ben. A második világháború megszakította Hoffman tanulmányait, 1943 februárjában behívták szolgálatra, és 1943-tól 1946-ig az amerikai hadseregben szolgált Európában és a Csendes-óceánon egyaránt. A légelhárító tüzériskola alapkiképzése során fontolóra vette a körök geometriájának axiómáinak kidolgozásának lehetőségét [2] .

Miután 1946 őszén visszatért Columbiába, 1950-ben fejezte be doktori disszertációját az inverziós geometria alapjairól. Ezt követően Hoffman egy évet a Princetoni Institute for Advanced Study -ban töltött (a mellette lévő irodát Albert Einstein foglalta el ) [2] .

Korai karrier

Hoffman első munkahelye a Nemzeti Szabványügyi Hivatal Alkalmazott Matematikai Osztálya volt . Az Irodánál Hoffman egy új tudományterület, a lineáris programozás vezetőjévé vált . Hoffman kulcsfontosságú szervezője volt az 1955 januárjában az Irodában megtartott, befolyásos Második Lineáris Programozási Szimpóziumnak [2] .

1956-ban Hoffman otthagyta az Irodát, és Angliába költözött, hogy kommunikációs kutatóként dolgozzon a Bureau of Naval Research londoni részlegénél. Ahogy közeledett az év külföldön, Hoffmannak két pozíciót ajánlottak fel New York-i ipari vállalatoknál: az egyiket a születőben lévő IBM Research Laboratory apró matematikai kutatócsoportjában , a másikat pedig a General Electric Company központjában . Hoffman egy megalapozottabb szervezetben választott szerepet. A vezetőség engedélyezte számára, hogy matematikát tanuljon, ha ez nem zavarja a rábízott feladatok ellátását, Hoffman pedig folytatta matematikai kutatásait, teljesen független a főállásától. 1961-ben elfogadta a felkérést, hogy csatlakozzon az IBM T. J. Watson Kutatóközpontjához 2] .

Karrier az IBM-nél

Az IBM-nél végzett pályafutása során Hoffman több mint 200 tudományos közleményt publikált, ezek több mint egyharmada társszerzője volt. Matematikai tartománya a matematika számos területére kiterjedt, az algebrától a műveletek kutatásáig [2] .

Matematikai hozzájárulások összefoglalása (a Selected Papers of Alan Hoffman című könyvében írt jegyzeteiből) [4] .

Hoffmann geometriai munkája, az inverziós geometria alapjairól szóló tézisétől kezdve, magában foglalta az affin síkok tulajdonságainak bizonyítását, valamint a véges projektív síkok kapcsolati pontjainak, a kúpok egyesülésének szabályszerűségeinek és metszéspontjainak tanulmányozását ( nagyrészt a valós mátrixok rangjára vonatkozó korábbi eredményeinek általánosításából származik). Néhány absztrakt konvex halmazrendszerre vonatkozó axiómákon alapuló alternatív bizonyítást mutatott be (Scarf és mások) egy egészszámú programozási probléma megoldásához szükséges egyenlőtlenségek számáról. Úgy tűnik, hogy az erről az absztrakt rendszerről szóló tétel szorosan kapcsolódik az antimatroidokhoz (más néven konvex geometriákhoz), bár az összefüggést még nem tárták fel teljesen.

Hoffman kombinatorika munkája kibővítette a gráfok több osztályának megértését. G. Hajos 1956-os előadása az intervallumgráfokról vezetett Hoffmannak az összehasonlíthatósági gráfok jellemzéséhez, majd később – Paul Gilmourral együttműködve – a GH-tételhez (amely szintén A. Guia-Ury-nak tulajdonítható). Az Edmond-féle illesztési algoritmus által ihletett Hoffman együttműködött Ray Fulkersonnal és M. McAndrew Hoffmannal, hogy olyan egész számokat jellemezzenek, amelyek megfeleltethetnék egy ilyen gráf minden csúcspárjának hatványait és határait. Ezen túlmenően azt is megvizsgálták, hogy az összes gráf osztályában mely gráfok, amelyek adott fokszámkészlettel és az élek számának határaival rendelkeznek, transzformálhatók egy bizonyos cserehalmazsal az osztály bármely más halmazává. A bizonyítások szorosan kapcsolódnak a Hilbert-alap fontos fogalmához. Az önortogonális latin négyzetekről szóló cikket, amelyet az IBM társszerzőivel, Don Coppersmith-tel és R. Brightonnal közösen írt, az a kérés ihlette, hogy egy vegyes párosokat elkerülő házastársat nevezzenek be egy helyi ütőklubba. Ez az egyetlen olyan dokumentum, amelyet Hoffman a matematikai közösségen kívül tárgyalt.

A részben megrendelt készletek gyakori témája volt Hoffmannak. Egy 1977-ben D. E. Schwartz-cal írt tanulmány a lineáris programozási kettősséget használja Green és Kleitman 1976-os Dilworth-féle dekompozíciós tételének általánosítására pózokra, ami egy másik példa a dualitás egyesítő szerepére számos kombinatorikus eredményben.

Pályafutása során Hoffman egyszerű és elegáns alternatív bizonyításokat keresett a megalapozott tételekre. Ezek az alternatív bizonyítások gyakran vezettek általánosításokhoz és kiterjesztésekhez. Az 1990-es évek végén Cao-val, Chvatallal és Vince-szel együttműködve egy alternatív bizonyítást dolgozott ki elemi módszerekkel, nem pedig lineáris algebra vagy Reiser 0-1 négyzetmátrix tétele alapján.

Hoffman mátrixegyenlőtlenségekkel és sajátértékekkel foglalkozó munkája a mátrixelmélet bármely kurzusának alapja. Az egységesítő megközelítések iránti rajongásával összhangban különösen varázslatos az 1975-ös tanulmánya a lineáris G-függvényekről. Noha ennek a Gershgorin-variációnak a bizonyítása hosszabb és bonyolultabb, mint a többi, az összes Osztrovszkij-variációt és sok további variációt speciális esetként lefedi.

Hoffman inspiráló vén volt, de nem vett részt aktívan az IBM számos lineáris és egész programozási termékének fejlesztésében. Mindazonáltal folytatta a lineáris programozás és a lineáris egyenlőtlenségek kombinatorikus és algebrai vonatkozásainak feltárását, beleértve a lineáris programozás kettősségének elragadó absztrakcióját (1963). Továbbra is a lineáris egyenlőtlenségek tulajdonságait használta a konvexitási eredmények bizonyítására (vagy elegánsabban újrabizonyítására).

Shmuel Winograddal, aki szintén az IBM munkatársa a matematika részlegen, együttműködve egy hatékony algoritmust fejlesztettek ki az irányított hálózat összes legrövidebb távolságának megtalálására mátrix pszeudomaplikáció segítségével. A rácspoliéderekről szóló cikkek sorozata (néhányszor Don Schwartssal) bevezette a rácspoliéder fogalmát, ami a kombinatorikus kettősség újabb példájához vezetett.

Miután együttműködött Ray Fulkersonnal és Rosa Oppenheimmal a kiegyensúlyozott mátrixokon, Hoffman általánosította a Ford-Fulkerson maximális áramlási minimum vágás eredményét más esetekre (áramlás a csomópontokban, irányítatlan ívek stb.), bizonyítva, hogy az összes korábban ismert eset speciális volt. esetek. Ez a cikk bemutatta a teljes kettős egész szám fogalmát (de nem a nevét), a lineáris programozás extremális kombinatorikus tételek bizonyítására szolgáló legtöbb alkalmazása mögött meghúzódó gondolatot.

Pályafutása során Hoffman egész számok programozási problémáit tanulmányozta, amelyek megoldhatók a változók egymás utáni, bizonyos sorrendben történő maximalizálásával. Ilyen például a teljes szállítási probléma, amikor a költségtényező egy különleges tulajdonságot mutat, amelyet több mint egy évszázaddal ezelőtt fedezett fel Gaspard Monge francia matematikus. Ezt a megközelítést, amelyet Hoffman írása egyszerűen "egyszerűnek" nevez, később Edmonds és Fulkerson "kapzsinak" tartotta. A Monge tulajdonság egy antimatroidot generál, és ennek az antimatroidnak köszönhetően a Hoffman-eredmény könnyen kiterjeszthető a nem teljes szállítási problémák esetére is. Hoffman újra felhasználta a "mohó" kifejezést egy 0-1 mátrixokból álló alosztály leírására, amelyre a duális lineáris program egy mohó algoritmussal megoldható minden jobb oldalra és minden célfüggvényre, csökkenő (változó indexű) együtthatókkal. . Kolennel és Sakarovich-csal együtt megmutatta, hogy ezekre a mátrixokra a megfelelő egész programnak van egészszámú optimális megoldása egész számokra. Egy 1992-ből származó elegáns és tömör papír 0-1 mátrixokat jellemez, amelyeknél a csomagolási és borítási problémák mohó megközelítéssel megoldhatók. Egyesíti az eredményeket a legrövidebb út és a minimális átívelő fa problémákhoz. Utolsó tanulmánya a témában, "A mohó algoritmusokról, részben rendezett halmazokról és szubmoduláris függvényekről", amelyet Dietrich-hel közösen írt, 2003-ban jelent meg.

Hoffman Robert Singletonnal együtt megalkotta a Hoffman-Singleton gráfot [5] , amely egy egyedi 7- es fokozatú és 2 - es átmérőjű Moore-gráf [3] . 1963-ban megszerkesztette a Hoffman -gráfot , amely ugyan kospektrális a Q 4 négydimenziós hiperkocka gráfjához [6] , de sugara egyenlő 3-mal (vannak olyan csúcsok, amelyeknek a legrövidebb útja bármely más csúcshoz a gráf legfeljebb három élből áll), míg a Q 4 hiperkocka gráf sugara 4 [7] .

Díjak és elismerések

Hoffmant 1982- ben választották a Nemzeti Tudományos Akadémiához [1] , 1987-ben az Amerikai Művészeti és Tudományos Akadémiához [1] és 2002-ben az Institute for Operations Research and Management Sciences (INFORMS) első tagjává. [8] . 1992-ben Philip Wolfdal (szintén az IBM-től) együtt megkapta a Neumann János Elméleti Díjat [1] . 1986 óta a tudomány tiszteletbeli doktora a Technion -tól (Israel Institute of Technology).

Hoffman hosszú pályafutása során tizenegy folyóirat szerkesztőségében dolgozott, az angol folyóirat szerkesztője és alapítója volt.  A lineáris algebra és alkalmazásai [1] . A Hoffman 65. születésnapi számában megjelent életrajzában Uriel Rothblum azt írta, hogy „Tudományos és szakmai eredményein kívül Hoffman páratlan képességgel rendelkezik, hogy élvezze mindazt, amit csinál. Szeret énekelni, pingpongozni, szójátékokat, szellemes történeteket, és talán mindennél jobban szeret matekozni .

Válogatott kiadványok

A publikációk teljes listája a személyes oldalon található [1] .

Jegyzetek

  1. 1 2 3 4 5 6 Személyes oldal, IBM. Alan Hoffman  . IBM kutatás. Letöltve: 2011. november 14. Az eredetiből archiválva : 2012. március 14..
  2. 1 2 3 4 5 6 7 Alan J. Hoffman életrajza
  3. e . 12. _ Brouwer és JH van Lint. Erősen szabályos gráfok és részleges geometriák // Felsorolás és tervezés  (angol) / DH Jackson, & SA Vanstone (szerk.). – Academic Press Inc. - P. 85-122.
  4. Hoffman, AJ (Alan Jerome), 1924-. Alan Hoffman válogatott dolgozatai kommentárral . - River Edge, NJ: World Scientific, 2003. - ISBN 978-981-279-693-6 .
  5. Hoffman, AJ, Singleton, R. R. Moore-gráfok 2-es és 3-as átmérővel, 1960 .
  6. Hoffman, A.J. On the Polynomial of a Graph, 1963 .
  7. Weisstein, Eric W. Hoffman grafikonja  a Wolfram MathWorld weboldalán .
  8. Fellows: Alfabetikus  lista . Operációkutató és Vezetéstudományi Intézet. Letöltve: 2019. október 9.