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).


Based on work by