Ajtai Miklós (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

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

Eredményei

• 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 skatulyaelv-nek nincs polinomiális hosszúságú bizonyítása.
• Igazolta, hogy egy $n$ hosszúságú 0-1 sorozatban található egyesek számának paritása nem dönthető el korlátos mélységű és $n$-ben polinomiális méretű hálózattal.

• Komlós Jánossal és Szemerédi Endrével bebizonyította az $R(3,n)$ Ramsey-számokra a $cn^2/\log n$ felső becslést.
• Szintén Komlós Jánossal és Szemerédi Endrével igazolta, hogy egy $n$ pontot és $an$ élt tartalmazó véletlen gráf majdnem biztosan tartalmaz egy $cn$ hosszú utat, ahol $c$ értéke $a$-tól függ ($a>1/2$).

Az IBM almadeni kutatóintézetének munkatársa. Az MTA külső tagja (1995). Knuth-díj (2003).

Lásd még

• Magyar akadémikusok listája