Ajtai Miklós (matematikus)

A Wikipédiából, a szabad enciklopédiából
Ajtai Miklós
Született 1946. július 2. (67 éves)
Budapest
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 | forrásszöveg szerkesztése]

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

Eredményei[szerkesztés | forrásszöveg szerkesztése]

  • 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[szerkesztés | forrásszöveg szerkesztése]