András Hajnal (May 13, 1931 – July 30, 2016) was a professor of mathematics at
Rutgers University
Rutgers University (; RU), officially Rutgers, The State University of New Jersey, is a Public university, public land-grant research university consisting of four campuses in New Jersey. Chartered in 1766, Rutgers was originally called Queen's ...
and a member of the
Hungarian Academy of Sciences
The Hungarian Academy of Sciences ( hu, Magyar Tudományos Akadémia, MTA) is the most important and prestigious learned society of Hungary. Its seat is at the bank of the Danube in Budapest, between Széchenyi rakpart and Akadémia utca. Its ma ...
known for his work in
set theory
Set theory is the branch of mathematical logic that studies 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 mathematics, is mostly conce ...
and
combinatorics
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many appl ...
.
Biography
Hajnal was born on 13 May 1931,Curriculum vitae in
Budapest
Budapest (, ; ) is the capital and most populous city of Hungary. It is the ninth-largest city in the European Union by population within city limits and the second-largest city on the Danube river; the city has an estimated population ...
,
Hungary
Hungary ( hu, Magyarország ) is a landlocked country in Central Europe. Spanning of the 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 a ...
.
He received his university diploma (M.Sc. degree) in 1953 from the
Eötvös Loránd University
Eötvös Loránd University ( hu, Eötvös Loránd Tudományegyetem, ELTE) is a Hungarian public research university based in Budapest. Founded in 1635, ELTE is one of the largest and most prestigious public higher education institutions in Hung ...
, his
Candidate
A candidate, or nominee, is the prospective recipient of an award or honor, or a person seeking or being considered for some kind of position; for example:
* to be elected to an office — in this case a candidate selection procedure occurs.
* t ...
of Mathematical Science degree (roughly equivalent to Ph.D.) in 1957, under the supervision of
László Kalmár
László Kalmár (27 March 1905, Edde – 2 August 1976, Mátraháza) was a Hungarian mathematician and Professor at the University of Szeged. Kalmár is considered the founder of mathematical logic and theoretical computer science in Hungary ...
, 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
Eötvös Loránd University ( hu, Eötvös Loránd Tudományegyetem, ELTE) is a Hungarian public research university based in Budapest. Founded in 1635, ELTE is one of the largest and most prestigious public higher education institutions in Hung ...
; in 1994, he moved to Rutgers University to become the director of
DIMACS
The Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) is a collaboration between Rutgers University, Princeton University, and the research firms AT&T, Bell Labs, Applied Communication Sciences, and NEC. It was founded in ...
, 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
The János Bolyai Mathematical Society (Bolyai János Matematikai Társulat, BJMT) is the Hungarian mathematical society, named after János Bolyai, a 19th-century Hungarian mathematician, a co-discoverer of non-Euclidean geometry. It is the profes ...
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
''Combinatorica'' is an international journal of mathematics, publishing papers in the fields of combinatorics and computer science. It started in 1981, with László Babai and László Lovász as the editors-in-chief with Paul Erdős as honora ...
''. 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, called White and Black, each controlling an army of chess pieces in their color, with the objective to checkmate the opponent's king. It is sometimes called international chess or Western chess to disti ...
player.
Hajnal was the father of
Peter Hajnal
Peter may refer to:
People
* List of people named Peter, a list of people and fictional characters with the given name
* Peter (given name)
** Saint Peter (died 60s), apostle of Jesus, leader of the early Christian Church
* Peter (surname), a sur ...
Hajnal was the author of over 150 publications. Among the many co-authors of
Paul Erdős
Paul Erdős ( hu, Erdős Pál ; 26 March 1913 – 20 September 1996) was a Hungarian mathematician. He was one of the most prolific mathematicians and producers of mathematical conjectures of the 20th century. pursued and proposed problems in ...
, 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
In theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of the Boolean circuits that compute them. A related notion is the circui ...
with Maas, Pudlak, Szegedy, and György Turán, showing exponential lower bounds on the size of bounded-depth circuits with weighted
majority
A majority, also called a simple majority or absolute majority to distinguish it from #Related terms, related terms, is more than half of the total.Dictionary definitions of ''majority'' aMerriam-Websterparity of
inner products
In mathematics, an inner product space (or, rarely, a Hausdorff pre-Hilbert space) is a real vector space or a complex vector space with an operation called an inner product. The inner product of two vectors in the space is a scalar, often d ...
.
*The
Hajnal–Szemerédi theorem In graph theory, an area of mathematics, an equitable coloring is an assignment of colors to the vertices of an undirected graph, in such a way that
*No two adjacent vertices have the same color, and
*The numbers of vertices in any two color classe ...
on
equitable coloring In graph theory, an area of mathematics, an equitable coloring is an assignment of colors to the vertices of an undirected graph, in such a way that
*No two adjacent vertices have the same color, and
*The numbers of vertices in any two color classe ...
, 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, Jim Crow Era to refer to an African Americans, African American. In many places, it may be considered a Pejorative, slur, though it ...
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''-
clique
A clique ( AusE, CanE, or ), in the social sciences, is a group of individuals who interact with one another and share similar interests. Interacting with cliques is part of normative social development regardless of gender, ethnicity, or popular ...
s.
Turán's theorem
In graph theory, Turán's theorem bounds the number of edges that can be included in an undirected graph that does not have a complete subgraph of a given size. It is one of the central results of extremal graph theory, an area studying the large ...
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 graph
In graph theory, a branch of mathematics, a split graph is a graph in which the vertices can be partitioned into a clique and an independent set. Split graphs were first studied by , and independently introduced by .
A split graph may have m ...
s. This paper also proves a conjecture of Erdős and Gallai on the number of edges in a
critical graph
In graph theory, a critical graph is an undirected graph all of whose subgraphs have smaller chromatic number. In such a graph, every vertex or edge is a critical element, in the sense that its deletion would decrease the number of colors needed ...
for
domination
Domination or dominant may refer to:
Society
* World domination, which is mainly a conspiracy theory
* Colonialism in which one group (usually a nation) invades another region for material gain or to eliminate competition
* Chauvinism in which ...
.
*A paper with Erdős on
graph coloring
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...
problems for infinite graphs and
hypergraph
In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices.
Formally, an undirected hypergraph H is a pair H = (X,E) wh ...
s. This paper extends
greedy coloring
In the study of graph coloring problems in mathematics and computer science, a greedy coloring or sequential coloring is a coloring of the vertices of a graph formed by a greedy algorithm that considers the vertices of the graph in sequence an ...
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
In set theory, a regular cardinal is a cardinal number that is equal to its own cofinality. More explicitly, this means that \kappa is a regular cardinal if and only if every unbounded subset C \subseteq \kappa has cardinality \kappa. Infinite ...
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
Stanisław Ruziewicz (29 August 1889 – 12 July 1941) was a Polish mathematician and one of the founders of the Lwów School of Mathematics.
He was a former student of Wacław Sierpiński, earning his doctorate in 1913 from the University of Lw ...
. 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
In mathematics, two sets or classes ''A'' and ''B'' are equinumerous if there exists a one-to-one correspondence (or bijection) between them, that is, if there exists a function from ''A'' to ''B'' such that for every element ''y'' of ''B'', the ...
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 Kuratowski's free set theorem, named after Kazimierz Kuratowski, is a result of set theory, an area of mathematics. It is a result which has been largely forgotten for almost 50 years, but has been applied recently in solving several lattice theory ...
, 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
In graph theory, Hedetniemi's conjecture, formulated by Stephen T. Hedetniemi in 1966, concerns the connection between graph coloring and the tensor product of graphs. This conjecture states that
: \chi (G \times H ) = \min\.
Here \chi(G) denotes ...
fails for infinite graphs.
*In a paper with
Paul Erdős
Paul Erdős ( hu, Erdős Pál ; 26 March 1913 – 20 September 1996) was a Hungarian mathematician. He was one of the most prolific mathematicians and producers of mathematical conjectures of the 20th century. pursued and proposed problems in ...
he proved several results on systems of infinite sets having
property B
In mathematics, Property B is a certain 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 every set in ...
.
*A paper with
Fred Galvin
Frederick William Galvin is a mathematician, currently a professor at the University of Kansas. His research interests include set theory and combinatorics.
His notable combinatorial work includes the proof of the Dinitz conjecture. In set theory, ...
in which they proved that if is a strong limit cardinal then
*:
:This was the result which initiated
Shelah Shelah may refer to:
* Shelah (son of Judah), a son of Judah according to the Bible
* Shelah (name), a Hebrew personal name
* Shlach, the 37th weekly Torah portion (parshah) in the annual Jewish cycle of Torah reading
* Salih, a prophet described ...
James Earl Baumgartner
James Earl Baumgartner (March 23, 1943 – December 28, 2011) was an American mathematician who worked in set theory, mathematical logic and foundations, and topology.
Baumgartner was born in Wichita, Kansas, began his undergraduate study at the ...
he proved a result in infinite
Ramsey theory
Ramsey theory, named after the British mathematician and philosopher Frank P. Ramsey, is a branch of mathematics that focuses on the appearance of order in a substructure given a structure of a known size. Problems in Ramsey theory typically ask a ...
, that for every partition of the vertices of a
complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is ...
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 relation In mathematics, infinitary combinatorics, or combinatorial set theory, is an extension of ideas in combinatorics to infinite sets.
Some of the things studied include continuous graphs and trees, extensions of Ramsey's theorem, and Martin's axiom.
R ...
s as
*:
*With
Matthew Foreman
Matthew Dean Foreman is an American mathematician at
University of California, Irvine. He has made notable contributions in set theory and in ergodic theory.
Biography
Born in Los Alamos, New Mexico, Foreman earned his Ph.D. from the
Univer ...
he proved that if κ is
measurable
In mathematics, the concept of a measure is a generalization and formalization of Geometry#Length, area, and volume, geometrical measures (length, area, volume) and other common notions, such as mass and probability of events. These seemingly ...
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
This is a glossary of some terms used in the branch of mathematics known as topology. Although there is no absolute distinction between different areas of topology, the focus here is on general topology. The following definitions are also funda ...
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
The Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) is a collaboration between Rutgers University, Princeton University, and the research firms AT&T, Bell Labs, Applied Communication Sciences, and NEC. It was founded in ...
, and a second conference honoring the 70th birthdays of both Hajnal and
Vera Sós
Vera may refer to:
Names
*Vera (surname), a surname (including a list of people with the name)
*Vera (given name), a given name (including a list of people and fictional characters with the name)
**Vera (), archbishop of the archdiocese of Tarrag ...
was held in 2001 in
Budapest
Budapest (, ; ) is the capital and most populous city of Hungary. It is the ninth-largest city in the European Union by population within city limits and the second-largest city on the Danube river; the city has an estimated population ...
. 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, ...