„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
Nincs szerkesztési összefoglaló |
Nincs szerkesztési összefoglaló |
||
1. sor:
'''Ramsey tétele''', melynek névadója [[Frank Plumpton Ramsey|
== A tétel véges formája ==
30. sor:
=== Ramsey-számok ===
A Ramsey-tételben (és több színre való kiterjesztéseiben) szereplő ''R''(''a'',''b'') számokat ''Ramsey-számok''nak nevezik. A tétel bizonyításából adódik egy felső korlát ''R''(''a'',''b'') számokra, alsó korlátok pedig máshonnan. Azonban a legjobb alsó korlátok és a legjobb felső korlátok között elég nagy űr tátong. Következésképpen, nagyon kevés ''a'' és ''b'' számra ismerjük ''R''(''a'',''b'') pontos értékét. Az ''L'' alsó korlát kiszámítása ''R''(''a'',''b'')-re általában a ''K''<sub>''L''‒1</sub> olyan kék-piros színezéséből áll, ami nem tartalmaz kék ''K<sub>a</sub>'' részgráfot, sem piros ''K''<sub>''b''</sub> részgráfot. Egy ''K<sub>n</sub>'' gráf összes lehetséges kiszínezésének
Az ''R''(''a'',''b'') értékei 11-nél kisebb ''a'' és ''b''-kre megtalálhatók a lenti táblázatban. Ahol a pontos érték ismeretlen, az eddigi legjobb alsó és felső korlátokat adjuk meg. ''R''(''a'',''b'') értékét, ahol akár ''a'' vagy ''b'' 3-nál kisebb, megadják az
{| class="wikitable"
172. sor:
A táblázat kivonat [[Stanisław Radziszowski]] részletesebb táblázatából [http://www.combinatorics.org/Surveys/index.html].
Az ''R''(''a'',''a'') átlós Ramsey-számok meghatározása a kombinatorika egyik legnehezebb problémája. Ismert, hogy ''R''(3,3)=6 és ''R''(4,4)=18. De ''R''(5,5) pontos értéke már
([[Brendan McKay]] és [[Stanisław Radziszowski]]) között található; hacsak nem találunk az összes eset szisztematikus végigvizsgálásánál lényegesen hatékonyabb eljárást, valószínű, hogy az ''R''(6,6) pontos értéke örökre ismeretlen marad számunkra.
193. sor:
=== ''R''<sub>2</sub>(3,3,…,3) esete ===
Szavakban ez tehát azt mondja ki, hogy ha egy <math>R_2(3,3,\dots,3)</math> (''s'' darab 3) szögpontú teljes gráf éleit ''s'' színnel színezzük, akkor van egyszínű
Bebizonyítjuk az <math>R(3)\leq 3, R(3,3)\leq 6, R(3,3,3)\leq 17</math> és általában az <math>R(3,3,\dots,3)\leq [er!]+1</math> becslést (az első három esetben egyenlőség van). Ehhez definiáljuk az ''f'' függvényt az <math>f(1)=2</math>, <math>f(r+1)=(r+1)f(r)+1</math> rekurzióval. ''r''-re való indukcióval bebizonyítjuk, hogy ha <math>K_{f(r)+1}</math> éleit ''r'' színnel színezzük, van egyszínű háromszög. Ez ''r''=1-re nyilván igaz.
hogy <math>|A_i|\geq f(r)+1</math>. Ha <math>A_i</math> pontjai között szerepelne az ''i''-edik szín, akkor van az ''i'' színben háromszög. Ha nem, <math>A_i</math> párjait ''r'' színnel
Végül jegyezzük meg, hogy indukcióval adódik <center><math>f(r)=r!\left(1+\frac{1}{1!}+\frac{1}{2!}+\cdots+\frac{1}{r!}\right)=[er!].
</math></center>
A tétel érdekes alkalmazása [[Issai Schur]] [[Issai Schur tétele (kombinatorikus számelmélet)|tétele]].
=== ''r''=2, tetszőleges ''s'' esete ===
210. sor:
== A tétel végtelen formája ==
:Ha ''s'', ''r'' pozitív egész számok és ''f'' a természetes számok összes ''r''
<!--== A végtelen alakból következik a véges ==-->
223. sor:
== Tétel (Ramsey) ==
Adott k, l pozitív egészekhez létezik egy olyan legkisebb <math>r(k,l)</math> szám, hogy <math>n \geq r(k,l)</math> esetén az <math>n</math> pontú [[teljes gráf]], <math>K_n</math> éleit két színnel kiszínezve van a gráfban egy
=== Bizonyítás ===
236. sor:
== Becslések r(k,l)-re ==
===
<math>r(k,l) \leq \binom {k+l-2}{k-1} </math>
249. sor:
== Forrás ==
* {{cite book
}}
* [http://en.wikipedia.org/wiki/Ramsey-type_theorem Ramsey-type theorem]
|