Ajtai Miklós (matematikus)

A Wikipédiából, a szabad lexikonból.

Ez a szócikk a matematikus Ajtai Miklósról szól. További jelentéséhez lásd: Ajtai Miklós (politikus).

Ajtai Miklós (Budapest, 1946. július 2.) magyar származású amerikai matematikus, az MTA külső tagja, Ajtai Miklós (politikus) fia.

[szerkesztés] Kutatási területe

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

[szerkesztés] 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 cn2 / logn 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).

[szerkesztés] Lásd még