Endre Szemerédi
Encyclopedia
Endre Szemerédi is a Hungarian
mathematician
, working in the field of combinatorics
and theoretical computer science. He is the State of New Jersey Professor of computer science at Rutgers University
since 1986. He has held visiting positions at Stanford University
(1974), McGill University
(1980), University of South Carolina
(1981–1983) and University of Chicago
(1985–1986). He was born in Budapest
, studied in Eötvös Loránd University in Budapest and received his PhD from Moscow State University
. His adviser was the late mathematician Israel Gelfand
.
and Paul Turán: if a sequence of natural numbers has positive upper density then it contains arbitrarily long arithmetic progression
s. This is now known as Szemerédi's theorem
. One of the key tools introduced in his proof is now known as
the Szemerédi regularity lemma
, which has become a very important tool in combinatorics
.
He is also known for the Szemerédi-Trotter theorem in incidence geometry
and the Hajnal-Szemerédi theorem in graph theory
.Ajtai
and Szemerédi proved the corners theorem
, an important step toward higher dimensional generalizations of the Szemerédi theorem
. With Ajtai
and Komlós
he proved the ct2/log t upper bound for the Ramsey number R(3,t). With Ajtai
, Chvátal
, and M. M. Newborn, Szemerédi proved the famous Crossing Lemma, that a graph
with n vertices and m edges, where has at least crossings.
Endre Szemeredi is a corresponding member (1982), and member (1987) of the Hungarian Academy of Sciences
and a member (2010) of the National Academy of Sciences
. He is also a member of the Institute for Advanced Study
(IAS), Princeton University (2007–2010) and a permanent research fellow at the Rényi Institute of Mathematics, Budapest.
He was the Fairchild Distinguished Scholar at CALTECH in 1987-88.
Prof. Szemeredi is an honorary doctor of the Charles University, Prague.
He was the lecturer in the Forty-Seventh Annual DeLong Lecture Series at University of Colorado.
He is also a recipient of the Aisenstadt Chair at CRM, University of Montreal. In 2008 he was the Eisenbud Professor at MSRI Berkeley.
Prior to the conference a volume of the Bolyai Society Mathematical Studies Series, An Irregular Mind, a collection of papers edited by Imre Bárány
and József Solymosi, was published to celebrate Szemerédi's achievements on the occasion of his 70th birthday.
Hungary
Hungary , officially the Republic of Hungary , is a landlocked country in Central Europe. It is situated in the Carpathian Basin and is bordered by Slovakia to the north, Ukraine and Romania to the east, Serbia and Croatia to the south, Slovenia to the southwest and Austria to the west. The...
mathematician
Mathematician
A mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....
, working in the field of combinatorics
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
and theoretical computer science. He is the State of New Jersey Professor of computer science at Rutgers University
Rutgers University
Rutgers, The State University of New Jersey , is the largest institution for higher education in New Jersey, United States. It was originally chartered as Queen's College in 1766. It is the eighth-oldest college in the United States and one of the nine Colonial colleges founded before the American...
since 1986. He has held visiting positions at Stanford University
Stanford University
The Leland Stanford Junior University, commonly referred to as Stanford University or Stanford, is a private research university on an campus located near Palo Alto, California. It is situated in the northwestern Santa Clara Valley on the San Francisco Peninsula, approximately northwest of San...
(1974), McGill University
McGill University
Mohammed Fathy is a public research university located in Montreal, Quebec, Canada. The university bears the name of James McGill, a prominent Montreal merchant from Glasgow, Scotland, whose bequest formed the beginning of the university...
(1980), University of South Carolina
University of South Carolina
The University of South Carolina is a public, co-educational research university located in Columbia, South Carolina, United States, with 7 surrounding satellite campuses. Its historic campus covers over in downtown Columbia not far from the South Carolina State House...
(1981–1983) and University of Chicago
University of Chicago
The University of Chicago is a private research university in Chicago, Illinois, USA. It was founded by the American Baptist Education Society with a donation from oil magnate and philanthropist John D. Rockefeller and incorporated in 1890...
(1985–1986). He was born in Budapest
Budapest
Budapest is the capital of Hungary. As the largest city of Hungary, it is the country's principal political, cultural, commercial, industrial, and transportation centre. In 2011, Budapest had 1,733,685 inhabitants, down from its 1989 peak of 2,113,645 due to suburbanization. The Budapest Commuter...
, studied in Eötvös Loránd University in Budapest and received his PhD from Moscow State University
Moscow State University
Lomonosov Moscow State University , previously known as Lomonosov University or MSU , is the largest university in Russia. Founded in 1755, it also claims to be one of the oldest university in Russia and to have the tallest educational building in the world. Its current rector is Viktor Sadovnichiy...
. His adviser was the late mathematician Israel Gelfand
Israel Gelfand
Israel Moiseevich Gelfand, also written Israïl Moyseyovich Gel'fand, or Izrail M. Gelfand was a Soviet mathematician who made major contributions to many branches of mathematics, including group theory, representation theory and functional analysis...
.
Work
Endre Szemerédi has published over 200 scientific articles in the fields of Discrete Mathematics, Theoretical Computer Science, Arithmetic Combinatorics and Discrete Geometry. He is best known for his proof from 1975 of an old conjecture of Paul ErdősPaul Erdos
Paul Erdős was a Hungarian mathematician. Erdős published more papers than any other mathematician in history, working with hundreds of collaborators. He worked on problems in combinatorics, graph theory, number theory, classical analysis, approximation theory, set theory, and probability theory...
and Paul Turán: if a sequence of natural numbers has positive upper density then it contains arbitrarily long arithmetic progression
Arithmetic progression
In mathematics, an arithmetic progression or arithmetic sequence is a sequence of numbers such that the difference between the consecutive terms is constant...
s. This is now known as Szemerédi's theorem
Szemerédi's theorem
In number theory, Szemerédi's theorem is a result that was formerly the Erdős–Turán conjecture...
. One of the key tools introduced in his proof is now known as
the Szemerédi regularity lemma
Szemerédi regularity lemma
In mathematics, the Szemerédi regularity lemma states that every large enough graph can be divided into subsets of about the same size so that the edges between different subsets behave almost randomly. introduced a weaker version of this lemma, restricted to bipartite graphs, in order to prove ...
, which has become a very important tool in combinatorics
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
.
He is also known for the Szemerédi-Trotter theorem in incidence geometry
Incidence geometry (structure)
Incidence geometry is an area of mathematics that studies relations of incidence between various geometrical objects such as points, lines, curves, and planes. A specific collection of such objects is called a mathematical structure...
and the Hajnal-Szemerédi theorem in graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
.Ajtai
Miklós Ajtai
Miklós Ajtai is a computer scientist at the IBM Almaden Research Center. In 2003 he received the Knuth Prize for his numerous contributions to the field, including a classic sorting network algorithm Miklós Ajtai (born 2 July 1946, Budapest, Hungary) is a computer scientist at the IBM Almaden...
and Szemerédi proved the corners theorem
Corners theorem
In mathematics, the corners theorem is an important result, proved by Miklós Ajtai and Endre Szemerédi, of a statement in arithmetic combinatorics...
, an important step toward higher dimensional generalizations of the Szemerédi theorem
Szemerédi's theorem
In number theory, Szemerédi's theorem is a result that was formerly the Erdős–Turán conjecture...
. With Ajtai
Miklós Ajtai
Miklós Ajtai is a computer scientist at the IBM Almaden Research Center. In 2003 he received the Knuth Prize for his numerous contributions to the field, including a classic sorting network algorithm Miklós Ajtai (born 2 July 1946, Budapest, Hungary) is a computer scientist at the IBM Almaden...
and Komlós
János Komlós (mathematician)
János Komlós is a Hungarian-American mathematician, working in probability theory and discrete mathematics. He is a professor of mathematics at Rutgers University since 1988. He graduated from the Eötvös Loránd University, then became a fellow at the Mathematical Institute of the Hungarian Academy...
he proved the ct2/log t upper bound for the Ramsey number R(3,t). With Ajtai
Miklós Ajtai
Miklós Ajtai is a computer scientist at the IBM Almaden Research Center. In 2003 he received the Knuth Prize for his numerous contributions to the field, including a classic sorting network algorithm Miklós Ajtai (born 2 July 1946, Budapest, Hungary) is a computer scientist at the IBM Almaden...
, Chvátal
Václav Chvátal
Václav Chvátal is a professor in the Department of Computer Science and Software Engineering at Concordia University in Montreal, Canada, where he holds theCanada Research Chair in Combinatorial Optimization....
, and M. M. Newborn, Szemerédi proved the famous Crossing Lemma, that a graph
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
with n vertices and m edges, where has at least crossings.
Awards and Honors
Szemeredi has won numerous awards and honors for his contribution to mathematics and computer science. A few of them are listed here:- Grünwald Prize (1967)
- Grünwald Prize (1968)
- Rényi PrizeAlfréd Rényi PrizeThe Alfréd Rényi Prize is awarded biannually by the Alfréd Rényi Institute of Mathematics of the Hungarian Academy of Science in honor of founder Alfréd Rényi. By the current rules it is given to one or two fellows of the Institute in recognition of their outstanding performance in mathematics...
(1973) - Pólya Prize for Achievement in Applied Mathematics (SIAM) (1975)
- Prize of the Hungarian Academy of Sciences (1979)
- State of New Jersey Professorship (1986)
- The AMS Leroy P. Steele Prize for Seminal Contribution to Research, (2008)
- The Rolf Schock Prize in Mathematics for deep and pioneering work from 1975 on arithmetic progressions in subsets of the integers, (2008)
Endre Szemeredi is a corresponding member (1982), and member (1987) of the Hungarian Academy of Sciences
Hungarian Academy of Sciences
The Hungarian Academy of Sciences is the most important and prestigious learned society of Hungary. Its seat is at the bank of the Danube in Budapest.-History:...
and a member (2010) of the National Academy of Sciences
United States National Academy of Sciences
The National Academy of Sciences is a corporation in the United States whose members serve pro bono as "advisers to the nation on science, engineering, and medicine." As a national academy, new members of the organization are elected annually by current members, based on their distinguished and...
. He is also a member of the Institute for Advanced Study
Institute for Advanced Study
The Institute for Advanced Study, located in Princeton, New Jersey, United States, is an independent postgraduate center for theoretical research and intellectual inquiry. It was founded in 1930 by Abraham Flexner...
(IAS), Princeton University (2007–2010) and a permanent research fellow at the Rényi Institute of Mathematics, Budapest.
He was the Fairchild Distinguished Scholar at CALTECH in 1987-88.
Prof. Szemeredi is an honorary doctor of the Charles University, Prague.
He was the lecturer in the Forty-Seventh Annual DeLong Lecture Series at University of Colorado.
He is also a recipient of the Aisenstadt Chair at CRM, University of Montreal. In 2008 he was the Eisenbud Professor at MSRI Berkeley.
70th Birthday Conference
On August 2–7, 2010, the Alfréd Rényi Institute of Mathematics and the János Bolyai Mathematical Society organized a conference in honor of 70th birthday of Endre Szemeredi.Prior to the conference a volume of the Bolyai Society Mathematical Studies Series, An Irregular Mind, a collection of papers edited by Imre Bárány
Imre Bárány
Imre Bárány is a Hungarian mathematician, working in combinatorics and discrete geometry. He works at the Rényi Mathematical Institute of the Hungarian Academy of Sciences, and has a part-time job at the University College London....
and József Solymosi, was published to celebrate Szemerédi's achievements on the occasion of his 70th birthday.
External links
- Personal Homepage at the Alfréd Rényi Institute of MathematicsAlfréd Rényi Institute of MathematicsThe Alfréd Rényi Institute of Mathematics is the research institute in mathematics of the Hungarian Academy of Sciences. It was created in 1950 by Alfréd Rényi, who directed it until his death. Since its creation, the institute has been the center of mathematical research in Hungary. It received...