Balazsil

Ramsey-típusú tételek

Tétel

Minden 6 pontú gráfban van egy teljes 3-as vagy egy teljes üres 3-as, azaz vagy van 3 olyan pont, hogy bármely 2 között fut él, vagy van 3 olyan pont, hogy közöttük nem fut él.

Bizonyítás

Válasszunk ki egy tetszőleges pontot, ${v_{1}}$-et. Ezen kívül még 5 pontunk van, ezekből vagy van 3 olyan pont, amibe vezet él $v_{1}$-ből, vagy van 3 olyan pont, amibe nem vezet él $v_{1}$-ből. Az első esetben legyenek $v_{1}$ szomszédai $v_{2}$, $v_{3}$, $v_{4}$. Ha ezek között fut él, például $\{v_{2},v_{3}\}\in E(G)$, akkor $v_{1}$, $v_{2}$, $v_{3}$ egy teljes 3-ast ad, azonban ha nem fut köztük él, akkor $v_{2}$, $v_{3}$, $v_{4}$ egy teljes üres hármas. A második esetben is ugyanígy következik az állítás.

Tétel(Ramsey)

Adott k, l pozitív egészekhez létezik egy olyan legkisebb $r(k,l)$ szám, hogy $n\geq r(k,l)$ esetén az $n$ pontú teljes gráf, $K_{n}$ éleit két színnel kiszínezve van a gráfban egy elsőszínű $K_{k}$ vagy egy második színű $K_{l}$.

Bizonyítás

A következő tétel bizonyításával együtt látjuk be ennek a tételnek a bizonyítását is.

Tétel(Erdős-Szekeres)

$r(k,l)\leq r(k-1,l)+r(k,l-1)$

Bizonyítás

Bizonyítsunk indukcióval. Nyilvánvaló, hogy létezik $r(k,2)$ és $r(2,l)$, és világos, hogy $r(k,2)=k$ és $r(2,l)=l$. Tegyük most fel, hogy létezik minden $r(t,s)$, ahol vagy $t\leq k$ és $s<l$ vagy $t<k$ és $s\leq l$. Valamint indirekt tegyünk fel, hogy $n\geq r(k-1,l)+r(k,l-1)$, és $K_{n}$ élei megszínezhetők két színnel úgy, hogy a gráfban nincs sem első színű (kék) $K_{k}$, sem második színű (piros) $K_{l}$. Válasszuk ki $K_{n}$ egy tetszőleges pontját, $v_{1}$-et. Legyenek $v_{1}$-ből kiinduló kék élek végpontjai $k_{1},k_{2},\dots ,k_{u}$, a pirosaké pedig $p_{1},p_{2},\dots ,p_{v}$. Ha $u$ nagyobb lenne $r(k-1,l)-1$-nél, akkor a $k_{i}$ pontok között a feltevés miatt volna vagy egy piros $K_{l}$, vagy egy kék $K_{(}k-1)$, és az utóbbi esetben ehhez hozzávéve $v_{1}$-et kék $K_{k}$-t kapnánk. Tehát a feltevésekből következik, hogy $u\leq r(k-1,l)-1$. Ugyanígy kapjuk, hogy $v\leq r(k,l-1)-1$. Ekkor viszont $n=u+v+1\leq r(k-1,l)+r(k,l-1)-2+1$, ami viszont ellentmondás. Tehát azt láttuk be, hogy $r(k-1,l)+r(k,l-1)$ olyan szám, hogy minden nála nem kisebb $n$-re $K_{n}$-et színezve lesz a gráfban kék $K_{k}$, vagy piros $K_{l}$. Ekkor viszont a legkisebb ilyen szám kisebb vagy egyenlő $r(k-1,l)+r(k,l-1)-1$-vel.

Becslések r(k,l)-re

Felsőbecslés

$r(k,l)\leq {\binom {k+l-2}{k-1}}$

Alsóbecslés

Ha $k\leq 3$, akkor $r(k,k)\geq 2^{\frac {k}{2}}$

Alkalmazások

Tétel(Schur)

Ha az első n pozitív számot r színnel kiszínezzük, és $n$ elég nagy, akkor lesz az $x+y=z$ egyenletnek egyszínű megoldása, azaz olyan $x,y,z\leq u$ számok, amikre $x+y=z$ áll, és mindegyik egyszínű.