Twierdzenie Ramseya

Twierdzenie Ramseya – twierdzenie matematyczne dotyczące teorii grafów, udowodnione przez F. Ramseya.

Przedstawienie graficzne

Jeśli narysujemy n {\displaystyle n} punktów i połączymy je każdy z każdym dwoma kolorami, to n {\displaystyle n} jest k {\displaystyle k} -tą liczbą Ramseya wtedy i tylko wtedy, gdy n {\displaystyle n} jest najmniejszą liczbą taką, że na takim grafie pełnym znajdziemy jednokolorową klikę o k {\displaystyle k} wierzchołkach.

Liczby Ramseya

Definicja

Liczbą Ramseya R ( q 1 , q 2 , q 3 , … , q k ) {\displaystyle R(q_{1},q_{2},q_{3},\dots ,q_{k})} dla k , q 1 , q 2 , … , q k ∈ N {\displaystyle k,q_{1},q_{2},\dots ,q_{k}\in N} i k ⩾ 2 {\displaystyle k\geqslant 2} nazywamy najmniejszą liczbę n , {\displaystyle n,} taką że dla dowolnego k {\displaystyle k} -pokolorowania krawędziowego n {\displaystyle n} -wierzchołkowego grafu pełnego istnieje i , 1 ⩽ i ⩽ k , {\displaystyle i,1\leqslant i\leqslant k,} takie, że w pokolorowanym grafie jest klika rozmiaru q i , {\displaystyle q_{i},} której wszystkie krawędzie są w kolorze i . {\displaystyle i.}

Dwukolorowanie krawędzi grafu K5 bez monochromatycznej kliki rozmiaru 3. Dowód, że R ( 3 , 3 ) > 5. {\displaystyle R(3,3)>5.}

Przykład

Aby znaleźć na przykład wartość R(3,3), kolorujemy krawędzie grafów pełnych dwoma kolorami (np. czerwonym i niebieskim), szukając najmniejszego grafu pełnego, dla którego przy dowolnym kolorowaniu znajdziemy albo trójkąt czerwony, albo trójkąt niebieski. Okazuje się, że R(3,3)=6. Dowód: wybierzmy dowolny punkt grafu pełnego o sześciu wierzchołkach. Wychodzi z niego pięć krawędzi, więc przynajmniej trzy mają wspólny kolor. Załóżmy bez utraty ogólności, że są to trzy czerwone krawędzie (sytuacje te charakteryzują się pełną symetrią). Krawędzie te prowadzą do trzech różnych punktów; te trzy nowe punkty są połączone między sobą trzema krawędziami. Jeżeli choć jedna z nowych krawędzi jest czerwona, powstaje czerwony trójkąt, w przeciwnym przypadku powstaje niebieski trójkąt. Wobec tego R(3, 3) nie może być większe od 6. Rysunek po lewej dowodzi, że nie może być równe 5 ani mniejsze, więc istotnie jest równe 6. Ma to bardzo wygodną interpretację, mianowicie w zbiorze 6 osób zawsze znajdziemy 3 osoby znające się wzajemnie lub 3 osoby, które się nie znają.

Wyznaczanie wartości liczb Ramseya

Okazuje się, że wyznaczenie wartości liczb Ramseya jest bardzo trudnym obliczeniowo zadaniem. Często mamy do dyspozycji bardzo dokładne ich oszacowania, a nie jesteśmy w stanie określić ich wartości, mimo że nie są to wielkie liczby. Poniżej dotychczasowe osiągnięcia w tej dziedzinie:

Liczba Wartość Odkrywca, rok
R(3,3) 6 Greenwood i Gleason, 1955
R(3,4) 9 Greenwood i Gleason, 1955
R(3,5) 14 Greenwood i Gleason, 1955
R(4,4) 18 Greenwood i Gleason, 1955
R(3,6) 18 Kery, 1964
R(3,7) 23 Kalbfleich, 1966
R(3,8) 28 Graver i Yachel, 1968
R(3,9) 36 McKay i Zhang Ke Min, 1992
R(4,5) 25 McKay i Radziszowski, 1995
R(3,3,3) 17 Greenwood i Gleason, 1955
30 ⩽ R ( 3 , 3 , 4 ) ⩽ 31 {\displaystyle 30\leqslant R(3,3,4)\leqslant 31} (nie wyznaczono dokładnej wartości)
51 ⩽ R ( 3 , 3 , 3 , 3 ) ⩽ 62 {\displaystyle 51\leqslant R(3,3,3,3)\leqslant 62} (nie wyznaczono dokładnej wartości)
43 ⩽ R ( 5 , 5 ) ⩽ 49 {\displaystyle 43\leqslant R(5,5)\leqslant 49} (nie wyznaczono dokładnej wartości)
102 ⩽ R ( 6 , 6 ) ⩽ 165 {\displaystyle 102\leqslant R(6,6)\leqslant 165} (nie wyznaczono dokładnej wartości)
205 ⩽ R ( 7 , 7 ) ⩽ 540 {\displaystyle 205\leqslant R(7,7)\leqslant 540} (nie wyznaczono dokładnej wartości)
282 ⩽ R ( 8 , 8 ) ⩽ 1870 {\displaystyle 282\leqslant R(8,8)\leqslant 1870} (nie wyznaczono dokładnej wartości)
565 ⩽ R ( 9 , 9 ) ⩽ 6588 {\displaystyle 565\leqslant R(9,9)\leqslant 6588} (nie wyznaczono dokładnej wartości)
798 ⩽ R ( 10 , 10 ) ⩽ 23556 {\displaystyle 798\leqslant R(10,10)\leqslant 23556} (nie wyznaczono dokładnej wartości)

źródło: Optymalizacja dyskretna, modele i metody kolorowania grafów, pod redakcją Marka Kubale, WNT 2002.

Algorytm kwantowy

W roku 2011 zaproponowany został kwantowy algorytm obliczania dwukolorowych liczb Ramseya R ( m , n ) {\displaystyle R(m,n)} [1]. Algorytm został następnie użyty eksperymentalnie do wyliczenia liczb R ( 2 , 4 ) , R ( 2 , 5 ) , R ( 2 , 6 ) , R ( 2 , 7 ) , R ( 2 , 8 ) {\displaystyle R(2,4),R(2,5),R(2,6),R(2,7),R(2,8)} i R ( 3 , 3 ) , {\displaystyle R(3,3),} używając komputera kwantowego o 84 kubitach[2]. Minimalna liczba kubitów niezbędna do wyliczenia dwukolorowej liczby Ramseya wynosi N ( N − 1 ) / 2 {\displaystyle N(N-1)/2} gdzie N {\displaystyle N} jest wartością wyliczanej liczby[1]. Zaproponowany algorytm kwantowy sprawdza, czy dla danej liczby wierzchołków wszystkie grafy mają własność podaną w definicji. Dla znalezienia liczby Ramseya algorytm uruchamiany jest kolejno dla coraz większych N , {\displaystyle N,} szukaną wartością R ( m , n ) {\displaystyle R(m,n)} jest najniższe N {\displaystyle N} dla którego zwróci on odpowiedź pozytywną.

Nieklasyczne liczby Ramseya

Klasyczne liczby Ramseya zdefiniowane są za pomocą kolorowania grafów pełnych, w których poszukujemy monochromatycznych klik (czyli podgrafów pełnych). Pojęcie można jednak uogólnić na poszukiwania dowolnych podgrafów monochromatycznych.

Zobacz też

Przypisy

  1. ↑ a b Frank Gaitan, Lane Clark. Ramsey numbers and adiabatic quantum computing. „Phys. Rev. Lett.”. 108, s. 010501, 2012. DOI: 10.1103/PhysRevLett.108.010501. arXiv:1103.1345. (ang.). 
  2. ↑ ZhengbingZ. Bian ZhengbingZ. i inni, Experimental determination of Ramsey numbers with quantum annealing, „Physical Review Letters”, 111, 2012, s. 130505, DOI: 10.1103/PhysRevLett.111.130505, arXiv:1201.1842  (ang.).

Bibliografia

  • Magazyn Miłośników Matematyki 3/2008.
  • Tomasz Bartnicki. Czy 11 jest największą liczbą na świecie?. „Matematyka Społeczeństwo Nauczanie”. 39, s. 32–37, styczeń 2007.