Ramsey-tétel

• IPA:

Ramsey-tétel

1. (matematika, kombinatorika) Ha ${\displaystyle r,k_{1},\dots ,k_{s}}$ pozitív egész számok, akkor van olyan (legkisebb) ${\displaystyle R_{r}(k_{1},\dots ,k_{s})}$ pozitív egész szám, hogy igaz a következő állítás: ha tetszőleges S halmazra ${\displaystyle |S|=R_{r}(k_{1},\dots ,k_{s})}$ és S összes r elemű részhalmazának halmazát s részre bontjuk (s színnel színezzük) akkor valamelyik i-re igaz, hogy van az alaphalmaznak olyan ${\displaystyle k_{i}}$-elemű részhalmaza, aminek összes r elemű részhalmaza az i-edik osztályba esik (i-edik színt kapja).

A Ramsey-tétel a kombinatorika és a gráfelmélet egyik alapvető tétele, amely kimondja, hogy a teljes káosz sem létezik: egy elég nagy struktúrában mindig megfigyelhető bizonyos rendezettség. A tétel általános formában az alábbiakat mondja ki:

1. Két színnel (${\displaystyle r=2}$):

  Ha ${\displaystyle n}$ elég nagy, akkor a ${\displaystyle K_{n}}$ teljes gráf éleinek ${\displaystyle 2}$ színnel történő színezésénél mindig létezik egy ${\displaystyle K_{k}}$ teljes részgrafikon, amelynek minden éle ugyanazzal a színnel van színezve.

1. Ramsey-számok (${\displaystyle R(k_{1},k_{2},\dots ,k_{r})}$):

  Az ${\displaystyle R(k_{1},k_{2},\dots ,k_{r})}$ Ramsey-szám a legkisebb olyan ${\displaystyle n}$, amelyre teljesül, hogy a ${\displaystyle K_{n}}$ gráf ${\displaystyle r}$-féle színnel történő élszínezésénél biztosan található egy ${\displaystyle K_{k_{i}}}$ teljes részgrafikon, amelynek minden éle ugyanazzal a színnel van színezve (legalább egy ${\displaystyle i}$-re).

Ha ${\displaystyle n=6}$, akkor bármely ${\displaystyle K_{6}}$ teljes gráf éleinek két színnel történő színezésénél mindig található egy ${\displaystyle K_{3}}$ (három csúcsú teljes gráf), amelynek minden éle azonos színű. Ez azt jelenti, hogy ${\displaystyle R(3,3)=6}$.

Legyen a ${\displaystyle K_{n}}$ teljes gráf élei piros és kék színnel színezve.

1. Válasszunk egy ${\displaystyle v}$ csúcsot a ${\displaystyle K_{n}}$-ből.
2. Tekintsük a ${\displaystyle v}$-ből kiinduló éleket:

  - Ha ${\displaystyle v}$-ből ${\displaystyle k}$-nál több él van egyetlen színnel, akkor a kapcsolódó csúcsok között biztosan található egy ${\displaystyle K_{k}}$ ugyanazzal a színnel.

1. Ha nincs ilyen, akkor a ${\displaystyle n}$-hez viszonyított ${\displaystyle k}$ csúcs között létezik egy homogén ${\displaystyle K_{k}}$ részgrafikon.

Ez a gondolatmenet általánosítható nagyobb ${\displaystyle k}$ és több szín esetére.

A bizonyítás erős indukcióval történik.

1. Alapindukció (${\displaystyle k=2}$):

  Ekkor az ${\displaystyle R(2,2,\dots ,2)=2}$ triválisan teljesül.

1. Indukciós lépés:

  Tegyük fel, hogy a tétel igaz ${\displaystyle k-1}$-re. Bizonyítsuk be ${\displaystyle k}$-ra.
  ## Válasszunk egy ${\displaystyle n}$-et elég nagynak, hogy ${\displaystyle R(k-1,k-1,\dots ,k-1)}$ teljesüljön.
  ## Ha egy adott csúcsból kiinduló éleket ${\displaystyle r}$-féle színnel színezzük, akkor bármely színből található egy homogén ${\displaystyle K_{k-1}}$ részgrafikon, amely tovább bővíthető ${\displaystyle k}$-ra.

Ez garantálja, hogy ${\displaystyle R(k,k,\dots ,k)}$ is igaz.

1. ${\displaystyle R(3,3)=6}$: Hat csúcsú gráfban két színnel színezve biztosan található egy három csúcsú homogén részgrafikon.
2. ${\displaystyle R(4,4)=18}$: Legalább 18 csúcsú gráf szükséges, hogy két színnel színezve biztosan találjunk egy négy csúcsú homogén részgrafikont.

1. ${\displaystyle R(k,k)\leq 4^{k/2}}$: Az upper bound exponenciális.
2. Az alsó korlát sokkal kisebb, és a pontos értékek meghatározása általában nehéz.

1. Kombinatorika:

  - Nagyméretű gráfok szerkezetének elemzése.

1. Számítástechnika:

  - Hálózati kapcsolatok és konfigurációk optimalizálása.

1. Matematikai logika:

  - Rendezettség és struktúrák elemzése.

A Ramsey-tétel a kombinatorika egyik legfontosabb eredménye, amely garantálja, hogy elég nagy struktúrákban mindig van bizonyos rendezettség. A tétel mély matematikai és gyakorlati jelentőséggel bír a gráfelméletben, a számítástechnikában és a matematikai logikában.

• angol: Ramsey's theorem (en)
• orosz: теорема Рамсея (ru) (teorema Ramseja)

• Ramsey-tétel - Értelmező szótár (MEK)
• Ramsey-tétel - Etimológiai szótár (UMIL)
• Ramsey-tétel - Szótár.net (hu-hu)
• Ramsey-tétel - DeepL (hu-de)
• Ramsey-tétel - Яндекс (hu-ru)
• Ramsey-tétel - Google (hu-en)
• Ramsey-tétel - Helyesírási szótár (MTA)
• Ramsey-tétel - Wikidata
• Ramsey-tétel - Wikipédia (magyar)