Endre Szemerédi: Difference between revisions
→Work: the mathematicians Wolfgang Paul and William Trotter do not currently have Wikipedia pages (but other people with these names do) |
|||
| Line 21: | Line 21: | ||
the [[Szemerédi regularity lemma]], which has become a very important tool in [[combinatorics]], being used for instance in [[property testing]] for graphs and in the theory of [[graph limit]]s. |
the [[Szemerédi regularity lemma]], which has become a very important tool in [[combinatorics]], being used for instance in [[property testing]] for graphs and in the theory of [[graph limit]]s. |
||
He is also known for the [[Szemerédi-Trotter theorem]] in [[Incidence geometry (structure)|incidence geometry]] and the [[Hajnal-Szemerédi theorem]] in [[graph theory]]. [[Miklós Ajtai|Ajtai]] and Szemerédi proved the [[corners theorem]], an important step toward higher dimensional generalizations of the [[Szemerédi's theorem|Szemerédi theorem]]. With [[Miklós Ajtai|Ajtai]] and [[János Komlós (mathematician)|Komlós]] he proved the ''ct''<sup>2</sup>/log ''t'' upper bound for the [[Ramsey number]] ''R''(3,''t''), and constructed a [[sorting network]] of optimal depth. With [[Miklós Ajtai|Ajtai]], [[Václav Chvátal|Chvátal]], and M. M. Newborn, Szemerédi proved the famous Crossing Lemma, that a [[Graph (mathematics)|graph]] with ''n'' vertices and ''m'' edges, where {{nowrap|''m'' > 4''n''}} has at least {{nowrap|''m''<sup>3</sup> / 64''n''<sup>2</sup>}} [[Crossing number (graph theory)#The crossing number inequality|crossings]]. With [[Paul Erdős]], he proved the [[Erdős-Szemerédi theorem]] on the number of sums and products in a finite set. With |
He is also known for the [[Szemerédi-Trotter theorem]] in [[Incidence geometry (structure)|incidence geometry]] and the [[Hajnal-Szemerédi theorem]] in [[graph theory]]. [[Miklós Ajtai|Ajtai]] and Szemerédi proved the [[corners theorem]], an important step toward higher dimensional generalizations of the [[Szemerédi's theorem|Szemerédi theorem]]. With [[Miklós Ajtai|Ajtai]] and [[János Komlós (mathematician)|Komlós]] he proved the ''ct''<sup>2</sup>/log ''t'' upper bound for the [[Ramsey number]] ''R''(3,''t''), and constructed a [[sorting network]] of optimal depth. With [[Miklós Ajtai|Ajtai]], [[Václav Chvátal|Chvátal]], and M. M. Newborn, Szemerédi proved the famous Crossing Lemma, that a [[Graph (mathematics)|graph]] with ''n'' vertices and ''m'' edges, where {{nowrap|''m'' > 4''n''}} has at least {{nowrap|''m''<sup>3</sup> / 64''n''<sup>2</sup>}} [[Crossing number (graph theory)#The crossing number inequality|crossings]]. With [[Paul Erdős]], he proved the [[Erdős-Szemerédi theorem]] on the number of sums and products in a finite set. With Wolfgang Paul, [[Nick Pippenger]], and William Trotter, he established a separation between [[Non-deterministic_Turing_machine|nondeterministic]] [[linear time]] and [[Deterministic_computation|deterministic]] linear time, in the spirit of the infamous [[P versus NP problem]]. With William Trotter, he established the [[Szemerédi–Trotter theorem]] obtaining an optimal bound on the number of incidences between finite collections of points and lines in the plane. |
||
==Awards and Honors== |
==Awards and Honors== |
||
Revision as of 18:59, 16 March 2012
Endre Szemerédi | |
|---|---|
 Endre Szemerédi | |
| Born | August 21, 1940 |
| Nationality |  Hungary |
| Alma mater | Moscow State University |
| Awards | Pólya Prize (1975) Rolf Schock Prizes (2008) Leroy P. Steele Prize (2008) Alfréd Rényi Prize (1973) Member NAS |
| Scientific career | |
| Fields | Computer science |
| Institutions | Rutgers University |
| Doctoral advisor | Israil Moiseivich Gelfand |
| Doctoral students | Jaikumar Radhakrishnan Ali Shokoufandeh Ryan Martin Sachin Lodha Gabor Sarkozy Bela Csaba Ayman Khalfallah Sarmad Abbasi |
Endre Szemerédi (born August 21, 1940) 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.[1]
Work
Endre Szemerédi has published over 200 scientific articles in the fields of Discrete Mathematics, Theoretical Computer Science, Arithmetic Combinatorics and Discrete Geometry.[2] He is best known for his proof from 1975 of an old conjecture of Paul Erdős and Paul Turán: if a sequence of natural numbers has positive upper density then it contains arbitrarily long arithmetic progressions. 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, being used for instance in property testing for graphs and in the theory of graph limits.
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), and constructed a sorting network of optimal depth. 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 m > 4n has at least m3 / 64n2 crossings. With Paul Erdős, he proved the Erdős-Szemerédi theorem on the number of sums and products in a finite set. With Wolfgang Paul, Nick Pippenger, and William Trotter, he established a separation between nondeterministic linear time and deterministic linear time, in the spirit of the infamous P versus NP problem. With William Trotter, he established the Szemerédi–Trotter theorem obtaining an optimal bound on the number of incidences between finite collections of points and lines in the plane.
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 Prize (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) [3]
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 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[4] of the Charles University, Prague.
He was the lecturer in the Forty-Seventh Annual DeLong Lecture Series [5] at University of Colorado.
He is also a recipient of the Aisenstadt Chair at CRM,[6] 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.[7]
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.[8][9]
References
- ^ Endre Szemerédi at the Mathematics Genealogy Project
- ^ Some Publications at mathscienet
- ^ Major US Maths Prize Given to HAS Full Member, Hungarian Academy of Sciences, January 9, 2008.
- ^ Doctor honoris causa Endre Szemerédi, June 15–16, 2010.
- ^ DeLong Lecture Series
- ^ Aisenstadt Chair Recipients
- ^ Szemerédi is 70
- ^ Springer:An Irregular Mind
- ^ Amazon:An Irregular Mind
External links
- 1940 births
- Living people
- Rolf Schock Prize laureates
- Rutgers University faculty
- 20th-century mathematicians
- 21st-century mathematicians
- Combinatorialists
- Theoretical computer scientists
- Hungarian mathematicians
- Hungarian computer scientists
- Members of the Hungarian Academy of Sciences
- Hungarian emigrants to the United States
- Members of the United States National Academy of Sciences