Matematyka.pl

Niech \(\displaystyle{ q \in \mathbb{N}^+}\) oraz \(\displaystyle{ Q = \binom{2q}{q} }\). Graf \(\displaystyle{ K_Q}\) kolorujemy na dwa kolory, aby nie istniał podgraf \(\displaystyle{ K_{q+2}}\) w jednym kolorze. Udowodnij, że w \(\displaystyle{ K_Q}\) istnieją dwa podgrafy jednokolorowe \(\displaystyle{ K_q}\) w różnych kolorach.

Spróbuję pokazać o co mi chodzi na przykładzie:

Ale najpierw troszkę prawdopodobieństwa, żeby pokazać o co mi chodzi:

Niech \(\displaystyle{ A_{i}}\) zdarzenie losowe ze zbioru: \(\displaystyle{ \Omega}\)

Niech:

\(\displaystyle{ X_{A_{i}}=\begin{cases} 1, \omega \in A_{i} & \\0, \omega \notin A_{i} \end{cases}}\)

\(\displaystyle{ X= \sum_{i}^{} X_{A_{i}}}\)

\(\displaystyle{ E(X)=E\left(\sum_{i}^{} X_{A_{i}} \right) = \sum_{i}^{} E\left( X_{A_{i}}\right) = \sum_{i}^{} P(A_{i})}\) - wartość oczekiwana

Jeżeli:

\(\displaystyle{ E(X)=k \in \ZZ \Rightarrow \bigvee\limits_{\omega_{1},\omega_{2} \in \Omega}: X(\omega_{1}) \le k, X(\omega_{2}) \ge k}\)

I teraz o to mi chodzi, żeby pokazać, że wartość oczekiwana pewnego zdarzenia powinna być większa od jeden...

Mamy tu do czynienie z dwu-kolorowaniem zbioru: \(\displaystyle{ Q= {2q \choose q} }\)...

Chodzi o to , że kolorujemy na np.: zielony i czerwony i jeżeli mamy monochromatyczną klikę o rozmiarze \(\displaystyle{ q}\) np zieloną i klikę czerwoną
ale wtedy gdy nie istnieje monochromatyczna klika o rozmiarze \(\displaystyle{ q+2}\)

Więc to co opisałem będzie iloczynem zdarzeń niezależnych:

\(\displaystyle{ A_{i}=B_{i} \cap C_{i} \cap D_{i}}\)

\(\displaystyle{ B_{i}}\) - zdarzenie że istnieje klika zielona o rozmiarze: \(\displaystyle{ q}\)

\(\displaystyle{ C_{i}}\) - zdarzenie że istnieje klika czerwona o rozmiarze: \(\displaystyle{ q}\)

\(\displaystyle{ D_{i}}\) - zdarzenie że nie istnieje klika monochromatyczna o rozmiarze: \(\displaystyle{ q+2}\)

I na zdarzeniu \(\displaystyle{ A_{i}}\) określamy zmienną losową \(\displaystyle{ X_{A_{i}}}\)

z wartościami: \(\displaystyle{ 0 , 1}\)

\(\displaystyle{ P(B_{i})=P(C_{i})= \frac{1}{2^{ {q \choose 2} }} }\)

\(\displaystyle{ P(D_{i})=\left( 1- \frac{2}{2^{ {q+2 \choose 2} }} \right) }\)

\(\displaystyle{ P(A_{i})=P(B_{i}) \cdot P(C_{i}) \cdot P(D_{i})}\)

\(\displaystyle{ E(X)= {Q \choose q} P(B_{i}) \cdot P(C_{i}) \cdot P(D_{i})}\)

Pokaże to dla:

\(\displaystyle{ q=3, Q= {6 \choose 3}=20 , q+2=5}\)

Otrzymamy:

\(\displaystyle{ E(X)= {20 \choose 3} \cdot \frac{1}{2^3} \cdot \frac{1}{2^3} \cdot \left( 1- \frac{2}{2^{ {5 \choose 2} }} \right)=1140 \cdot \frac{2^9-1}{2^{15}} \approx 17 }\)

Znaczy, że wartość oczekiwana jest większa od jeden czyli taka sytuacja jest możliwa...

Można to rozszerzyć dla dowolnych:

\(\displaystyle{ q, Q= {2q \choose q} }\)