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

We wtorek, 11 grudnia 2001 roku, o godzinie 12:45

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

Jarosław GRYTCZUK

(Uniwersytet Zielonogórski)

wygłosi referat pod tytułem:

O pudłach i pudełkach

Pudełko $n$-wymiarowe to po prostu zbiór postaci $%% X=X_{1}\times ...\times X_{n}$, gdzie $X_{i}$ są pewnymi zbiorami skończonymi. Pudełeczkiem zawartym w $X$ nazywamy pudełko $%% A=A_{1}\times ...\times A_{n}$, $A_{i}\subseteq X_{i}$, spełniają ce warunek $A_{i}\neq X_{i}$, dla wszystkich $i=1,...,n$. Czy najmniejszą liczbą pudełeczek, na które można podzielić $X$ jest $2^{n}$? To pytanie zostało postawione przez Kearnesa i Kissa (Finite algebras of finite complexity, Discrete Math. 207 (1999), 89-135) przy okazji badania tak zwanych algebr prostokątnych. A że odpowiedź na nie jest pozytywna udowodnili niedawno Alon, Bohman, Holzman i Kleitman (On partitions of discrete boxes, manuskrypt, 2001). Ich prosty i zarazem elegancki dowód opiera się na klasycznej dwoistości ,parzyste-nieparzyste''. Mimo szybkiego rozwiązania, problem Kearnesa i Kissa zdążył pobudzić do rozmaitych uogólnień i dalszych dociekań. Oto dwie, być może nietrudne kwestie, które pojawiły się podczas kontemplacji pudeł , pudełek i pudełeczek.
1. (Wersja grafowa) Niech $G=(V,E)$ będzie grafem o średnicy $d(G)$. Podzbiór $U\subseteq V$ nazywamy wypukłym jeśli dla dowolnych $u,v\in U$ każda najkrótsza ścieżka łącząca $u$ z $v$ zawiera się w zbiorze $U$. Kolorowanie wierzchołków grafu $G$ nazywamy antypodalnym, jeżeli klasy kolorów są wypukłe i dla każdej klasy $K$ istnieje wierzchołek $%% v\in V$ leżący w odległości $d(G)$ od $K$. Wreszcie, niech $%% \varphi (G)$ oznacza najmniejszą liczbę kolorów w antypodalnym kolorowaniu grafu $G$, lub $0$, jeśli takie kolorowanie nie istnieje. Czy jest prawdą , że $\varphi (G\times H)\geq \varphi (G)\varphi (H)$, dla dowolnych grafów $G$ i $H$?
2. (Wersja nieskończona) Czy pudełko $\aleph _{0}$-wymiarowe można podzielić na mniej niż $2^{\aleph _{0}}$ pudełeczek?

Serdecznie zapraszamy wszystkich chętnych !