- Biography
- Research and publications
- Awards and honors
- References
- External links
András Hajnal (May 13, 1931 – July 30, 2016[1][2]) was a professor of mathematics at Rutgers University[3] and a member of the Hungarian Academy of Sciences[4] known for his work in set theory and combinatorics.
Biography
Hajnal was born on 13 May 1931,[5] in Budapest, Hungary.
He received his university diploma (M.Sc. degree) in 1953 from the Eötvös Loránd University,[6] his Candidate of Mathematical Science degree (roughly equivalent to Ph.D.) in 1957, under the supervision of László Kalmár,[7] and his Doctor of Mathematical Science degree in 1962. From 1956 to 1995 he was a faculty member at the Eötvös Loránd University; in 1994, he moved to Rutgers University to become the director of DIMACS, and he remained there as a professor until his retirement in 2004.[5] He became a member of the Hungarian Academy of Sciences in 1982, and directed its mathematical institute from 1982 to 1992.[5] He was general secretary of the János Bolyai Mathematical Society from 1980 to 1990, and president of the society from 1990 to 1994.[5] Starting in 1981, he was an advisory editor of the journal Combinatorica. Hajnal was also one of the Honorary Presidents of the European Set Theory Society.
Hajnal was an avid chess player.[8]
Hajnal was the father of Peter Hajnal, the co-dean of the European College of Liberal Arts.
Research and publications
Hajnal was the author of over 150 publications.[9] Among the many co-authors of Paul Erdős, he had the second largest number of joint papers, 56.[10]
With Peter Hamburger, he wrote a textbook, Set Theory (Cambridge University Press, 1999, {{ISBN|0-521-59667-X}}). Some of his more well-cited research papers[11] include
- A paper on circuit complexity with Maas, Pudlak, Szegedy, and György Turán,[12] showing exponential lower bounds on the size of bounded-depth circuits with weighted majority gates that solve the problem of computing the parity of inner products.
- The Hajnal–Szemerédi theorem on equitable coloring, proving a 1964 conjecture of Erdős:[13] let Δ denote the maximum degree of a vertex in a finite graph G. Then G can be colored with Δ + 1 colors in such a way that the sizes of the color classes differ by at most one. Several authors have subsequently published simplifications and generalizations of this result.[14]
- A paper with Erdős and J. W. Moon on graphs that avoid having any k-cliques. Turán's theorem characterizes the graphs of this type with the maximum number of edges; Erdős, Hajnal and Moon find a similar characterization of the smallest maximal k-clique-free graphs, showing that they take the form of certain split graphs. This paper also proves a conjecture of Erdős and Gallai on the number of edges in a critical graph for domination.[15]
- A paper with Erdős on graph coloring problems for infinite graphs and hypergraphs.[16] This paper extends greedy coloring methods from finite to infinite graphs: if the vertices of a graph can be well-ordered so that each vertex has few earlier neighbors, it has low chromatic number. When every finite subgraph has an ordering of this type in which the number of previous neighbors is at most k (that is, it is k-degenerate), an infinite graph has a well-ordering with at most 2k − 2 earlier neighbors per vertex. The paper also proves the nonexistence of infinite graphs with high finite girth and sufficiently large infinite chromatic number and the existence of graphs with high odd girth and infinite chromatic number.
Other selected results include:
- In his dissertation[17] he introduced the models L(A) (see relative constructibility), and proved that if κ is a regular cardinal and A is a subset of κ+, then ZFC and 2κ = κ+ hold in L(A). This can be applied to prove relative consistency results: e.g., if 2ℵ0 = ℵ2 is consistent then so is 2ℵ0 = ℵ2 and 2ℵ1 = ℵ2.
- Hajnal's set mapping theorem, the solution to a conjecture of Stanisław Ruziewicz.[18] This work concerns functions ƒ that map the members of an infinite set S to small subsets of S; more specifically, all subsets' cardinalities should be smaller than some upper bound that is itself smaller than the cardinality of S. Hajnal shows that S must have an equinumerous subset in which no pair of elements x and y have x in ƒ(y) or y in ƒ(x). This result greatly extends the case n = 1 of Kuratowski's free set theorem, which states that when ƒ maps an uncountable set to finite subsets there exists a pair x, y neither of which belongs to the image of the other.
- An example of two graphs each with uncountable chromatic number, but with countably chromatic direct product.[19] That is, Hedetniemi's conjecture fails for infinite graphs.
- In a paper[20] with Paul Erdős he proved several results on systems of infinite sets having property B.
- A paper with Fred Galvin in which[21] they proved that if
is a strong limit cardinal then
This was the result which initiated Shelah's pcf theory.
- With James Earl Baumgartner he proved a result in infinite Ramsey theory, that for every partition of the vertices of a complete graph on ω1 vertices into finitely many subsets, at least one of the subsets contains a complete subgraph on α vertices, for every α < ω1.[22] This can be expressed using the notation of partition relations as
- With Matthew Foreman he proved that if κ is measurable then[23] the partition relation
holds for α < Ω, where Ω < κ+ is a very large ordinal. - With István Juhász he published several results in set-theoretic topology. They first established[24] the existence of Hausdorff spaces which are hereditarily separable, but not hereditarily Lindelöf, or vice versa. The existence of regular spaces with these properties (S-space and L-space) was much later settled, by Todorcevic and Moore.
Awards and honors
In 1992, Hajnal was awarded the Officer's Cross of the Order of the Republic of Hungary.[5] In 1999, a conference in honor of his 70th birthday was held at DIMACS,[25] and a second conference honoring the 70th birthdays of both Hajnal and Vera Sós was held in 2001 in Budapest.[26] Hajnal became a fellow of the American Mathematical Society[27] in 2012.
References
1. ^[https://www.facebook.com/809060619130294/photos/a.857845014251854.1073741828.809060619130294/1061525430550477/?type=1&theater Announcement from Rényi Institute]
2. ^Remembering András Hajnal (1931-2016)
3. ^Rutgers University Department of Mathematics – Emeritus Faculty {{Webarchive|url=https://web.archive.org/web/20100715123824/http://math.rutgers.edu/people/index.php?type=faculty-emeritus&id=149 |date=2010-07-15 }}.
4. ^Hungarian Academy of Sciences, Section for Mathematics {{webarchive |url=https://web.archive.org/web/20090311073142/http://www.math.bme.hu/akademia/akada.html |date=March 11, 2009 }}.
5. ^1 2 3 4 Curriculum vitae.
6. ^A halmazelmélet huszadik századi "Hajnal A", M. Streho's interview with A. H., Magyar Tudomány, 2001.
7. ^{{mathgenealogy|id=24611|name=Andras Hajnal}}. The 1957 date is from Hajnal's cv; the mathematics genealogy site lists the date of Hajnal's Ph.D. as 1956.
8. ^The announcement {{webarchive|url=https://web.archive.org/web/20080724013925/http://atlas-conferences.com/f/a/b/c/58.dir/second.txt |date=2008-07-24 }} for the 2001 conference in honor of Hajnal and Sós calls him “the great chess player”; the conference included a blitz chess tournament in his honor.
9. ^List of publications {{webarchive |url=https://web.archive.org/web/20100716114722/http://www.math.rutgers.edu/~ahajnal/hajnalpu.pdf |date=July 16, 2010 }} from Hajnal's web site.
10. ^[https://files.oakland.edu/users/grossman/enp/Erdos0p.html List of collaborators of Erdős by number of joint papers], from the Erdős number project web site.
11. ^According to citation counts from Google scholar, retrieved March 1, 2009.
12. ^{{citation|contribution=Threshold circuits of bounded depth|first1=A.|last1=Hajnal|first2=W.|last2=Maass|first3=P.|last3=Pudlak|first4=M.|last4=Szegedy|first5=G.|last5=Turán|title=Proc. 28th Symp. Foundations of Computer Science (FOCS 1987)|pages=99–110|year=1987|doi=10.1109/SFCS.1987.59}}
13. ^{{citation|contribution=Proof of a conjecture of P. Erdős|first1=A.|last1=Hajnal|first2=E.|last2=Szemerédi|author2-link=Endre Szemerédi|title=Combinatorial theory and its applications, II (Proc. Colloq., Balatonfüred, 1969)|publisher=North-Holland|year=1970|pages=601–623|mr=0297607}}
14. ^{{citation | last = Catlin | first = Paul A. | journal = Utilitas Mathematica | pages = 163–177 | title = On the Hajnal–Szemerédi theorem on disjoint cliques | volume = 17 | year = 1980 | mr = 583138}}; {{citation | last = Fischer | first = Eldar | doi = 10.1002/(SICI)1097-0118(199908)31:4<275::AID-JGT2>3.0.CO;2-F | issue = 4 | journal = Journal of Graph Theory | pages = 275–282 | title = Variants of the Hajnal–Szemerédi theorem | volume = 31 | year = 1999 | mr = 1698745}}; {{citation | last1 = Kierstead | first1 = H. A. | last2 = Kostochka | first2 = A. V. | doi = 10.1017/S0963548307008619 | issue = 2 | journal = Combinatorics, Probability and Computing | pages = 265–270 | title = A short proof of the Hajnal–Szemerédi theorem on equitable colouring | volume = 17 | year = 2008 | mr = 2396352}}; {{citation | last1 = Martin | first1 = Ryan | last2 = Szemerédi | first2 = Endre | doi = 10.1016/j.disc.2007.08.019 | issue = 19 | journal = Discrete Mathematics | pages = 4337–4360 | title = Quadripartite version of the Hajnal–Szemerédi theorem | volume = 308 | year = 2008 | mr = 2433861}}
15. ^{{citation|doi=10.2307/2311408|first1=P.|last1=Erdős|author1-link=Paul Erdős|first2=A.|last2=Hajnal|first3=J. W.|last3=Moon|title=A problem in graph theory|journal=American Mathematical Monthly|volume=71|issue=10|pages=1107–1110|publisher=Mathematical Association of America|year=1964|jstor=2311408|mr=0170339}}
16. ^{{citation|first1=P.|last1=Erdős|author1-link=Paul Erdős|first2=A.|last2=Hajnal|title=On chromatic number of graphs and set-systems|journal=Acta Mathematica Hungarica|volume=17|issue=1–2|pages=61–99|year=1966|doi=10.1007/BF02020444|mr=0193025}}
17. ^{{citation|doi=10.1007/BF02023921|first=A.|last=Hajnal|title=On a consistency theorem connected with the generalized continuum problem|journal=Acta Math. Acad. Sci. Hung.|volume=12|year=1961|pages=321–376|mr=0150046|issue=3–4}}
18. ^{{citation|first=A.|last=Hajnal|title=Proof of a conjecture of S. Ruziewicz|journal=Fund. Math.|volume=50|year=1961–1962|pages=123–128|mr=0131986|doi=10.4064/fm-50-2-123-128}}
19. ^{{Citation | author = Hajnal, A. | title = The chromatic number of the product of two ℵ1 chromatic graphs can be countable | journal = Combinatorica | volume = 5 | year = 1985 | pages = 137–140 | mr = 0815579 | doi = 10.1007/BF02579376 | postscript = . | issue = 2}}
20. ^P. Erdős, A. Hajnal: On a property of families of sets, Acta Math. Acad. Sci. Hung.., 12(1961), 87–123.
21. ^{{citation|doi=10.2307/1970936|first1=F.|last1=Galvin|author1-link=Fred Galvin|first2=A.|last2=Hajnal|title=Inequalities for cardinal powers|journal=Annals of Mathematics |series=Second Series|volume=101|issue=3|year=1975|pages=491–498|jstor=1970936}}
22. ^{{citation | last1 = Baumgartner | first1 = J. | last2 = Hajnal | first2 = A. | issue = 3 | journal = Polska Akademia Nauk. Fundamenta Mathematicae | pages = 193–203 | title = A proof (involving Martin's axiom) of a partition relation | volume = 78 | year = 1973 | mr = 0319768 | doi=10.4064/fm-78-3-193-203}}. For additional results of Baumgartner and Hajnal on partition relations, see the following two papers: {{citation | last1 = Baumgartner | first1 = J. E. | last2 = Hajnal | first2 = A. | contribution = A remark on partition relations for infinite ordinals with an application to finite combinatorics | location = Providence, RI | pages = 157–167 | publisher = Amer. Math. Soc. | series = Contemp. Math. | title = Logic and combinatorics (Arcata, Calif., 1985) | volume = 65 | year = 1987 | mr = 891246 | doi=10.1090/conm/065/891246}}; {{citation | last1 = Baumgartner | first1 = James E. | last2 = Hajnal | first2 = Andras | doi = 10.2307/2695046 | issue = 2 | journal = The Journal of Symbolic Logic | pages = 811–821 | title = Polarized partition relations | volume = 66 | year = 2001 | publisher = Association for Symbolic Logic | jstor = 2695046 | mr = 1833480}}
23. ^{{cite journal | last1 = Foreman | first1 = M. | last2 = Hajnal | first2 = A. | year = 2003 | title = A partition relation for successors of large cardinals | url = | journal = Math. Ann. | volume = 325 | issue = | pages = 583–623 | doi=10.1007/s00208-002-0323-7}}
24. ^A. Hajnal, I. Juhász: On hereditarily α-Lindelöf and hereditarily α-separable spaces, Ann. Univ. Sci. Budapest. Eötvös Sect. Math., 11(1968), 115–124.
25. ^{{citation|title=Set Theory: The Hajnal Conference, October 15–17, 1999 DIMACS Center|editor-first=Simon|editor-last=Thomas|publisher=American Mathematical Society|year=1999|isbn=978-0-8218-2786-4|series=DIMACS Series in Discrete Mathematics and Theoretical Computer Science|volume=58}}
26. ^{{citation|title=More sets, graphs and numbers: a salute to Vera Sós and András Hajnal|editor1-first=Ervin|editor1-last=Győri|editor2-first=Gyula O. H.|editor2-last=Katona|editor2-link=Gyula O. H. Katona|editor3-first=László|editor3-last=Lovász|editor3-link=László Lovász|publisher=Springer-Verlag|year=2006|isbn=978-3-540-32377-8|series=Bolyai Society Mathematical Studies|volume=15}}
27. ^List of Fellows of the American Mathematical Society
2. ^Remembering András Hajnal (1931-2016)
3. ^Rutgers University Department of Mathematics – Emeritus Faculty {{Webarchive|url=https://web.archive.org/web/20100715123824/http://math.rutgers.edu/people/index.php?type=faculty-emeritus&id=149 |date=2010-07-15 }}.
4. ^Hungarian Academy of Sciences, Section for Mathematics {{webarchive |url=https://web.archive.org/web/20090311073142/http://www.math.bme.hu/akademia/akada.html |date=March 11, 2009 }}.
5. ^1 2 3 4 Curriculum vitae.
6. ^A halmazelmélet huszadik századi "Hajnal A", M. Streho's interview with A. H., Magyar Tudomány, 2001.
7. ^{{mathgenealogy|id=24611|name=Andras Hajnal}}. The 1957 date is from Hajnal's cv; the mathematics genealogy site lists the date of Hajnal's Ph.D. as 1956.
8. ^The announcement {{webarchive|url=https://web.archive.org/web/20080724013925/http://atlas-conferences.com/f/a/b/c/58.dir/second.txt |date=2008-07-24 }} for the 2001 conference in honor of Hajnal and Sós calls him “the great chess player”; the conference included a blitz chess tournament in his honor.
9. ^List of publications {{webarchive |url=https://web.archive.org/web/20100716114722/http://www.math.rutgers.edu/~ahajnal/hajnalpu.pdf |date=July 16, 2010 }} from Hajnal's web site.
10. ^[https://files.oakland.edu/users/grossman/enp/Erdos0p.html List of collaborators of Erdős by number of joint papers], from the Erdős number project web site.
11. ^According to citation counts from Google scholar, retrieved March 1, 2009.
12. ^{{citation|contribution=Threshold circuits of bounded depth|first1=A.|last1=Hajnal|first2=W.|last2=Maass|first3=P.|last3=Pudlak|first4=M.|last4=Szegedy|first5=G.|last5=Turán|title=Proc. 28th Symp. Foundations of Computer Science (FOCS 1987)|pages=99–110|year=1987|doi=10.1109/SFCS.1987.59}}
13. ^{{citation|contribution=Proof of a conjecture of P. Erdős|first1=A.|last1=Hajnal|first2=E.|last2=Szemerédi|author2-link=Endre Szemerédi|title=Combinatorial theory and its applications, II (Proc. Colloq., Balatonfüred, 1969)|publisher=North-Holland|year=1970|pages=601–623|mr=0297607}}
14. ^{{citation | last = Catlin | first = Paul A. | journal = Utilitas Mathematica | pages = 163–177 | title = On the Hajnal–Szemerédi theorem on disjoint cliques | volume = 17 | year = 1980 | mr = 583138}}; {{citation | last = Fischer | first = Eldar | doi = 10.1002/(SICI)1097-0118(199908)31:4<275::AID-JGT2>3.0.CO;2-F | issue = 4 | journal = Journal of Graph Theory | pages = 275–282 | title = Variants of the Hajnal–Szemerédi theorem | volume = 31 | year = 1999 | mr = 1698745}}; {{citation | last1 = Kierstead | first1 = H. A. | last2 = Kostochka | first2 = A. V. | doi = 10.1017/S0963548307008619 | issue = 2 | journal = Combinatorics, Probability and Computing | pages = 265–270 | title = A short proof of the Hajnal–Szemerédi theorem on equitable colouring | volume = 17 | year = 2008 | mr = 2396352}}; {{citation | last1 = Martin | first1 = Ryan | last2 = Szemerédi | first2 = Endre | doi = 10.1016/j.disc.2007.08.019 | issue = 19 | journal = Discrete Mathematics | pages = 4337–4360 | title = Quadripartite version of the Hajnal–Szemerédi theorem | volume = 308 | year = 2008 | mr = 2433861}}
15. ^{{citation|doi=10.2307/2311408|first1=P.|last1=Erdős|author1-link=Paul Erdős|first2=A.|last2=Hajnal|first3=J. W.|last3=Moon|title=A problem in graph theory|journal=American Mathematical Monthly|volume=71|issue=10|pages=1107–1110|publisher=Mathematical Association of America|year=1964|jstor=2311408|mr=0170339}}
16. ^{{citation|first1=P.|last1=Erdős|author1-link=Paul Erdős|first2=A.|last2=Hajnal|title=On chromatic number of graphs and set-systems|journal=Acta Mathematica Hungarica|volume=17|issue=1–2|pages=61–99|year=1966|doi=10.1007/BF02020444|mr=0193025}}
17. ^{{citation|doi=10.1007/BF02023921|first=A.|last=Hajnal|title=On a consistency theorem connected with the generalized continuum problem|journal=Acta Math. Acad. Sci. Hung.|volume=12|year=1961|pages=321–376|mr=0150046|issue=3–4}}
18. ^{{citation|first=A.|last=Hajnal|title=Proof of a conjecture of S. Ruziewicz|journal=Fund. Math.|volume=50|year=1961–1962|pages=123–128|mr=0131986|doi=10.4064/fm-50-2-123-128}}
19. ^{{Citation | author = Hajnal, A. | title = The chromatic number of the product of two ℵ1 chromatic graphs can be countable | journal = Combinatorica | volume = 5 | year = 1985 | pages = 137–140 | mr = 0815579 | doi = 10.1007/BF02579376 | postscript = . | issue = 2}}
20. ^P. Erdős, A. Hajnal: On a property of families of sets, Acta Math. Acad. Sci. Hung.., 12(1961), 87–123.
21. ^{{citation|doi=10.2307/1970936|first1=F.|last1=Galvin|author1-link=Fred Galvin|first2=A.|last2=Hajnal|title=Inequalities for cardinal powers|journal=Annals of Mathematics |series=Second Series|volume=101|issue=3|year=1975|pages=491–498|jstor=1970936}}
22. ^{{citation | last1 = Baumgartner | first1 = J. | last2 = Hajnal | first2 = A. | issue = 3 | journal = Polska Akademia Nauk. Fundamenta Mathematicae | pages = 193–203 | title = A proof (involving Martin's axiom) of a partition relation | volume = 78 | year = 1973 | mr = 0319768 | doi=10.4064/fm-78-3-193-203}}. For additional results of Baumgartner and Hajnal on partition relations, see the following two papers: {{citation | last1 = Baumgartner | first1 = J. E. | last2 = Hajnal | first2 = A. | contribution = A remark on partition relations for infinite ordinals with an application to finite combinatorics | location = Providence, RI | pages = 157–167 | publisher = Amer. Math. Soc. | series = Contemp. Math. | title = Logic and combinatorics (Arcata, Calif., 1985) | volume = 65 | year = 1987 | mr = 891246 | doi=10.1090/conm/065/891246}}; {{citation | last1 = Baumgartner | first1 = James E. | last2 = Hajnal | first2 = Andras | doi = 10.2307/2695046 | issue = 2 | journal = The Journal of Symbolic Logic | pages = 811–821 | title = Polarized partition relations | volume = 66 | year = 2001 | publisher = Association for Symbolic Logic | jstor = 2695046 | mr = 1833480}}
23. ^{{cite journal | last1 = Foreman | first1 = M. | last2 = Hajnal | first2 = A. | year = 2003 | title = A partition relation for successors of large cardinals | url = | journal = Math. Ann. | volume = 325 | issue = | pages = 583–623 | doi=10.1007/s00208-002-0323-7}}
24. ^A. Hajnal, I. Juhász: On hereditarily α-Lindelöf and hereditarily α-separable spaces, Ann. Univ. Sci. Budapest. Eötvös Sect. Math., 11(1968), 115–124.
25. ^{{citation|title=Set Theory: The Hajnal Conference, October 15–17, 1999 DIMACS Center|editor-first=Simon|editor-last=Thomas|publisher=American Mathematical Society|year=1999|isbn=978-0-8218-2786-4|series=DIMACS Series in Discrete Mathematics and Theoretical Computer Science|volume=58}}
26. ^{{citation|title=More sets, graphs and numbers: a salute to Vera Sós and András Hajnal|editor1-first=Ervin|editor1-last=Győri|editor2-first=Gyula O. H.|editor2-last=Katona|editor2-link=Gyula O. H. Katona|editor3-first=László|editor3-last=Lovász|editor3-link=László Lovász|publisher=Springer-Verlag|year=2006|isbn=978-3-540-32377-8|series=Bolyai Society Mathematical Studies|volume=15}}
27. ^List of Fellows of the American Mathematical Society
External links
- [https://web.archive.org/web/20090227064734/http://math.rutgers.edu/~ahajnal/ Hajnal's web page at Rutgers].
- Hajnal's web page at the Hungarian academy of sciences
10 : 1931 births|2016 deaths|American mathematicians|Rutgers University faculty|Set theorists|Graph theorists|Members of the Hungarian Academy of Sciences|Fellows of the American Mathematical Society|20th-century Hungarian mathematicians|21st-century Hungarian mathematicians
- Rayagiri
- Ray Agnew
- Ray Aguilar
- Rayah
- Ray Ahipene-Mercer
- Raya Jet
- Rayak
- Ray A. Kroc
- Ray Alder
- Ray Alexander (gridiron football)
- Ray Allen Rudder
- Ray Allen (ventriloquist)
- Ray Allison
- Rayamangalam
- Ray Amm
- Ray Amstrong
- Rayan
- Ray and Charles Eames
- Ray Anderson (broadcaster)
- Ray and Faye Copeland
- Ray (anime)
- Ray Anthony
- Rayaparthy
- Rayapati Sambasiva Rao
- Ray Apollo