András Hajnal (May 13, 1931 – July 30, 2016) was a professor of mathematics at
Rutgers University
Rutgers University ( ), officially Rutgers, The State University of New Jersey, is a Public university, public land-grant research university consisting of three campuses in New Jersey. Chartered in 1766, Rutgers was originally called Queen's C ...
and a member of the
Hungarian Academy of Sciences known for his work in
set theory
Set theory is the branch of mathematical logic that studies Set (mathematics), sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory – as a branch of mathema ...
and
combinatorics
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and as an end to obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ...
.
Biography
Hajnal was born on 13 May 1931,
[Curriculum vitae](_blank)
in
Budapest
Budapest is the Capital city, capital and List of cities and towns of Hungary, most populous city of Hungary. It is the List of cities in the European Union by population within city limits, tenth-largest city in the European Union by popul ...
,
Hungary
Hungary is a landlocked country in Central Europe. Spanning much of the Pannonian Basin, Carpathian Basin, it is bordered by Slovakia to the north, Ukraine to the northeast, Romania to the east and southeast, Serbia to the south, Croatia and ...
.
He received his university diploma (M.Sc. degree) in 1953 from the
Eötvös Loránd University, his
Candidate
A candidate, or nominee, is a prospective recipient of an award or honor, or a person seeking or being considered for some kind of position. For example, one can be a candidate for membership in a group (sociology), group or election to an offic ...
of Mathematical Science degree (roughly equivalent to Ph.D.) in 1957, under the supervision of
László Kalmár, 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.
He became a member of the Hungarian Academy of Sciences in 1982, and directed its
mathematical institute from 1982 to 1992.
He was general secretary of the
János Bolyai Mathematical Society from 1980 to 1990, and president of the society from 1990 to 1994.
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
Chess is a board game for two players. It is an abstract strategy game that involves Perfect information, no hidden information and no elements of game of chance, chance. It is played on a square chessboard, board consisting of 64 squares arran ...
player.
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. Among the many co-authors of
Paul Erdős, he had the second largest number of joint papers, 56.
With Peter Hamburger, he wrote a textbook, ''Set Theory'' (Cambridge University Press, 1999, ). Some of his more well-cited research papers include
*A paper on
circuit complexity with Maas, Pudlak,
Szegedy, and György Turán, 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: let Δ denote the maximum degree of a vertex in a finite graph ''G''. Then ''G'' can be
colored
''Colored'' (or ''coloured'') is a racial descriptor historically used in the United States during the Jim Crow era to refer to an African American. In many places, it may be considered a slur.
Dictionary definitions
The word ''colored'' wa ...
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.
*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.
*A paper with Erdős on
graph coloring
In graph theory, graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a Graph (discrete mathematics), graph. The assignment is subject to certain constraints, such as that no two adjacent elements have th ...
problems for infinite graphs and
hypergraphs. 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 2''k'' − 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 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. 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. That is,
Hedetniemi's conjecture fails for infinite graphs.
*In a paper with
Paul Erdős he proved several results on systems of infinite sets having
property B
In mathematics, Property B is a certain set theory, set theoretic property. Formally, given a finite set ''X'', a collection ''C'' of subsets of ''X'' has Property B if we can partition ''X'' into two disjoint subsets ''Y'' and ''Z'' such that eve ...
.
*A paper with
Fred Galvin in which 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
Ramsey theory, named after the British mathematician and philosopher Frank P. Ramsey, is a branch of the mathematical field of combinatorics that focuses on the appearance of order in a substructure given a structure of a known size. Problems in R ...
, 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. This can be expressed using the notation of
partition relations as
*:
*With
Matthew Foreman he proved that if κ is
measurable then 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 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.
In 1999, a conference in honor of his 70th birthday was held at
DIMACS, and a second conference honoring the 70th birthdays of both Hajnal and
Vera Sós was held in 2001 in
Budapest
Budapest is the Capital city, capital and List of cities and towns of Hungary, most populous city of Hungary. It is the List of cities in the European Union by population within city limits, tenth-largest city in the European Union by popul ...
. Hajnal became a fellow of the
American Mathematical Society
The American Mathematical Society (AMS) is an association of professional mathematicians dedicated to the interests of mathematical research and scholarship, and serves the national and international community through its publications, meetings, ...
List of Fellows of the American Mathematical Society
/ref> in 2012.
References
External links
Hajnal's web page at Rutgers
Hajnal's web page at the Hungarian academy of sciences
{{DEFAULTSORT:Hajnal, Andras
1931 births
2016 deaths
20th-century 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
21st-century American mathematicians