„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|F.Frank P. Ramsey]] brit matematikus-filozófus-közgazdász, a [[kombinatorika]], de tulajdonképpen a [[matematika]] egészének fontos tétele.
 
== 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 a vizsgálata hamar számításigényessé válik, ahogy ''n'' értéke növekszik; a színezések száma [[exponenciális]]nál gyorsabban növekszik.
 
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 ''R''(1,''b'') = 1 és ''R''(2,''b'') = ''b'' képletek minden ''b''-re. A Ramsey-számok kutatását [[Stanisław Radziszowski]] tekintette át, aki [[Brendan McKay]]-jel együtt kiszámította az R(4,5) pontos értékét.
 
{| 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 ismeretlen, csak azt tudjuk róla, hogy 43 (Geoffrey Exoo) és 49
([[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ű háromszög.
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. TegyükfelTegyük fel, hogy tudjuk az állítást ''r''-re és adott <math>K_{f(r+1)+1}</math> éleinek egy ''r''+1 színnel való színezése. Legyen ''p'' a gráf egy csúcsa, <math>A_1,\dots,A_{r+1}</math> sorra azon további pontok halmaza, amelyek ''p''-be az első, második, …, ''r''+1-edik színben vannak bekötve. Nyilván <math>|A_1|+\cdots+|A_{r+1}|=f(r+1)=(r+1)f(r)+1</math>, ezért van olyan <math>i</math>,
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 színezzük, az indukció miatt van tehát egyszínű háromszög.
 
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''- elemű [[részhalmaz]]ainak halmazát ''s'' részre bontja (''s'' színnel színezi), akkor van olyan végtelen részhalmaz, aminek minden részhalmaza ugyanabba a részbe esik (ugyanazt a színt kapja).
 
<!--== 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 elsőszínűelső színű <math>K_k</math> vagy egy második színű <math>K_l</math>.
 
=== Bizonyítás ===
236. sor:
 
== Becslések r(k,l)-re ==
=== FelsőbecslésFelső becslés ===
<math>r(k,l) \leq \binom {k+l-2}{k-1} </math>
 
249. sor:
== Forrás ==
* {{cite book
| author = Katona Gyula Y, Recski András, Szabó Csaba
| authorlink =
| title = A számítástudomány alapjai
| publisher = Typotex Kiadó
| year = 2001
| id = ISBN 963-9326-68-2
| url =
}}
* [http://en.wikipedia.org/wiki/Ramsey-type_theorem Ramsey-type theorem]