„Ajtai Miklós (matematikus)” változatai közötti eltérés

{{egyért2|a matematikusról|Ajtai Miklós (egyértelműsítő lap)}}

 

}}

'''Ajtai Miklós''' ([[Budapest]], [[1946]]. [[július 2.]] –) magyar származású [[Amerikai Egyesült Államok|amerikai]] [[matematikus]], a [[Magyar Tudományos Akadémia]] külső tagja. [[Ajtai Miklós (politikus)|Ajtai Miklós]] politikus és [[Jóború Magda]] könyvtári főigazgató fia.

==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 <math>n</math> hosszúságú 0-1 sorozatban található egyesek számának paritása nem dönthető el korlátos mélységű és <math>n</math>-ben polinomiális méretű hálózattal.

* [[Komlós János (matematikus)|Komlós János]]sal és [[Szemerédi Endre|Szemerédi Endrével]] bebizonyította az <math>R(3,n)</math> [[Ramsey-tétel#A tétel véges formája|Ramsey-számok]]okra a <math>cn^2/\log n</math> felső becslést.

* Szintén Komlós Jánossal és Szemerédi Endrével igazolta, hogy egy <math>n</math> pontot és <math>an</math> élt tartalmazó véletlen gráf majdnem biztosan tartalmaz egy <math>cn</math> hosszú utat, ahol <math>c</math> értéke <math>a</math>-tól függ (<math>a>1/2</math>).