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

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

Ćwiczenie 1

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 $u,v\in \mathsf{V}\left(\overline{\mathbf{𝐆}}\right)=\mathsf{V}\left(\mathbf{𝐆}\right)$ . Jeżeli $u$ oraz $v$ leżą w dwu różnych spójnych składowych grafu $\mathbf{𝐆}$ , to $uv\in ̸\mathsf{E}\left(\mathbf{𝐆}\right)$ , czyli $uv\in \mathsf{E}\left(\overline{\mathbf{𝐆}}\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, $uw,vw\in ̸\mathsf{E}\left(\mathbf{𝐆}\right)$ , czyli $uw,vw\in \mathsf{E}\left(\overline{\mathbf{𝐆}}\right)$ . Wtedy $u\to w\to v$ jest ścieżką między $u$ i $v$ w grafie $\overline{\mathbf{𝐆}}$ .

Ćwiczenie 2

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$ oraz jego dopełnienie $\overline{{\mathbf{𝐆}}_1}$

Graf ${\mathbf{𝐆}}_1$ przedstawiony na rysunku spełnia warunki zadania.

Ćwiczenie 3

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 ${{𝒫}}_2\left(\{1,2,\dots ,n\}\right)$ na $k$ podrodzin i skorzystaj z Twierdzenia Ramseya 3.3.

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 $\mathsf{E}\left({{𝒦}}_n\right)={{𝒫}}_2\left(\{1,2,\dots ,n\}\right)$ na podzbiory $E_1,E_2,\dots ,E_k\subseteq \mathsf{E}\left({{𝒦}}_n\right)$ poprzez:

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

Na mocy Twierdzenia Ramseya 3.3 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 4

Pokaż, że dla $k$ -argumentowej liczby Ramseya $\mathsf{R}(a_1,a_2,\dots ,a_k)$ zachodzi:

$2^k<\mathsf{R}(3,3,\dots ,3)\le 3k!$

Wskazówka

Zauważ że, szukana wartość $\mathsf{R}(3,3,\dots ,3)$ 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

• $2^k<\mathsf{R}(3,3,\dots ,3)$

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 $\mathsf{R}(3,3,\dots ,3)$ jest większa niż $2^k$ .

• $\mathsf{R}(3,3,\dots ,3)\le 3k!$

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 $\mathsf{E}\left({{𝒦}}_{3k!}\right)$ na $k$ barw. Wierzchołek $v\in \mathsf{V}\left({{𝒦}}_{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 5

Graf doskonały to graf $\mathbf{𝐆}$ posiadający maksymalną klikę o rozmiarze równym liczbie chromatycznej $\chi \left(\mathbf{𝐆}\right)$ . Oszacuj liczbę Ramseya $\mathsf{R}(n,m)$ 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

$\mathsf{V}\left(\mathbf{𝐆}\right)=A_1\cup A_2\cup \dots \cup A_n$

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

$\left|\mathsf{V}\left(\mathbf{𝐆}\right)\right|\le 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:

$\mathsf{R}(n,m)\le (n-1)(m-1)+1=mn-n-m+2$

Ćwiczenie 6

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 $\mathsf{R}(3,3)=6$ .

Rozwiązanie

<flash>file=Ramsey c4 1.swf|width=300|height=150</flash>

<div.thumbcaption>1. Grafy $\mathbf{𝐆}$ oraz $\overline{\mathbf{𝐆}}$

<flash>file=Ramsey c4 3.swf|width=300|height=150</flash>

<div.thumbcaption>3. Grafy $\mathbf{𝐆}$ oraz $\overline{\mathbf{𝐆}}$

<flash>file=Ramsey c4 5.swf|width=300|height=150</flash>

<div.thumbcaption>5. Grafy $\mathbf{𝐆}$ oraz $\overline{\mathbf{𝐆}}$

<flash>file=Ramsey c4 2.swf|width=300|height=150</flash>

<div.thumbcaption>2. Grafy $\mathbf{𝐆}$ oraz $\overline{\mathbf{𝐆}}$

<flash>file=Ramsey c4 4.swf|width=300|height=150</flash>

<div.thumbcaption>4. Grafy $\mathbf{𝐆}$ oraz $\overline{\mathbf{𝐆}}$

<flash>file=Ramsey c4 pieciokat.swf|width=300|height=150</flash>

<div.thumbcaption>6. Grafy $\mathbf{𝐆}$ oraz $\overline{\mathbf{𝐆}}$

Załóżmy, że ani sześcioelementowy graf $\mathbf{𝐆}$ , ani jego dopełnienie nie zawiera czteroelementowego cyklu. Z drugiej strony, ponieważ $\mathsf{R}(3,3)=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 1 przedstawia grafy $\mathbf{𝐆}$ oraz $\overline{\mathbf{𝐆}}$ , gdzie szarymi liniami zaznaczyliśmy naszą niewiedzę dotyczącą istnienia krawędzi.

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 2.

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 3).

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

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 5.

Pięcioelementowy graf $\mathbf{𝐇}$ taki, że ani on sam ani jego dopełnienie $\overline{\mathbf{𝐇}}$ nie ma czteroelementowego cyklu, jest przedstawiony na rysunku 6.