Matematyka dyskretna 2/Ćwiczenia 3: Własności podziałowe i Twierdzenie Ramsey'a

Własności podziałowe i Twierdzenie Ramsey'a

Ćwiczenie ex spoj

Wykaż, że dla dowolnego grafu $\mathbf{𝐆}$ , co najmniej jeden z grafów $\mathbf{𝐆}$ , $\overline{\mathbf{𝐆}}$ jest spójny.

Wskazówka

Rozważ graf $\overline{\mathbf{𝐆}}$ w przypadku, gdyby $\mathbf{𝐆}$ nie był spójny, czyli posiadał co najmniej dwie spójne składowe.

Rozwiązanie

Zakładając, że $\mathbf{𝐆}$ nie jest spójny, czyli ma co najmniej dwie spójne składowe, pokażemy, że $\overline{\mathbf{𝐆}}$ jest spójny. Niech Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle u,v\in{\sf V}\!\left(\overline{\mathbf{G}}\right)={\sf V}\!\left(\mathbf{G}\right) } . Jeżeli $u$ oraz $v$ leżą w dwu różnych spójnych składowych grafu $\mathbf{𝐆}$ , to Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle uv\not\in{\sf E}\!\left(\mathbf{G}\right) } , czyli Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle uv\in{\sf E}\!\left(\overline{\mathbf{G}}\right) } . Niech więc $u$ wraz z $v$ leżą w tej samej spójnej składowej $C$ grafu $\mathbf{𝐆}$ . Graf $\mathbf{𝐆}$ ma jednak przynajmniej jeszcze jedną spójną składową $\mathrm{\varnothing }\ne C^{\prime }\ne C$ . Wtedy wierzchołek $w\in C^{\prime }$ nie jest sąsiadem (w $\mathbf{𝐆}$ ) ani $u$ , ani $v$ . A zatem, Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle uw, vw \not\in {\sf E}\!\left(\mathbf{G}\right) } , czyli Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle uw, vw \in {\sf E}\!\left(\overline{\mathbf{G}}\right) } . Wtedy $u\to w\to v$ jest ścieżką między $u$ i $v$ w grafie $\overline{\mathbf{𝐆}}$ .

Ćwiczenie ex ekstr

Znajdź ośmiowierzchołkowy graf bez trójelementowych klik i czteroelementowych antyklik.

Wskazówka

Przeanalizuj wierzchołki ośmiokąta połączone bokami oraz przekątnymi łączącymi naprzeciwległe wierzchołki.

Rozwiązanie

Graf ${\mathbf{𝐆}}_1$ przedstawiony na Rysunku Uzupelnic cw ramsey 8w| spełnia warunki zadania.

[!ht]

{cw_ramsey_8w} {Graf ${\mathbf{𝐆}}_1$ oraz jego dopełnienie $\overline{{\mathbf{𝐆}}_1}$ . [Rysunek z pliku: cwramsey8w.eps]}

Ćwiczenie ex shur

Pokaż, że dla $k\in \mathbb{\mathbb{N}}$ , istnieje $n\in \mathbb{\mathbb{N}}$ takie, że w dowolnym podziale zbioru liczb $\{1,2,\dots ,n\}$ na $k$ podzbiorów, jest podzbiór zawierający liczy $a,b,c$ spełniające $a+b=c$ .

Wskazówka

Przetłumacz podział zbioru $\{1,2,\dots ,n\}$ na $k$ podzbiorów, na podział rodziny Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \mathscr{P}_{2}\!\left( \left\lbrace 1,2,\ldots,n \right\rbrace \right) } na $k$ podrodzin i skorzystaj z Twierdzenia Ramseya [th][th Ramsey].

Rozwiązanie

Niech $\{1,2,\dots ,n\}=V_1\cup V_2\cup \dots ,V_k$ . W grafie pełnym ${{𝒦}}_n$ o wierzchołkach $1,2,\dots ,n$ zdefiniujmy podział zbioru krawędzi Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf E}\!\left(\mathcal{K}_{n}\right)=\mathscr{P}_{2}\!\left( \left\lbrace 1,2,\ldots,n \right\rbrace \right) } na podzbiory Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle E_1,E_2,\ldots,E_k\subseteq{\sf E}\!\left(\mathcal{K}_{n}\right) } poprzez:

$ab\in E_i$ wtedy i tylko wtedy, gdy $|a-b|\in V_i$ .

Na mocy Twierdzenia Ramseya [th][th Ramsey] otrzymujemy, że przy odpowiednio dużym $n$ , istnieje taki zbiór $\{a,b,c\}$ , którego krawędzie należą do któregoś $E_i$ , czyli $ab,bc,ac\in E_i$ . Bez straty ogólności załóżmy, że $a>b>c$ . Wtedy, z definicji $E_i$ , mamy:

$(a-b),(b-c),(a-c)\in V_i,$

i oczywiście

$(a-b)+(b-c)=(a-c).$

Ćwiczenie ex oszac

Pokaż, że dla $k$ -argumentowej liczby Ramseya Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf R}\!\left( a_1,a_2,\ldots,a_k \right) } zachodzi:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle 2^k<{\sf R}\!\left( 3,3,\ldots,3 \right)\leq3k!. }

Wskazówka

Zauważ że, szukana wartość Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf R}\!\left( 3,3,\ldots,3 \right) } to najmniejsza liczność grafu pełnego ${{𝒦}}_n$ , w którym po dowolnym pomalowaniu krawędzi na $k$ kolorów, istnieje trójkąt złożony z krawędzi tego samego koloru. W oszacowaniu od góry zastosuj indukcję po $k$ . Rozważ dowolny wierzchołek $v$ i najliczniejszy zbiór krawędzi oraz ich drugich końców incydentnych z $v$ .

Rozwiązanie

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle 2^k<{\sf R}\!\left( 3,3,\ldots,3 \right) }

Niech wierzchołkami kliki ${{𝒦}}_{2^k}$ będą $k$ -elementowe ciągi $(a_1,a_2,\dots ,a_k)$ , gdzie $a_i=0,1$ . Pokolorujmy krawędzie ${{𝒦}}_{2^k}$ na $k$ kolorów w następujący sposób:

• • pierwszym kolorem pokolorujmy wszystkie krawędzie postaci
    

$\left((0,a_2,\dots ,a_k)(1,b_2,\dots ,b_k)\right)$

• • drugim kolorem pokolorujmy wszystkie krawędzie postaci
    

$\left((0,0,a_3,\dots ,a_k)(0,1,b_3,\dots ,b_k)\right)$ oraz postaci
$\left((1,0,a_3,\dots ,a_k)(1,1,b_3,\dots ,b_k)\right)$

• • i w ogólności, $i$ -tym kolorem wszystkie krawędzie postaci
    

$\left((c_1,\dots ,c_{i-1},0,a_{i+1},\dots ,a_k)(c_1,\dots ,c_{i-1},1,b_{i+1},\dots ,b_k)\right)$

Nietrudno zauważyć, że po usunięciu z grafu ${{𝒦}}_{2^k}$ wszystkich krawędzi poza krawędziami o z góry ustalonym kolorze, otrzymujemy graf dwudzielny, a więc bez trójkątów. Graf ${{𝒦}}_{2^k}$ wraz ze zdefiniowanym kolorowaniem świadczy więc, że $k$ -argumentowa liczba Ramseya Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf R}\!\left( 3,3,\ldots,3 \right) } jest większa niż $2^k$ .

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf R}\!\left( 3,3,\ldots,3 \right)\leq3k! }

Pokażemy, że dowolnie kolorując krawędzie grafu pełnego ${{𝒦}}_{3k!}$ na $k$ kolorów, znajdziemy trójkąt o krawędziach tego samego koloru. Dowód będzie przeprowadzony indukcyjnie ze względu na $k$ . Dla $k=1$ nierówność jest oczywista. Rozważmy więc graf pełny ${{𝒦}}_{3k!}$ , gdzie $k>1$ . Ponadto rozważmy dowolne kolorowanie krawędzi Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf E}\!\left(\mathcal{K}_{3k!}\right) } na $k$ barw. Wierzchołek Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle v\in{\sf V}\!\left(\mathcal{K}_{3k!}\right) } jest incydentny z $3k!-1$ krawędziami. Z Uogólnionej Zasady Szufladkowej otrzymujemy, że musi istnieć $3(k-1)!$ krawędzi tego samego koloru, powiedzmy $c$ , incydentnych z $v$ . Niech $V^{\prime }$ będzie zbiorem wierzchołków połączonych z $v$ za pomocą krawędzi o kolorze $c$ . Jeśli dla jakichś dwu wierzchołków $u,w\in V^{\prime }$ krawędź $uw$ ma kolor $c$ , to trójkąt o wierzchołkach $u,v,w$ jest monochromatyczny. Niech zatem kolorowanie krawędzi pomiędzy wierzchołkami z $V^{\prime }$ nie używa koloru $c$ . Kolorowanie to używa więc tylko $k-1$ barw. Ponieważ $\left|V^{\prime }\right|\ge 3(k-1)!$ , to założenie indukcyjne daje w $V^{\prime }$ trójkąt złożony z krawędzi o tym samym kolorze.

Ćwiczenie ex perfect

Graf doskonały to graf $\mathbf{𝐆}$ posiadający maksymalną klikę o rozmiarze równym liczbie chromatycznej $\chi \left(\mathbf{𝐆}\right)$ . Oszacuj liczbę Ramseya Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf R}\!\left( n,m \right) } dla grafów doskonałych.

Wskazówka

Zbiór wierzchołków grafu $\mathbf{𝐆}$ jednego koloru tworzą antyklikę, więc liczba chromatyczna $\chi \left(\mathbf{𝐆}\right)$ jest liczbą antyklik, którymi można pokryć graf $\mathbf{𝐆}$ .

Rozwiązanie

Jednokolorowe wierzchołki grafu $\mathbf{𝐆}$ tworzą antyklikę, więc liczba chromatyczna $\chi \left(\mathbf{𝐆}\right)$ jest liczbą antyklik, którymi można pokryć graf $\mathbf{𝐆}$ . A zatem dla $n=\chi \left(\mathbf{𝐆}\right)$ istnieją parami rozłączne antykliki $A_1,A_2,\dots ,A_n$ takie, że

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf V}\!\left(\mathbf{G}\right)=A_1\cup A_2\cup\ldots\cup A_n. }

Oznaczając przez $m$ rozmiar najliczniejszej antykliki w grafie $\mathbf{𝐆}$ otrzymujemy

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \left\vert {\sf V}\!\left(\mathbf{G}\right) \right\vert\leq n\cdot m. }

Graf $\mathbf{𝐆}$ jest doskonały, więc liczba chromatyczna $\chi \left(\mathbf{𝐆}\right)=n$ jest rozmiarem najliczniejszej kliki. A zatem graf doskonały, w którym kliki nie są liczniejsze niż $n$ , a antykliki nie są liczniejsze niż $m$ , ma co najwyżej $n\cdot m$ wierzchołków. Graf doskonały o co najmniej $nm+1$ elementach musi więc mieć klikę $n+1$ elementową lub antyklikę $m+1$ elementową. A zatem:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf R}\!\left( n,m \right)\leq\left( n-1 \right)\left( m-1 \right)+1=mn-n-m+2. }

Ćwiczenie ex c4

Pokaż, że jeśli graf $\mathbf{𝐆}$ ma sześć wierzchołków, to on sam lub jego dopełnienie $\overline{\mathbf{𝐆}}$ ma czteroelementowy cykl. Czy o grafach pięcioelementowych da się powiedzieć to samo?

Wskazówka

Skorzystaj z faktu, że Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf R}\!\left( 3,3 \right)=6 } .

Rozwiązanie

Załóżmy, że ani sześcioelementowy graf $\mathbf{𝐆}$ , ani jego dopełnienie nie zawiera czteroelementowego cyklu. Z drugiej strony, ponieważ Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf R}\!\left( 3,3 \right)=6 } , to $\mathbf{𝐆}$ lub $\overline{\mathbf{𝐆}}$ zawiera trójkąt. Bez straty ogólności załóżmy, że to $\mathbf{𝐆}$ zawiera trójkąt, powiedzmy $\{c,d,e\}$ . Rysunek Uzupelnic ramsey c4 1| przedstawia grafy $\mathbf{𝐆}$ oraz $\overline{\mathbf{𝐆}}$ , gdzie szarymi liniami zaznaczyliśmy naszą niewiedzę dotyczącą istnienia krawędzi.

[!ht]

{ramsey_c4_1} {Grafy $\mathbf{𝐆}$ oraz $\overline{\mathbf{𝐆}}$ . [Rysunek z pliku: ramseyc41.eps]}

Gdyby teraz któryś z wierzchołków $a,b,f$ byłby połączony z co najmniej dwoma wierzchołkami ze zbioru $\{c,d,e\}$ , to wraz z tymi wierzchołkami $c,d,e$ tworzyłby czteroelementowy cykl. A zatem każdy z wierzchołków $a,b,f$ ma co najwyżej jednego sąsiada w zbiorze $\{c,d,e\}$ . Tym samym, w grafie $\overline{\mathbf{𝐆}}$ , każdy z wierzchołków $a,b,f$ ma przynajmniej dwu sąsiadów w zbiorze $\{c,d,e\}$ . Bez straty ogólności załóżmy, że to $b$ sąsiaduje z $d$ oraz $e$ , jak przedstawiono na Rysunku Uzupelnic ramsey c4 2|.

[!ht]

{ramsey_c4_2} {Grafy $\mathbf{𝐆}$ oraz $\overline{\mathbf{𝐆}}$ . [Rysunek z pliku: ramseyc42.eps]}

Aby uniknąć niepożądanego cyklu w $\overline{\mathbf{𝐆}}$ , wierzchołek $a$ musi więc być sąsiedni z $c$ oraz $e$ , a wierzchołek $f$ z $c$ oraz $d$ (patrz Rysunek Uzupelnic ramsey c4 3|).

[!ht]

{ramsey_c4_3} {Grafy $\mathbf{𝐆}$ oraz $\overline{\mathbf{𝐆}}$ . [Rysunek z pliku: ramseyc43.eps]}

Analizując dalej graf $\overline{\mathbf{𝐆}}$ zauważamy, że nie może on mieć żadnej z krawędzi $ef,ad,bc$ (patrz Rysunek Uzupelnic ramsey c4 4|).

[!ht]

{ramsey_c4_4} {Grafy $\mathbf{𝐆}$ oraz $\overline{\mathbf{𝐆}}$ . [Rysunek z pliku: ramseyc44.eps]}

Krawędzie te muszą więc być w grafie $\mathbf{𝐆}$ . Ale, ich istnienie zabrania krawędzi $ab,af,bf$ w $\mathbf{𝐆}$ . Tym samym w grafie $\overline{\mathbf{𝐆}}$ mamy cykl

$a\to b\to d\to f\to a,$

jak na Rysunku Uzupelnic ramsey c4 5|.

[!ht]

{ramsey_c4_5} {Grafy $\mathbf{𝐆}$ oraz $\overline{\mathbf{𝐆}}$ . [Rysunek z pliku: ramseyc45.eps]}

Pięcioelementowy graf $\mathbf{𝐇}$ taki, że ani on sam ani jego dopełnienie $\overline{\mathbf{𝐇}}$ nie ma czteroelementowego cyklu, jest przedstawiony na Rysunku Uzupelnic ramsey c4 pieciokat|.

[!ht]

{ramsey_c4_pieciokat} {Grafy $\mathbf{𝐆}$ oraz $\overline{\mathbf{𝐆}}$ . [Rysunek z pliku: ramseyc4pieciokat.eps]}