Endre Szemerédi

Endre Szemerédi [ ɛndrɛ sɛmɛre ː di] ( born August 21, 1940 in Budapest) is a Hungarian mathematician employed, which deals with combinatorics (graph theory ), computer science and number theory.

Education and Career

Szemerédi studied ( after he initially studied medicine and worked in a factory of one year - his mathematical talent was recognized by Paul Erdős ) Mathematics at the University of Budapest ( Diploma at the Eotvos Lorand University, 1965) András Hajnal and Paul Erdős and was in 1970 at the Lomonosov University in Moscow in Israel Gelfand PhD (specifically candidate status, equivalent to a dissertation in the West). He is since 1965 the Alfréd Rényi Institute of the Hungarian Academy of Sciences since 1990 and a professor of computer science at Rutgers University (New Jersey Professor of Computer Science). He was a guest scientist and visiting professor at Stanford University ( 1974), at McGill University ( 1980), the University of South Carolina ( 1981-1983), the University of Chicago ( 1985-1986), the Institute for Advanced Study, the University of Montreal ( Aisenstadt Chair ), the MSRI ( Professor Eisenbud 2008) and at Caltech ( Fairchild Scholar 1987/88 ).

Work

Szemerédi proved in 1975 the old (1936 ) conjecture of Pál Turán and Paul Erdős that a sequence of natural numbers, the positive density in the natural numbers, has arbitrarily long arithmetic progressions contains ( set of Szemerédi ). The regularity lemma used in the proof of Szemerédi found applications in complexity theory, the theory of random graphs, and number theory. It says roughly that large dense graphs can be approximated as a union of a limited amount of " regular " graph of about the same size. The evidence led to advances in Ramsey theory ( Ramsey - sentences from the Szemerédi - type) and in ergodic theory ( by Hillel Furstenberg, Yitzhak Katznelson ).

In 1977, Fürstenberg an alternative proof for the set of Szemerédi with methods of ergodic theory, and in 2001 was Timothy Gowers further evidence, in which the Fourier analysis was used in addition to the combinatorics. Terence Tao and Ben Green in 2004 were even the existence of arithmetic progressions of arbitrary length in the prime numbers ( which do not have positive density ) show, where she further developed Szemerédis methods.

From Szemerédi and his teacher András Hajnal the set of Szemerédi - Hajnal on graph coloring (1970 ), who had been suspected of Erdős comes.

He has published over 200 scientific papers ( 2011).

Rates and Memberships

Szemerédi is since 1987 a full member of the Hungarian Academy of Sciences (since 1982 corresponding member ). In 2010 he became a member of the National Academy of Sciences. In 2010 he was made an honorary Doctor of Charles University in Prague.