Főmenü megnyitása

Ajtai Miklós (matematikus)

magyar származású amerikai matematikus, az MTA külső tagja

Ajtai Miklós (Budapest, 1946. július 2. –) magyar származású amerikai matematikus, a Magyar Tudományos Akadémia külső tagja. Ajtai Miklós politikus és Jóború Magda könyvtári főigazgató fia.

Ajtai Miklós
Született 1946. július 2. (73 éves)
Budapest
Állampolgársága magyar
SzüleiAjtai Miklós
Foglalkozása matematikus
Kitüntetései Knuth Prize (2003)

Tartalomjegyzék

Kutatási területeSzerkesztés

Matematikai logikával, számítógéptudománnyal, kombinatorikával foglalkozik.

EredményeiSzerkesztés

  • Belátta, hogy az az állítás, hogy két másodrendben elemien ekvivalens struktúra izomorf is, független a halmazelmélet szokásos axiómáitól.
  • Megmutatta, hogy a skatulyaelvnek nincs polinomiális hosszúságú bizonyítása.
  • Igazolta, hogy egy   hosszúságú 0-1 sorozatban található egyesek számának paritása nem dönthető el korlátos mélységű és  -ben polinomiális méretű hálózattal.
  • Komlós Jánossal és Szemerédi Endrével bebizonyította az   Ramsey-számokokra a   felső becslést.
  • Szintén Komlós Jánossal és Szemerédi Endrével igazolta, hogy egy   pontot és   élt tartalmazó véletlen gráf majdnem biztosan tartalmaz egy   hosszú utat, ahol   értéke  -tól függ ( ).

Az IBM almadeni kutatóintézetének munkatársa.

ElismeréseiSzerkesztés

Kapcsolódó szócikkekSzerkesztés