Ajtai Miklós (matematikus)

A Wikipédiából, a szabad enciklopédiából
Ajtai Miklós
Született 1946. július 2. (70 éves)
Budapest
Állampolgársága Magyarország
Szülei Ajtai Miklós
Foglalkozása matematikus
Díjak Knuth Prize (2003)

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 (1914–1982) politikus fia.

Kutatási területe[szerkesztés]

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

Eredményei[szerkeszté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ámokra 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. Az MTA külső tagja (1995). Knuth-díj (2003).

Kapcsolódó szócikkek[szerkesztés]