Szemerédi Endre

A Wikipédiából, a szabad lexikonból.

Szemerédi Endre (Budapest, 1940. augusztus 21.) magyar matematikus, Erdős Pál és Hajnal András tanítványa.

Kombinatorikai, számelméleti és számítógéptudományi kutatásokat végez. Jelenleg a Rutgers Egyetem számítógéptudományi tanszékének kutatóprofesszora.


[szerkesztés] Fontosabb eredményei

  • Nevezetes, nagy port felvert eredménye Erdős és Turán sejtésének bizonyítása: minden pozitív felső sűrűségű sorozat tartalmaz tetszőleges hosszú számtani sorozatot. Ehhez fogalmazta meg és igazolta a regularitási lemmát, ami fontos eszközzé vált a nagy gráfok kutatásában.
  • A. D. Korsunov és Pósa Lajos eredményét megjavítva, Komlós Jánossal igazolja, hogy ha egy G véletlen gráf n szögponttal és
\frac12n\log n+\frac12n\log\log n+cn
éllel, akkor e^{e^{-2c}}-hez tartó valószínűséggel tartalmaz Hamilton-kört.
  • Hajnal Andrással bebizonyította Erdős sejtését: ha egy véges gráfban minden pont foka kisebb k-nál, akkor a gráf egyenletesen kiszínezhető k színnel, azaz úgy, hogy a színosztályok mérete legfeljebb 1-gyel tér el egymástól.
  • W. T. Trotterrel igazolta Erdős Pál egy sejtését, eszerint m pont és n egyenes között a síkban legfeljebb O(m2 / 3n2 / 3 + m + n) illeszkedés lehet.
  • Ruzsa Imrével igazolta azt a meghökkentő tényt, hogy ha f(n) jelöli az n ponton kiválasztható 3-elemű részhalmazok maximális számát amire nincs hat pont, ami 3 kiválasztott halmazt tartalmaz, akkor
n^{2-\varepsilon}<f(n)=o(n^2).
  • Ajtai Miklóssal és Komlós Jánossal bebizonyította a R(3,n) = O(n2 / logn)Ramsey-számokra vonatkozó becslést.

[szerkesztés] Díjai

Akadémiai Díj (1979). A Magyar Tudományos Akadémia levelező (1982), rendes (1987) tagja.


Más nyelveken