András Hajnal - András Hajnal
András Hajnal (13 maj 1931 - 30 juli 2016) var professor i matematik vid Rutgers University och medlem i ungerska vetenskapsakademien känd för sitt arbete inom uppsättningsteori och kombinatorik .
Biografi
Hajnal föddes den 13 maj 1931 i Budapest , Ungern .
Han fick sitt universitetsdiplom (M.Sc.) 1953 från Eötvös Loránd University , sin kandidat i matematisk vetenskapsexamen (ungefär motsvarande doktorsexamen) 1957, under överinseende av László Kalmár och hans doktor i matematisk Science degree 1962. Från 1956 till 1995 var han fakultetsmedlem vid Eötvös Loránd University ; 1994 flyttade han till Rutgers University för att bli direktör för DIMACS , och han stannade där som professor tills han gick i pension 2004. Han blev medlem i Ungerska vetenskapsakademin 1982 och ledde dess matematiska institut från 1982 till 1992 Han var generalsekreterare för János Bolyai Mathematical Society från 1980 till 1990 och ordförande i föreningen 1990 till 1994. Från 1981 var han en rådgivande redaktör för tidskriften Combinatorica . Hajnal var också en av hederspresidenterna för European Set Theory Society.
Hajnal var en ivrig schackspelare .
Hajnal var far till Peter Hajnal , meddekan för European College of Liberal Arts .
Forskning och publikationer
Hajnal var författare till över 150 publikationer. Bland de många medförfattarna till Paul Erdős hade han det näst största antalet gemensamma uppsatser, 56. Med Peter Hamburger skrev han en lärobok, Set Theory (Cambridge University Press, 1999, ISBN 0-521-59667-X ). Några av hans mer välciterade forskningsartiklar inkluderar
- Ett papper om kretsens komplexitet med Maas, Pudlak, Szegedy och György Turán, som visar exponentiellt lägre gränser för storleken på kretsar med begränsat djup med viktade majoritetsportar som löser problemet med att beräkna paritet hos inre produkter .
- Den Hajnal-Szemerédi sats på rättvis färg , bevisar en 1964 gissningar av Erdős: Låt Δ beteckna den högsta graden av ett hörn i en ändlig graf G . Då G kan färgas med Δ + 1 färger på ett sådant sätt att storlekarna på färg klasserna skiljer sig med högst en. Flera författare har därefter publicerat förenklingar och generaliseringar av detta resultat.
- Ett papper med Erdős och JW Moon grafer som slipper alla k - klick . Turáns sats kännetecknar graferna av denna typ med maximalt antal kanter; Erdős, Hajnal och Moon finner en liknande karakterisering av de minsta maximala k -klickfria graferna, vilket visar att de har formen av vissa delade grafer . Detta dokument visar också en gissning av Erdős och Gallai om antalet kanter i en kritisk graf för dominans .
- Ett papper med Erdős om graffärgproblem för oändliga grafer och hypergrafer . Detta papper sträcker sig giriga färgmetoder från ändliga till oändliga grafer: om hörnen i en graf kan vara välordnade så att varje hörn har få tidigare grannar har den ett lågt kromatiskt tal. När varje ändlig undergraf har en ordning av denna typ där antalet tidigare grannar är högst k (det vill säga det är k -genererat ) har en oändlig graf en välordning med högst 2 k -2 tidigare grannar per vertex. Papperet bevisar också att det inte finns några oändliga grafer med hög begränsad omkrets och tillräckligt stort oändligt kromatiskt tal och förekomsten av grafer med hög udda omkrets och oändligt kromatiskt tal.
Andra utvalda resultat inkluderar:
- I sin avhandling introducerade han modellerna L ( A ) (se relativ konstruerbarhet ) och bevisade att om κ är en vanlig kardinal och A är en delmängd av κ + , så håller ZFC och 2 κ = κ + i L ( A ). Detta kan tillämpas för att bevisa relativa konsistensresultat: t.ex. om 2 ℵ 0 = ℵ 2 är konsekvent så är 2 ℵ 0 = ℵ 2 och 2 ℵ 1 = ℵ 2 .
- Hajnals uppsättningskartläggningsteorem , lösningen på en gissning av Stanisław Ruziewicz . Detta arbete gäller funktioner ƒ som kartlägger medlemmarna i en oändlig uppsättning S till små delmängder av S ; mer specifikt bör alla undergrupper cardinalities vara mindre än vissa övre bunden som själv är mindre än kardinaliteten för S . Hajnal visar att S måste ha en likvärdig delmängd där inget par element x och y har x i ƒ ( y ) eller y i ƒ ( x ). Detta resultat utvidgar fallet n = 1 i Kuratowskis fria uppsättningssats , som säger att när ƒ kartlägger en otalig uppsättning till ändliga delmängder finns det ett par x , och ingen av dem tillhör bilden av den andra.
- Ett exempel på två grafer med vardera oräkneligt kromatiskt tal, men med otaligt kromatisk direktprodukt. Det vill säga Hedetniemis gissning misslyckas för oändliga grafer.
- I en artikel med Paul Erdős visade han flera resultat på system för oändliga mängder med fastighets B .
- Ett papper med Fred Galvin där de bevisade att if är en stark gräns kardinal då
- Med James Earl Baumgartner bevisade han ett resultat i oändlig Ramsey -teori , att för varje delning av hörnen i en komplett graf på ω 1 hörn till oändligt många delmängder, innehåller minst en av delmängderna en fullständig undergraf om α -hörn, för varje α <ω 1 . Detta kan uttryckas med notationen partitionsrelationer som
- Med Matthew Foreman bevisade han att om κ är mätbart så gäller partitionsrelationen för α <Ω, där Ω < κ + är en mycket stor ordinal.
- Med István Juhász publicerade han flera resultat inom uppsättningsteoretisk topologi . De etablerade först existensen av Hausdorff -utrymmen som ärftligt separerbara, men inte ärftligt Lindelöf, eller vice versa. Förekomsten av vanliga utrymmen med dessa egenskaper ( S-space och L-space ) avgjordes mycket senare av Todorcevic och Moore .
Pris och ära
År 1992 tilldelades Hajnal Officerkorset av Republiken Ungerns ordning. År 1999 hölls en konferens för att hedra hans 70 -årsdag på DIMACS , och en andra konferens som hedrade 70 -årsdagarna för både Hajnal och Vera Sós hölls 2001 i Budapest . Hajnal blev stipendiat i American Mathematical Society 2012.