• Gyula O.H. Katona

Consider all k-element subsets and l-element subsets (k > l) of an n-element set as vertices of a bipartite graph. Two vertices are adjacent if the corresponding l-element set is a subset of the corresponding k-element set. Let G_{k,l} denote this graph. The domination number of G_{k,1} is exactly determined.

We pose the following conjecture. The domination number of G_{k,2} is asymptotically equal to (k+3)/2(k-1)(k+1) n^2 for k≥3.

Unfortunately, we can give only lower and upper estimates on this domination number. The constant in the conjecture for k=3 is 3/8. We will prove that this is a correct upper estimate, but our lower estimate is only 7/20 although difficult theorems like Szemerédi's regularity lemma is used.

Joint work with Leila Badakhshian.

• Konstanty Junosza-Szaniawski

Twierdzenie Ramseya można sparafrazować słowami: w każdym bałaganie znajdzie się uporządkowany kawałek, o ile bałagan jest dostatecznie duży, inaczej każda odpowiednio duża struktura zawiera uporządkowaną podstrukturę. Dla grafów definiujemy Liczbę Ramseya R(k) jako najmniejszą liczbę n, taką że dla dowolnego pokolorowania zbioru krawędzi grafu pełnego o n wierzchołkach istnieje podgraf pełny o k wierzchołkach i wszystkich krawędziach w jednym kolorze.

Przypuśćmy, że nasz bałagan chcemy podzielić na uporządkowane kawałki i ewentualnie coś niedużego, niekoniecznie uporządkowanego. Rozmiar tego ostatniego kawałka będziemy nazywać Resztą Ramseya. W przypadku grafów Reszta Ramseya RR(k) to liczba taka, że zbiór wierzchołków każdego dostatecznie dużego grafu pełnego o dowolnym pokolorowaniu jego krawędzi dwoma kolorami, może być podzielony na zbiory monochromatyczne o rozmiarze co najmniej k oraz pewien zbiór (resztę) o rozmiarze nie większym niż RR(k). Oczywiście RR(k)< R(k), ale różnica między Resztą a Liczbą Ramseya może być stosunkowo nieduża.

Twierdzenia typu Ramseyowskiego dowodzi się dla różnych struktur i różnej liczby kolorów i dla nich w analogiczny sposób definiuje sie Resztę Ramseya. Opowiem o ciekawszych przykładach.

• Mariusz Woźniak

Wierzchołki nie lubią jak się je traktuje jako ot, elementy zbioru. Każdy z nich uważa, że ma własna osobowość, coś co go odróżnia od innych. Jeśli nie od wszystkich, to chociażby od sąsiadów. Często, aby osiągnąć zamierzony efekt, używają kolorów ... .

• Jarosław Grytczuk

A famous theorem of Thomassen asserts that every planar graph is 5-choosable. Voigt proved that this result is optimal by exhibiting a non-4-choosable planar graph. We prove that from every planar graph one may delete a matching so that the resulting graph is 4-choosable. The proof uses graph polynomials and is based on Combinatorial Nullstellensatz of Alon.

Joint work with Xuding Zhu.

• Andrzej Ruciński

Przedstawię nowe wyniki dotyczące istnienia cykli Hamiltona w hipergrafach jednolitych uzyskane wspólnie z A. Żakiem oraz z Chr. Reiherem, V. Rodlem, M. Schachtem i E. Szemeredim.

• Krzysztof Parol

Przedstawię fragment pracy doktorskiej dotyczący zliczania drzew rozpinających w grafach cyklicznych. Pokażę jak uzyskane wyniki mogą pomóc w obliczaniu pewnych całek niewłaściwych.

• Krzysztof Bryś

Opowiem o problemie Holyera, czyli klasyfikowaniu ze względu na złożoność obliczeniową pytań o istnienie podziału zbioru krawędzi danego grafu na podzbiory indukujące grafy izomorficzne z określonym grafem H.

• Monika Pszczoła

Dekompozycja grafu to podział zbioru jego krawędzi na zbiory indukujące grafy z wybranej rodziny. W zależności od tej rodziny, stwierdzenie, czy dany graf ma dekompozycję, ma różną złożoność obliczeniową.

• Paweł Naroski

Opowiem o pewnym uogólnieniu pojęcia cyklu Eulera na hipergrafy 3-jednorodne i pewnym uogólnieniu twierdzenia Eulera ("Eulera graf!"), które ono umożliwia. Będą to, a jakże, wyniki uzyskane wspólnie ze Zbigniewem Loncem.

• Michał Tuczyński

Powiem o algorytmach typu mierz i zwyciężaj znajdujących liczbę zbiorów niezależnych i maksymalnych zbiorów niezależnych w pewnych klasach grafów.

• Paweł Rzążewski

W trakcie referatu opowiem o tzw. ciągach o promieniu k i przedstawię dwa powiązane z nimi problemy, którym, moim zdaniem, warto przyjrzeć się bliżej. Będą to ciągi o promieniu k dla grafów oraz tzw. BL-etykietowania.

Problemy przedstawione w referacie zostały sformułowane w ramach współpracy ze Z. Loncem, A. Bondym i M. Dębskim.