Hoffman, Alan

Alan Jerome Hoffman ( eng.  Alan Jerome Hoffman ; 30 maj 1924, New York  - 18 januari 2021 [2] ) var en amerikansk matematiker som arbetade vid IBM T. J. Watson Research Center . Redaktör och grundare av tidningen Linjär algebra och dess tillämpningar . Han bidrog till kombinatorisk optimering och egenvärdesteori för grafer. Hoffman, tillsammans med Robert Singleton, konstruerade Hoffman-Singleton-grafen , som är en unik Moore-graf av grad 7 och diameter 2 [3] .  

Biografi

Alan Hoffman började på Columbia University 1940 och fick ett Pulitzer-stipendium 1940 vid 16 års ålder. Andra världskriget avbröt Hoffmans studier, han kallades till tjänst i februari 1943 och tjänstgjorde i den amerikanska armén från 1943 till 1946, både i Europa och Stilla havet. Under grundutbildningen på luftvärnsartilleriskolan övervägde han möjligheten att utveckla axiomen för cirklarnas geometri [2] .

När han återvände till Columbia hösten 1946, avslutade han sin doktorsavhandling om grunderna för inversionsgeometri 1950. Efter det tillbringade Hoffman ett år på Institutet för avancerade studier i Princeton (kontoret bredvid honom ockuperades av Albert Einstein ) [2] .

Tidig karriär

Hoffmans första jobb var i Applied Mathematics Division av National Bureau of Standards . På presidiet blev Hoffman en ledare inom ett nytt vetenskapsområde, linjär programmering . Hoffman var en nyckelorganisatör av det inflytelserika Second Linear Programming Symposium som hölls vid presidiet i januari 1955 [2] .

1956 lämnade Hoffman byrån och flyttade till England för att arbeta som kommunikationsforskare vid London-avdelningen av Bureau of Naval Research. När året närmade sig sitt slut utomlands erbjöds Hoffman två tjänster hos industriföretag i New York City: en i en liten matematisk forskargrupp vid det begynnande IBM Research Laboratory , och den andra vid huvudkontoret för General Electric Company . Hoffman valde en roll i en mer etablerad organisation. Ledningen tillät honom att studera matematik, om detta inte störde utförandet av de uppgifter som tilldelats honom, och Hoffman fortsatte sin matematiska forskning, helt utan samband med hans huvudsakliga jobb. 1961 accepterade han en inbjudan att gå med i IBM:s T. J. Watson Research Center 2] .

Karriär på IBM

Under sin karriär på IBM publicerade Hoffman mer än 200 vetenskapliga artiklar, mer än en tredjedel av dem var medförfattare. Hans matematiska räckvidd täckte många områden inom matematiken, från algebra till operationsforskning [2] .

Sammanfattning av matematiska bidrag (från hans anteckningar i Selected Papers of Alan Hoffman) [4] .

Hoffmanns arbete om geometri, som började med hans avhandling "On the Foundations of Inversion Geometry", inkluderade bevis på egenskaperna hos affina plan, såväl som studiet av relationspunkter för ändliga projektiva plan, villkor för regelbundenhet i förening och korsning av koner ( till stor del härledd från hans generalisering av hans tidigare resultat på rangordningen av verkliga matriser). Han presenterade ett alternativt bevis, baserat på axiom för vissa abstrakta system av konvexa uppsättningar, på ett resultat (Scarf och andra) på antalet ojämlikheter som behövs för att bestämma lösningen på ett heltalsprogrammeringsproblem. Teoremet om detta abstrakta system verkar vara nära relaterat till antimatroider (även känd som konvexa geometrier), även om sambandet inte har utforskats helt.

Hoffmans arbete med kombinatorik har utökat vår förståelse av flera klasser av grafer. En föreläsning 1956 av G. Hajos om intervallgrafer ledde till Hoffmans karaktärisering av jämförbarhetsgrafer och senare, genom samarbete med Paul Gilmour, till GH-satsen (även tillskriven A. Guia-Ury). Inspirerad av Edmonds matchningsalgoritm, samarbetade Hoffman med Ray Fulkerson och M. McAndrew Hoffman för att karakterisera uppsättningar av heltal som kunde matcha potenserna och gränserna för varje par av hörn i en sådan graf. Dessutom övervägde de vilka grafer i klassen av alla grafer som har en given uppsättning grader och gränser på antalet kanter som kan omvandlas av en viss uppsättning utbyten till någon annan uppsättning i klassen. Bevisen är nära besläktade med den viktiga föreställningen om Hilbertbasen. En artikel om självortogonala latinska rutor, skriven tillsammans med IBMs medförfattare Don Coppersmith och R. Brighton, inspirerades av en förfrågan om att schemalägga en blandad dubbel-undvikande make till en lokal racketklubb. Det har skillnaden att vara det enda papper som Hoffman har diskuterat utanför den matematiska gemenskapen.

Delvis beställda uppsättningar har varit ett frekvent studieämne för Hoffman. En artikel från 1977 med D. E. Schwartz använder linjär programmeringsdualitet för att generalisera Green och Kleitmans generalisering från 1976 av Dilworths nedbrytningsteorem för poseter, ett annat exempel på den förenande roll som dualitet spelar i många kombinatoriska resultat.

Hoffman har under hela sin karriär sökt efter enkla och eleganta alternativa bevis på etablerade teorem. Dessa alternativa bevis ledde ofta till generaliseringar och förlängningar. I slutet av 1990-talet samarbetade han med Cao, Chvatal och Vince för att utveckla ett alternativt bevis med hjälp av elementära metoder snarare än linjär algebra eller Reisers 0-1 kvadratmatrissats.

Hoffmans arbete med matrisojämlikheter och egenvärden är grunden för varje kurs i matristeori. Av särskild charm, i linje med hans förkärlek för förenande tillvägagångssätt, är hans artikel från 1975 om linjära G-funktioner. Även om beviset för denna Gershgorin-variation är längre och mer komplicerat än de andra, täcker det alla Ostrovsky-variationer och många ytterligare variationer som specialfall.

Hoffman var en inspirerande äldste, men deltog inte aktivt i IBM:s utveckling av ett antal produkter för linjär- och heltalsprogrammering. Men han fortsatte att utforska de kombinatoriska och algebraiska aspekterna av linjär programmering och linjära ojämlikheter, inklusive en förtjusande abstraktion av dualiteten av linjär programmering (1963). Han fortsatte också att använda egenskaperna hos linjära ojämlikheter för att bevisa (eller mer elegant återbevisa) konvexitetsresultat.

I samarbete med Shmuel Winograd, också en IBM-stipendiat på matematikavdelningen, utvecklades en effektiv algoritm för att hitta alla kortaste avstånd i ett riktat nätverk med hjälp av matrispseudomultiplikation. En serie artiklar om gitterpolyedrar (vissa med Don Schwarts) introducerade begreppet gitterpolyedrar, vilket ledde till ännu ett exempel på kombinatorisk dualitet.

Efter att ha samarbetat med Ray Fulkerson och Rosa Oppenheim om balanserade matriser, generaliserade Hoffman Ford-Fulkerson maximum-flow-minimum-cut-resultatet till andra fall (flöde vid noder, oriktade bågar, etc.), vilket gav bevis för att alla tidigare kända fall var speciella fall. Den här artikeln introducerade också konceptet (men återigen, inte namnet) med fullständig dubbel integerness, idén bakom de flesta tillämpningar av linjär programmering för att bevisa extrema kombinatoriska teorem.

Under hela sin karriär studerade Hoffman en klass av heltalsprogrammeringsproblem som kunde lösas genom att successivt maximera variabler i någon ordning. Ett sådant exempel är det kompletta transportproblemet när kostnadsfaktorn uppvisar en speciell egenskap som upptäcktes för mer än ett sekel sedan av den franske matematikern Gaspard Monge. Detta tillvägagångssätt, som helt enkelt kallas "enkelt" i Hoffmans tidning, ansågs senare som "girigt" av Edmonds och Fulkerson. Monge-egenskapen genererar en antimatroid, och tack vare användningen av denna antimatroid kan Hoffmans resultat enkelt utökas till fallet med ofullständiga transportproblem. Hoffman återanvände termen "girig" för att beskriva en underklass av 0-1 matriser för vilka det dubbla linjära programmet kan lösas med en girig algoritm för alla högersidor och alla objektiva funktioner med minskande (med variabelt index) koefficienter. . Tillsammans med Kolen och Sakarovich visade han att för dessa matriser har motsvarande heltalsprogram en heltalsoptimal lösning för heltalsdata. Ett elegant och kortfattat papper från 1992 kännetecknar 0-1-matriser för vilka packnings- och täckningsproblemen kan lösas med ett girigt tillvägagångssätt. Det ger en enhetlig resultat för den kortaste vägen och minimala spännträdsproblem. Hans sista artikel om ämnet, "On Greedy Algorithms, Partially Ordered Sets, and Submodular Functions", som skrevs tillsammans med Dietrich, dök upp 2003.

Hoffman, tillsammans med Robert Singleton, konstruerade Hoffman-Singleton-grafen [5] , som är en unik Moore-graf av grad 7 och diameter 2 [3] . 1963 konstruerade han Hoffman Graph , som visserligen är kospektral till grafen för den fyrdimensionella hyperkuben Q 4 [6] , men vars radie är lika med 3 (det finns sådana hörn, vars kortaste väg till någon annan vertex av grafen består av högst tre kanter), medan radien för hyperkubgrafen Q 4 är lika med 4 [7] .

Utmärkelser och erkännande

Hoffman valdes in i National Academy of Sciences 1982 [1] , till American Academy of Arts and Sciences 1987 [1] och till det första medlemskapet i Institute for Operations Research and Management Sciences (INFORMS) 2002 [8] . 1992 tilldelades han tillsammans med Philip Wolf (också från IBM) John von Neumanns teoretiska pris [1] . Vetenskapens hedersdoktor från Technion (Israel Institute of Technology) sedan 1986.

Under sin långa karriär arbetade Hoffman i redaktionen för elva tidskrifter och var redaktör och grundare av den engelska tidskriften.  Linjär algebra och dess tillämpningar [1] . I en biografi publicerad i Hoffmans 65- årsdagsnummer skrev Uriel Rothblum att "Förutom hans vetenskapliga och professionella prestationer har Hoffman en oöverträffad förmåga att njuta av allt han gör. Han älskar att sjunga, spela pingis, ordlekar, kvicka historier och kanske mer än något annat att göra matte .

Utvalda publikationer

• Hoffman AJ, Jacobs W. Släta produktionsmönster  //  Management Science. - 1954. - Vol. 1 , iss. 1 . — S. 86–91 .
• Hoffman, AJ, Singleton, RR Moore grafer med diameter 2 och 3 // IBM Journal of Research and Development. - 1960. - V. 5 , nr. 4 . — S. 497–504 . - doi : 10.1147/rd.45.0497 .
• Hoffman AJ On the Polynomial of a Graph   // Amer . Matematik. En gång i månaden. - 1963. - Vol. 70 . - S. 30-36 .
• Hoffman AJ, Wolfe P. History of Traveling Salesman problem // The Travelling Salesman Problem  (Eng.) / Lawler EL, Lenstra JK, Rinnooy Kan AHG, & Shmoys DB, eds. — John Wiley, 1985.

En fullständig lista över publikationer finns på den personliga sidan [1] .

Anteckningar

1. ↑ 1 2 3 4 5 6 Personlig sida, IBM. Alan Hoffman  . IBM Research. Hämtad 14 november 2011. Arkiverad från originalet 14 mars 2012.
2. ↑ 1 2 3 4 5 6 7 Biografi om Alan J. Hoffman
3. ↑ 12 A.E. _ Brouwer & JH van Lint. Starkt regelbundna grafer och partiella geometrier // Uppräkning och design  (engelska) / DH Jackson, & SA Vanstone (red.). – Academic Press Inc. - S. 85-122.
4. ↑ Hoffman, AJ (Alan Jerome), 1924-. Utvalda tidningar av Alan Hoffman med kommentarer . - River Edge, NJ: World Scientific, 2003. - ISBN 978-981-279-693-6 .
5. ↑ Hoffman, AJ, Singleton, R. R. Moore grafer med diameter 2 och 3, 1960 .
6. ↑ Hoffman, A.J. On the Polynomial of a Graph, 1963 .
7. ↑ Weisstein, Eric W. Hoffman graf  på Wolfram MathWorld- webbplatsen .
8. ↑ Fellows: Alfabetisk  lista . Institutet för verksamhetsforskning och företagsledningsvetenskap. Hämtad: 9 oktober 2019.

Tematiska platser	Matematisk släktforskning zbMATH Öppna
I bibliografiska kataloger GND : 1103166549 ISNI : 0000 0001 1463 2648 J9U : 987007431043105171 LCCN : n78042498 NLG : 221689 NTA : 07088692X NUKAT : n2006011297 SUDOC : 164195823 VIAF : 110277368 WorldCat VIAF : 110277368