Oszacowania rozgrywanych liczb Ramseya

Abstract

Praca skupia się na oszacowaniach rozgrywanych liczb Ramseya. Dowodzimy m.in., że jeśli graf G nie jest dwudzielny, a H jest spójny, to rozgrywana liczba Ramseya dla pary (G, H) wynosi co najmniej (fi+1)v(H)+e(H)−2fi+1, gdzie fi jest złotą liczbą. Znajdujemy też dokładne wartości dla gry czworokąt vs. ścieżka. Ponadto prezentujemy metodę (pół)potencjału, która pozwala znajdować oszacowania rozgrywanych liczb Ramseya i dowodzimy, że jest ona uniwersalna. Pokazujemy też, że wiele ze znanych dowodów dotyczących rozgrywanych liczb Ramseya da się wyrazić w języku tej metody.

The work focuses on estimates of online Ramsey numbers. We prove, among other things, that if a graph G is not bipartite and H is connected, then the online Ramsey number for the pair (G, H) is at least (phi+1)v(H)+e(H)−2phi+1, where phi is the golden ratio. We also determine the exact values for the game between a quadrilateral and a path. Furthermore, we present the (semi-)potential method, which allows for estimating online Ramsey numbers, and we prove that it is universal. We also show that many of the known proofs concerning online Ramsey numbers can be expressed in the language of this method.