Hoffman, Alan

Alan Jerome Hoffman ( Eng.  Alan Jerome Hoffman ; 30. maj 1924, New York  - 18. januar 2021 [2] ) var en amerikansk matematiker, der arbejdede ved IBM T. J. Watson Research Center . Redaktør og stifter af bladet Lineær algebra og dens anvendelser . Han bidrog til kombinatorisk optimering og egenværditeori for grafer. Hoffman konstruerede sammen med Robert Singleton Hoffman-Singleton grafen , som er en unik Moore graf af grad 7 og diameter 2 [3] .  

Biografi

Alan Hoffman kom ind på Columbia University i 1940 og modtog et Pulitzer-stipendium i 1940 i en alder af 16. Anden verdenskrig afbrød Hoffmans studier, han blev indkaldt til tjeneste i februar 1943 og tjente i den amerikanske hær fra 1943 til 1946, både i Europa og Stillehavet. Under grunduddannelsen på luftværnsartilleriskolen overvejede han muligheden for at udvikle aksiomer for cirklernes geometri [2] .

Da han vendte tilbage til Columbia i efteråret 1946, afsluttede han sin doktorafhandling om grundprincipperne for inversionsgeometri i 1950. Derefter tilbragte Hoffman et år på Institute for Advanced Study i Princeton (kontoret ved siden af ​​ham var besat af Albert Einstein ) [2] .

Tidlig karriere

Hoffmans første job var i Applied Mathematics Division af National Bureau of Standards . På Bureauet blev Hoffman førende inden for et nyt videnskabsområde, lineær programmering . Hoffman var en nøglearrangør af det indflydelsesrige Second Linear Programming Symposium afholdt på Bureauet i januar 1955 [2] .

I 1956 forlod Hoffman Bureauet og flyttede til England for at arbejde som kommunikationsforsker ved London-afdelingen af ​​Bureau of Naval Research. Da året nærmede sig enden i udlandet, blev Hoffman tilbudt to stillinger hos industrivirksomheder i New York City: den ene i en lille matematisk forskningsgruppe på det begyndende IBM Research Laboratory og den anden i hovedkvarteret for General Electric Company . Hoffman valgte en rolle i en mere etableret organisation. Ledelsen tillod ham at studere matematik, hvis dette ikke forstyrrede udførelsen af ​​de opgaver, han fik tildelt, og Hoffman fortsatte sin matematiske forskning, fuldstændig uden relation til hans hovedjob. I 1961 accepterede han en invitation til at blive medlem af IBM's T. J. Watson Research Center 2] .

Karriere hos IBM

I løbet af sin karriere hos IBM udgav Hoffman mere end 200 videnskabelige artikler, mere end en tredjedel af dem var medforfatter. Hans matematiske rækkevidde dækkede mange områder af matematik, fra algebra til operationsforskning [2] .

Sammenfatning af matematiske bidrag (fra hans noter i Selected Papers of Alan Hoffman) [4] .

Hoffmanns arbejde med geometri, begyndende med hans afhandling "On the Foundations of Inversion Geometry", inkluderede beviser for egenskaberne af affine planer, såvel som studiet af relationspunkter af endelige projektive planer, betingelser for regelmæssighed af forening og skæring af kegler ( hovedsageligt afledt af hans generalisering af hans tidligere resultater på rangeringen af ​​reelle matricer). Han præsenterede et alternativt bevis, baseret på aksiomer for nogle abstrakte systemer af konvekse sæt, for et resultat (Scarf og andre) på antallet af uligheder, der er nødvendige for at bestemme løsningen på et heltalsprogrammeringsproblem. Sætningen om dette abstrakte system ser ud til at være tæt beslægtet med antimatroider (også kendt som konvekse geometrier), selvom forbindelsen ikke er blevet fuldt ud undersøgt.

Hoffmans arbejde med kombinatorik har udvidet vores forståelse af flere klasser af grafer. Et foredrag fra 1956 af G. Hajos om intervalgrafer førte til Hoffmans karakterisering af sammenlignelighedsgrafer og senere, gennem samarbejde med Paul Gilmour, til GH-sætningen (også tilskrevet A. Guia-Ury). Inspireret af Edmonds matchende algoritme samarbejdede Hoffman med Ray Fulkerson og M. McAndrew Hoffman for at karakterisere sæt af heltal, der kunne matche potenserne og grænserne for hvert par af hjørner i en sådan graf. Derudover overvejede de, hvilke grafer i klassen af ​​alle grafer med et givet sæt af grader og grænser på antallet af kanter, der kan transformeres af et bestemt sæt af udvekslinger til ethvert andet sæt i klassen. Beviserne er tæt forbundet med den vigtige forestilling om Hilbert-grundlaget. En artikel om selv-ortogonale latinske firkanter, skrevet sammen med IBM-medforfatterne Don Coppersmith og R. Brighton, var inspireret af en anmodning om at planlægge en ægtefælle, der undgår mixed double til en lokal ketsjerklub. Det udmærker sig ved at være det eneste papir, som Hoffman har diskuteret uden for det matematiske samfund.

Delvist bestilte sæt har været et hyppigt studieemne for Hoffman. Et papir fra 1977 med D. E. Schwartz bruger lineær programmeringsdualitet til at generalisere Green og Kleitmans generalisering fra 1976 af Dilworths dekomponeringssætning for poseter, et andet eksempel på den samlende rolle, som dualitet spiller i mange kombinatoriske resultater.

Gennem hele sin karriere har Hoffman søgt efter enkle og elegante alternative beviser for etablerede teoremer. Disse alternative beviser førte ofte til generaliseringer og udvidelser. I slutningen af ​​1990'erne samarbejdede han med Cao, Chvatal og Vince for at udvikle et alternativt bevis ved hjælp af elementære metoder frem for lineær algebra eller Reisers 0-1 kvadratmatrixsætning.

Hoffmans arbejde med matrixuligheder og egenværdier er grundlaget for ethvert kursus i matrixteori. Af særlig charme, i tråd med hans forkærlighed for samlende tilgange, er hans 1975-opgave om lineære G-funktioner. Selvom beviset for denne Gershgorin-variation er længere og mere kompliceret end de andre, dækker det alle Ostrovsky-variationer og mange yderligere variationer som særlige tilfælde.

Hoffman var en inspirerende ældste, men deltog ikke aktivt i IBM's udvikling af en række produkter til lineær og heltalsprogrammering. Imidlertid fortsatte han med at udforske de kombinatoriske og algebraiske aspekter af lineær programmering og lineære uligheder, herunder en dejlig abstraktion af dualiteten af ​​lineær programmering (1963). Han fortsatte også med at bruge egenskaberne ved lineære uligheder til at bevise (eller mere elegant genbevis) konveksitetsresultater.

I samarbejde med Shmuel Winograd, også en IBM-stipendiat i matematikafdelingen, blev der udviklet en effektiv algoritme til at finde alle korteste afstande i et rettet netværk ved hjælp af matrix-pseudomultiplication. En række artikler om gitterpolyedre (nogle med Don Schwarts) introducerede begrebet gitterpolyedre, hvilket førte til endnu et eksempel på kombinatorisk dualitet.

Efter at have samarbejdet med Ray Fulkerson og Rosa Oppenheim om afbalancerede matricer, generaliserede Hoffman Ford-Fulkerson maksimum-flow-minimum-cut-resultatet til andre tilfælde (flow ved knuder, urettede buer osv.), hvilket gav bevis for, at alle tidligere kendte tilfælde var specielle sager. Denne artikel introducerede også konceptet (men igen, ikke navnet) med fuldstændig dobbelt integerness, ideen bag de fleste anvendelser af lineær programmering til at bevise ekstreme kombinatoriske teoremer.

Gennem hele sin karriere studerede Hoffman en klasse af heltalsprogrammeringsproblemer, der kunne løses ved successivt at maksimere variabler i en eller anden rækkefølge. Et sådant eksempel er det komplette transportproblem, når omkostningsfaktoren udviser en særlig egenskab, der blev opdaget for mere end et århundrede siden af ​​den franske matematiker Gaspard Monge. Denne tilgang, kaldet simpelthen "simpel" i Hoffmans papir, blev senere betragtet som "grådig" af Edmonds og Fulkerson. Monge-ejendommen genererer en antimatroid, og takket være brugen af ​​denne antimatroid kan Hoffmans resultat nemt udvides til tilfælde af ufuldstændige transportproblemer. Hoffman genbrugte udtrykket "greedy" til at beskrive en underklasse af 0-1 matricer, for hvilke det dobbelte lineære program kan løses ved en grådig algoritme for alle højre sider og alle objektive funktioner med faldende (ved variabelt indeks) koefficienter. . Sammen med Kolen og Sakarovich viste han, at for disse matricer har det tilsvarende heltalsprogram en heltalsoptimal løsning for heltalsdata. Et elegant og kortfattet papir fra 1992 kendetegner 0-1-matricer, hvor pakke- og afdækningsproblemerne kan løses med en grådig tilgang. Det giver ensartet resultater for den korteste vej og minimale spændingstræ-problemer. Hans sidste papir om emnet, "On Greedy Algorithms, Partially Ordered Sets, and Submodular Functions", medforfattet med Dietrich, udkom i 2003.

Hoffman konstruerede sammen med Robert Singleton Hoffman-Singleton grafen [5] , som er en unik Moore graf af grad 7 og diameter 2 [3] . I 1963 konstruerede han Hoffman-grafen , som, selvom den er kospektral i forhold til grafen for den firedimensionelle hyperkube Q 4 [6] , men hvis radius er lig med 3 (der er sådanne toppunkter, hvis korteste vej til ethvert andet toppunkt af grafen ikke består af mere end tre kanter), mens radius af hyperkubegrafen Q 4 er lig med 4 [7] .

Priser og anerkendelse

Hoffman blev valgt til National Academy of Sciences i 1982 [1] , til American Academy of Arts and Sciences i 1987 [1] og til det første medlemskab af Institute for Operations Research and Management Sciences (INFORMS) i 2002 [8] . I 1992 blev han sammen med Philip Wolf (også fra IBM) tildelt John von Neumann Theoretical Prize [1] . Æresdoktor i naturvidenskab fra Technion (Israel Institute of Technology) siden 1986.

I løbet af sin lange karriere tjente Hoffman i redaktionen af ​​elleve blade og var redaktør og grundlægger af det engelske blad.  Lineær algebra og dens anvendelser [1] . I en biografi offentliggjort i Hoffmans 65-års fødselsdagsudgave skrev Uriel Rothblum , at "Ud over hans videnskabelige og professionelle præstationer har Hoffman en enestående evne til at nyde alt, hvad han gør. Han elsker at synge, spille ping-pong, ordspil, vittige historier og måske mere end noget andet at lave matematik .

Udvalgte publikationer

• Hoffman AJ, Jacobs W. Glatte produktionsmønstre  //  Management Science. - 1954. - Bd. 1 , iss. 1 . — S. 86–91 .
• Hoffman, AJ, Singleton, RR Moore grafer med diameter 2 og 3 // IBM Journal of Research and Development. - 1960. - V. 5 , no. 4 . — S. 497–504 . - doi : 10.1147/rd.45.0497 .
• Hoffman AJ On the Polynomial of a Graph   // Amer . Matematik. Månedlige. - 1963. - Bd. 70 . - S. 30-36 .
• Hoffman AJ, Wolfe P. History of Travelling Salesman problem // The Travelling Salesman Problem  (Eng.) / Lawler EL, Lenstra JK, Rinnooy Kan AHG, & Shmoys DB, eds. - John Wiley, 1985.

En komplet liste over publikationer findes på den personlige side [1] .

Noter

1. ↑ 1 2 3 4 5 6 Personlig side, IBM. Alan Hoffman  . IBM Research. Hentet 14. november 2011. Arkiveret fra originalen 14. marts 2012.
2. ↑ 1 2 3 4 5 6 7 Biografi om Alan J. Hoffman
3. ↑ 12 A.E. _ Brouwer & JH van Lint. Stærkt regelmæssige grafer og partielle geometrier // Enumeration and Design  (engelsk) / DH Jackson, & SA Vanstone (red.). – Academic Press Inc. - S. 85-122.
4. ↑ Hoffman, AJ (Alan Jerome), 1924-. Udvalgte artikler af 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 og 3, 1960 .
6. ↑ Hoffman, A.J. On the Polynomial of a Graph, 1963 .
7. ↑ Weisstein, Eric W. Hoffman-graf  på Wolfram MathWorld- webstedet .
8. ↑ Fellows: Alfabetisk  liste . Institut for Driftsforskning og Ledelsesvidenskaberne. Hentet: 9. oktober 2019.

Tematiske steder	Matematisk genealogi zbMATH Åbn
I bibliografiske 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