„Ajtai Miklós (matematikus)” változatai közötti eltérés
| [nem ellenőrzött változat] | [nem ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
aNincs szerkesztési összefoglaló |
a Zárójelhez tapadó külsö szöveghez szóköz |
||
12. sor:
* 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-számokra 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>).
| |||