Liczby Turána i Ramseya dla 3-jednolitych ścieżek

Abstract

Tematem pracy są liczby Ramseya i Turána dla 3-jednolitej luźnej ścieżki długości 3, oznaczonej jako P. Zaczęliśmy od wprowadzenia terminologii oraz przedstawiliśmy nasze wyniki z podziałem na te dotyczące liczb Ramseya i liczb Turána. W rozdziale 1 sformułowaliśmy najważniejszy wynik - Twierdzenie 2.2. Stwierdza ono, że liczba Ramseya R(P;r)=r+6 dla liczby kolorów mniejszej niż 8. Do wyznaczania liczb Ramseya mogą służyć liczby Turána. Dla k-grafu F jest to maksymalna liczba krawędzi w k-grafie o n wierzchołkach, który nie zawiera F. Aby udowodnić Twierdzenie 2.2 musieliśmy odnieść się do Twierdzenia Erdősa-Ko-Rado oraz do Twierdzenia dotyczącego liczby Turána dla trójkąta. Najważniejszym twierdzeniem typu turánowskiego, w naszej pracy jest Twierdzenie 2.7. Jest to liczba Turána dla P, dla wszystkich n. Ponadto, w rozdziale 2 podaliśmy Twierdzenia 2.9 i 2.10, będące rozszerzeniem standardowego pojęcia liczby Turána, były to liczby Turána drugiego i trzeciego rzędu. Twierdzenia te okazały się niezbędne w dowodzie Twierdzenia 2.2, który został przedstawiony w rozdziale 3. W rozdziale 4 skupiliśmy się na warunkowych liczbach Turána i ich zastosowaniu w dowodach Twierdzenia 2.7. Ponadto, podaliśmy kilka wyników związanych z warunkowymi liczbami Turána. Rozdział 5 został poświęcony na przedstawienie dowodów pozostałych twierdzeń.

The main subject of this dissertation are Ramsey and Turán numbers for the 3-uniform loose path P of length 3. We began by introducing the basic terminology and our results related to Ramsey and Turán numbers. In chapter 1, we formulated the most crucial result - Theorem 2.2. It gives the exact value for Ramsey number R(P;r)=r+6, for a number of colors less than 8. One of the most important method in determining Ramsey numbers is an application of Turán numbers. In order to prove Theorem 2.2. we had to use Erdős-Ko-Rado Theorem and Theorem related to Turán number for a triangle. The most important Turán-type Theorem is 2.7, which determines Turán number for P, for all n. Moreover, in chapter 2, we stated Theorems 2.9 and 2.10, which were extensions of a standard approach of Turán number- Turán numbers of the second and the third order. Those Theorems appeared to be very useful in the proof of Theorem 2.2, which was introduced in chapter 3. In chapter 4, w focused on conditional Turán numbers and their applications in the proofs of Theorem 2.7. The last chapter 5 was devoted to the presentation of the proofs of remaining theorems.