„Ramsey-tétel” változatai közötti eltérés
| [ellenőrzött változat] | [ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
a j |
Nincs szerkesztési összefoglaló |
||
82. sor:
|
|-
! 4
| 1
| 4
181. sor:
<center><math>2^{\frac{n}{2}}<R_2(n,n).</math></center>
Egy hosszú ideig érintetlen Erdős-kérdés volt, hogy lehet-e <math>R_2(n,n)</math>-re a triviális <math>(n-1)^2+1</math>-nél lényegesen jobb ''konstruktív'' alsó becslést adni. Erre először Nagy Zsigmond egy <math>n^3</math>-ös, majd Frankl Péter és Wilson egy <math>n^{c\log n}</math>-es [[Frankl–Wilson-tétel|
Erdős egyik nevezetes sejtése, hogy van olyan ''c'' szám, hogy minden <math>\varepsilon>0</math> -ra elég nagy ''n'' esetén
215. sor:
== Ramsey-típusú tételek ==
== Tétel ==
Minden 6 pontú gráfban van egy teljes 3-as vagy egy teljes üres 3-as, azaz
=== Bizonyítás ===
Válasszunk ki egy tetszőleges pontot, <math>{v_1}</math>-et. Ezen kívül még 5 pontunk van, ezekből vagy van 3 olyan pont, amibe vezet él <math>v_1</math>-ből, vagy van 3 olyan pont, amibe nem vezet él <math>v_1</math>-ből. Az első esetben legyenek <math>v_1</math> szomszédai <math>v_2</math>, <math>v_3</math>, <math>v_4</math>. Ha ezek között fut él, például <math>\{v_2, v_3\} \in E(G)</math>, akkor <math>v_1</math>, <math>v_2</math>, <math>v_3</math> egy teljes 3-ast ad, azonban ha nem fut köztük él, akkor <math>v_2</math>, <math>v_3</math>, <math>v_4</math> egy teljes üres hármas. A második esetben is ugyanígy következik az állítás.
| |||