$\parbox{7cm}{ {\Huge\bf SEMINARIUM}}$
Zakładu Matematyki Dyskretnej
Wydziału Matematyki Stosowanej
AGH

We wtorek, 13 maja 2003 roku, o godzinie 12:45

w sali 304, łącznik A-3-A-4, A G H

Leszek ADAMUS

(WMS, AGH)

wygłosi referat pod tytułem:

O drzewach i turniejach

Niech $g(k)$ będzie najmniejszą liczbą całkowitą, dla której każdezorientowane drzewo o $n$ wierzchołkach i $k$ liściach zawiera się w każdymturnieju rzędu $n + g(k)$. Na początku lat 90-tych Häggkvist i Thomasondowiedli, że $g(k)\le 2^{512(k^3)}$. W czasie referatu będziemyzajmowali się problemem zawierania się w turniejach specjalnego rodzajudrzew zorientowanych. Pokażemy w szczególności, że w każdym turniejurzędu $n+5$ zawiera się dowolne zorientowane drzewo o $n$ wierzchołkach i 3liściach, co oznacza, że $g(3)<=5$. (!) Jest to wynik Havety z roku 2002.Pokażemy także, że dowolny turniej rzędu $(38/5)n - 6$ zawiera każdezorientowane drzewo rzędu $n$.

Serdecznie zapraszamy wszystkich chętnych !