\magnification=\magstep1
\input amstex
\hsize=16truecm
\parskip=4pt
\parindent=18pt
 
 
\centerline{\bf Val\'osz\'{\i}n\H us\'egsz\'am\'{\i}t\'asi m\'odszerek
a kombinatorik\'aban}
\bigskip
 
\item{1.} Legyen $H$ egy legfeljebb $2^{r-1}-1$ \'el\H u $r$-uniform
hipergr\'af. Bizony\'\i tsuk be, hogy a pontok 2 sz\'\i nnel sz\'\i
nezhet\H ok \'ugy, hogy minden $r$ pont\'u \'elben mindk\'et sz\'\i n
el\H ofordul.
 
\item{2.} Bizony\'\i tsuk be, hogy az $R_2(n,n)$ Ramsey sz\'am
legal\'abb $2^{n/2}$.
 
\item{3.} Bizony\'\i tsuk be, hogy az $1,2,,\dots,2^{k/2}$ sz\'amok 2
sz\'\i nnel sz\'\i nezhet\H ok \'ugy, hogy ne legyen $k$ tag\'u
monokromatikus sz\'amtani sorozat.
 
\bigskip
Besz\'el\"unk  az 1997 Schweitzer verseny 1.
feladat\'anak (i.) r\'esz\'er\H{o}l, illetve a megold\'as gerinc\'et
alkot\'o Lov\'asz lok\'alis lemm\'ar\'ol \'es annak
bizony\'{\i}t\'as\'ar\'ol. A Schweitzer feladat:
\medskip
 
\item{}Defini\'aljuk minden $k$ pozit\'\i v eg\'esz sz\'amra
gr\'afoknak egy ${\Cal G}_k$ oszt\'aly\'at a k\"o\-vet\-ke\-z\H o
m\'odon. Egy $G=(V,E)$ gr\'af pontosan akkor eleme ${\Cal G}_k$-nak,
ha l\'etezik \'eleinek olyan $\psi\: E\to [k]=\{1,2,\dots, k\}$
sz\'\i nez\'ese, hogy a cs\'ucsok tetsz\H oleges $\varphi\: V\to [k]$
sz\'\i nez\'ese eset\'en tal\'alhat\'o a gr\'afnak olyan $e=\{x,y\}$
\'ele, melyre $\varphi(x)=\varphi(y)=\psi(e)$. \hfill\break
Bizony\'\i tsuk be, hogy l\'eteznek $c_1<c_2$ pozit\'\i v konstansok
az al\'abbi k\'et tulajdons\'aggal:
\itemitem{(i)} minden ${\Cal G}_k$-beli gr\'afnak legal\'abb $c_1k^2$
cs\'ucsa van;
\itemitem{(ii)} van ${\Cal G}_k$-ban olyan gr\'af, melynek legfeljebb
$c_2k^2$ cs\'usa van.
\medskip
A t\'argyaland\'o (i) r\'esz \'all\'{\i}t\'asa \'{\i}gy is
fogalmazhat\'o: Ha egy gr\'af cs\'ucsainak sz\'ama kisebb, mint $c_1
k^2$  ($c_1=\frac18$ v\'alaszt\'as p\'eld\'aul megfelel\H{o}), \'es a
gr\'af \'eleit kisz\'{\i}nezz\"uk $k$ sz\'{\i}nnel valamilyen
m\'odon, akkor a gr\'af cs\'ucsainak l\'etezik olyan
kisz\'{\i}nez\'ese ezzel a $k$ sz\'{\i}nnel \'ugy,  hogy e
sz\'{\i}nez\'essel a gr\'af minden \'el\'ere igaz a k\"ovetkez\H{o}
\'all\'{\i}t\'as: Az \'elnek \'es az \'el k\'et v\'egpontj\'aban
lev\H{o} cs\'ucsoknak a sz\'{\i}ne (azaz h\'arom helyen l\'ev\H{o}
sz\'{\i}n) mind\-egyi\-ke nem egyezhet meg. L\'assuk be az al\'abb
megfogalmazott \'es t\'argyaland\'o Lov\'asz lok\'alis lemma
seg\'{\i}ts\'eg\'evel a k\"ovetez\H{o} eredm\'enyt: Ha
minden cs\'ucsot egym\'ast\'ol f\"uggetlen\"ul kisz\'{\i}nez\"unk $k$
sz\'{\i}nnel, minden sz\'{\i}nt egyforma val\'osz\'{\i}n\H{u}s\'eggel
v\'alasztva, akkor pozit\'{\i}v annak a val\'osz\'{\i}n\H{u}s\'ege,
hogy valamelyik sz\'{\i}nez\'es teljes\'{\i}ti a k\'{\i}v\'ant
tulajdons\'agot.
 
A Lov\'asz lok\'alis lemma c\'elja j\'ol haszn\'alhat\'o felt\'etelt adni
arra, hogy pozit\'{\i}v legyen annak a val\'osz\'{\i}n\H{u}s\'ege,
hogy b\'{\i}zonyos esem\'enyek mindegyike bek\"ovetkezik. Olyan
fel\-t\'e\-telt fogalmaz meg, mely akkor is alkalmazhat\'o, amikor a
tekintett esem\'enyek nem teljesen (csak majdnem teljesen)
f\"uggetlenek, \'es az esem\'enyek egy\"uttes
be\-k\"o\-vet\-ke\-z\'e\-s\'e\-nek
a val\'osz\'{\i}n\H{u}s\'ege kicsi is lehet. \medskip\noindent
{\bf Lov\'asz lok\'alis lemma:}\/ {\it Legyenek $A_1,\dots, A_n$ esem\'enyek egy
val\'osz\'{\i}n\H{u}s\'egi mez\H{o}n, $d$ egy eg\'esz sz\'am, melyek
teljes\'{\i}tik a k\"ovetkez\H{o} felt\'eteleket:
 
\item{1.} $P(A_j)\le\dfrac1{4d}$ minden $j=1,\dots,n$-re
\item{2.} Lehet olyan gr\'afot defini\'alni, melynek cs\'ucsai az
$\{1,2,\dots,n\}$ pontok, minden pont foksz\'ama kisebb vagy
egyenl\H{o} $d$-vel, \'es amennyiben valamilyen az $i$ pont a
$j_1,\dots, j_k$ pontok egyik\'evel sincs \"osszek\"otve, akkor
az $A_i$ esem\'eny f\"uggetlen az $A_{j_1},\dots,A_{j_k}$ esem\'enyek
egy\"uttes\'et\H{o}l (azaz az $A_{j_1},\dots,A_{j_k}$
esem\'enyek minden f\"ugg\-v\'e\-ny\'e\-t\H{o}l).
 
Ekkor $P(\bar A_1\cdots\bar A_n)>0$, ahol $\bar A_i$ az $A_i$
esem\'eny komplementere.} \medskip
 
\item{4.} Bizony\'{\i}tsuk be a Lov\'asz lemm\'at, illetve ennek
seg\'{\i}ts\'eg\'evel a Schweitzer verseny els\H{o} feladat\'anak (i)
r\'esz\'et. \hfill \break
{\it Seg\'{\i}ts\'eg:}\/ Bizony\'{\i}tsuk be $k$ szerinti teljes
indukci\'oval, hogy
$$
P(A_j|\bar A_{i_1}\cdots \bar A_{i_k})=\frac{P(A_j\bar A_{i_1}\cdots
\bar A_{i_h}|\bar A_{i_{h+1}}\cdots \bar A_{i_k})}
{P(\bar A_{i_1}\cdots \bar A_{i_h}|\bar A_{i_{h+1}}\cdots
\bar A_{i_k})}\le\dfrac1{2d},
$$
ahol $i_1,\dots,i_h$ azok a pontok az $i_1,\dots,i_k$ pontok k\"oz\"ul,
amelyek a tekintett gr\'afban \"ossze vannak k\"otve a $j$ ponttal.
 
 
 
\bye