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
Szülei Ajtai Miklós
Foglalkozása matematikus

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]