Twierdzenie o przyjaciołach i nieznajomych

78 ze 156 możliwych grafów znajomych-nieznajomych z 6 węzłami. Pozostałe 78 można uzyskać, odwracając kolory czerwony i niebieski na każdym wykresie. Na każdym wykresie czerwone/niebieskie węzły przedstawiają przykładową trójkę wspólnych znajomych/nieznajomych.

Twierdzenie o przyjaciołach i nieznajomych jest twierdzeniem matematycznym z dziedziny matematyki zwanej teorią Ramseya .

Oświadczenie

Załóżmy, że impreza liczy sześć osób. Rozważ dowolne dwa z nich. Mogą spotykać się po raz pierwszy – w takim przypadku nazwiemy ich wspólnymi nieznajomymi; albo mogli się już wcześniej spotkać — w takim przypadku będziemy ich nazywać wspólnymi znajomymi. Twierdzenie mówi:

W każdej sześcioosobowej grupie co najmniej troje z nich jest (parami) obcymi osobami lub co najmniej troje z nich jest (parami) wspólnymi znajomymi.

Konwersja do ustawienia teoretycznego grafów

Dowód twierdzenia wymaga jedynie trzystopniowej logiki . Wygodnie jest sformułować problem w języku teorii grafów.

Załóżmy, że graf ma 6 wierzchołków, a każda para (różnych) wierzchołków jest połączona krawędzią. Graf taki nazywany jest grafem pełnym (ponieważ nie może być więcej krawędzi). Kompletny wykres na $wierzchołkach$ ${\ displaystyle K_ {n}}$ oznaczony symbolem .

Teraz weź ${\ Displaystyle K_ {6}}$ . Ma w sumie 15 krawędzi. Niech 6 wierzchołków oznacza 6 osób w naszej grupie. Niech krawędzie będą pokolorowane na czerwono lub niebiesko, w zależności od tego, czy dwie osoby reprezentowane przez wierzchołki połączone krawędzią są odpowiednio nieznajomymi, czy wspólnymi znajomymi. Twierdzenie stwierdza teraz:

Bez względu na to, jak pokolorujesz 15 krawędzi

pary

niebieskiego, nie możesz uniknąć czerwonego trójkąta - to znaczy trójkąta, którego wszystkie trzy boki są czerwone, reprezentującego trzy wspólnych nieznajomych — lub niebieski trójkąt reprezentujący trzy pary wspólnych znajomych. Innymi słowy, bez względu na to, jakich kolorów użyjesz, zawsze będzie co najmniej jeden trójkąt monochromatyczny (tj. trójkąt, którego wszystkie krawędzie mają ten sam kolor).

Dowód

Wybierz dowolny wierzchołek; nazwij to p . Istnieje pięć krawędzi wychodzących z P . Każdy z nich jest w kolorze czerwonym lub niebieskim. Zasada szufladkowania mówi, że co najmniej trzy z nich muszą być tego samego koloru; bo jeśli jest mniej niż trzy jednego koloru, powiedzmy czerwonego, to przynajmniej trzy są niebieskie.

Niech A , B , C będą drugimi końcami tych trzech krawędzi, wszystkie tego samego koloru, powiedzmy niebieskiego. Jeśli którakolwiek z AB , BC , CA jest niebieska, to ta krawędź razem z dwiema krawędziami od P do jej punktów końcowych tworzy niebieski trójkąt. Jeśli żaden z AB , BC , CA nie jest niebieski, to wszystkie trzy krawędzie są czerwone i mamy czerwony trójkąt, czyli ABC .

papier Ramseya

Całkowita prostota tego argumentu, który tak silnie prowadzi do bardzo interesującego wniosku, sprawia, że twierdzenie to jest atrakcyjne. W roku 1930 w artykule zatytułowanym „O problemie logiki formalnej” Frank P. Ramsey udowodnił bardzo ogólne twierdzenie (obecnie znane jako twierdzenie Ramseya ), którego to twierdzenie jest prostym przypadkiem. To twierdzenie Ramseya stanowi podstawę dziedziny znanej jako teoria Ramseya w kombinatoryce .

Granice twierdzenia

A 2-kolorystyka K ₅ bez monochromatycznego K ₃

Wniosek z twierdzenia nie obowiązuje, jeśli grupę sześciu osób zastąpimy grupą mniejszą niż sześć osób. Aby to pokazać, podajemy kolorowanie K ₅ z czerwonym i niebieskim, które nie zawiera trójkąta o wszystkich krawędziach tego samego koloru. Rysujemy K ₅ jako pięciokąt otaczający gwiazdę ( pentagram ). Krawędzie pięciokąta kolorujemy na czerwono, a gwiazdki na niebiesko. Zatem 6 jest najmniejszą liczbą, dla której możemy wyciągnąć wniosek z twierdzenia. W teorii Ramseya zapisujemy ten fakt jako:

{\ Displaystyle R (3,3: 2) = 6.}

V. Krishnamurthy'ego. Kultura, emocje i znaczenie matematyki , Wiley Eastern, 1990. ISBN 81-224-0272-0 .

Linki zewnętrzne

Znajomi z imprez w miejscu przecinania węzłów (wymagana Java)