Kombinatoricky seminar

Zapocty: Podminkou udeleni zapoctu za ZS 2001 je odreferovani clanku nebo priprava na referovani prideleneho clanku v pristim semestru nebo aktivni prace na seminari.

V LS 2001 se seminar kona ve stredu v 11:00-12:30 v seminarni mistnosti DIMATIA (tj. KAM) (nebo v S4 nebo jinde podle aktualni stavebni situace).

Kombinatoricky seminar je seminar pro studenty 2.-5. rocniku, zamereny na vychovu k tymove praci pomoci reseni vhodnych, casto dosud neresenych uloh z ruznych oboru kombinatoriky, napr. z teorie grafu nebo kombinatoricke geometrie. Vybirany jsou zejmena snadno formulovatelne problemy nevyzadujici specialni znalosti. Soucasti seminare je rovnez cetba a referovani odbornych clanku ucastniky seminare. Kazdorocne je pro studenty Kombinatorickeho seminare poradana Jarni skola kombinatoriky. Kod seminare je ted DMI022.

jarni skola 2002: bude urceno.

Seminar tomto semestru vedou Martin Klazar a Pavel Valtr a vypomaha nam radou i vtipem i Jan Kratochvil.

Seznam pridelenych clanku. Clanky s * uz byly odpredneseny.

Queens on non-square tori (10. 10. J. Spoustova)*
The polynomial part of a restricted partition function. . . (10. 10. P. Podbrdsky)*
Dartboard arrangements (10. 10. M. Sotakova)*
Pairs of disjoint q-element subsets. . . (10. 10. V. Jelinek)
Another form of matrix Nim (10. 10. J. Kara)*
Convex sets in the plane. . . (10. 10. Privetivy)*
How Berger, Felzenbaum and Fraenkel revolutionized covering systems. . . (10. 10. Sames)*
A new bound on the chromatic number. . . (10. 10. D. Sterba)
On distinct sums and distinct distances (24. 10. J. Cerny)
Which crossing number is it anyway? (24. 10. J. Bystron, P. Charvat)
The shortest distance among points ... (24. 10. T. Vyskocil)*
An improved lower bound for crossing numbers (31. 10. A. Slavik)
On Conway's thrackle conjecture (31. 10. P. Hoffmann)
Helly type ... (31. 10. Pergel)
Monotone paths in line arrangements (7. 11. Valla)*
On a Conjecture of Kemnitz (5. 12. Hubicka)

10.10. 2001 Rozdeleni nekolika clanku (viz vyse).

Problem o rozkladech mnozin: Existuje n>2 takove, ze pocet rozkladu mnoziny {1, 2, . . ., n} na sudy pocet bloku je roven poctu rozkladu na lichy pocet bloku?

Problem o kloboucich. Kazdy z n vesnicanu dostane ve tme na hlavu cerny nebo bily kloboucek, rozsviti se a kazdy z nich napise na papirek "mam bily kloboucek" nebo "mam cerny kloboucek" nebo "nevim, jaky mam kloboucek". Pokud nikdo nenapsal spatnou barvu sveho kloboucku a alespon jeden clovek ji uhadl, skupina vyhrala. V opacnem pripade (nekdo napsal spatnou barvu sveho klouboucku nebo vsichni napsali "nevim") skupina prohrala. Na Jake strategii se maji vesnicane predem domluvit, aby maximalizovali pravdepodobnost vyhry pro nahodne rozdani klobouku? Po rozsviceni se kazdy muze rozhlednou po ostatnich, nesmi se ale s nimi nijak domlouvat a samozrejme se nesmi podivat na vlastni kloboucek. Jednoducha strategie dava pro n=3 pravdepodobnost vyhry 3/4.

Jak synchronizovat radu vojaku, z nichz kazdy je (stejny) konecny automat vidici jen sve dva (jednoho, je-li krajni) sousedy, aby po povelu vydanem velitelem na zacatku rady vsichni po urcitem poctu taktu soucasne vystrelili?

17.10. 2001 Trochu o vojacich a pak referovani clanku Queens on non-square tori (Spoustova). Priste: Dartboard arrangements (Sotakova).

24.10. 2001 Dartboard arrangements (Sotakova). Priste bude komplexka a kombinatorika v podani p. Podbrdskeho.

31.10. 2001 Strucny uvod do komplexky a pak The polynomial part of a restricted partition function. . . (Podbrdsky).

7. 11. 2001 How Berger, Felzenbaum and Fraenkel revolutionized covering systems. . . (Sames).

14. 11. 2001 Another form of matrix Nim (Kara).

21. 11. 2001 (presun do studene S4) Jeste o 2 x 2 Nimu (Kara). Convex sets in the plane. . . (Privetivy): Mejme libovolny konecny soubor konvexnich mnozin v rovine, v nemz se v kazde ctverici mnozin nektere tri protinaji; potom existuje trinact bodu tak, ze kazda mnozina obsahuje alespon jeden z nich.

28. 11. 2001 Convex sets in the plane. . . (Privetivy), jeste zbyva trosku napriste.

5. 12. 2001 Dokonceni z minula a pak The shortest distance among points ... (T. Vyskocil).

12. 12. 2001 Dokonceni The shortest distance among points ... (T. Vyskocil) a Monotone paths in line arrangements (Valla)

19. 12. 2001 Vanocni besidka spojena s petim Hymny teorie grafu.

V novem roce: 2. 1. 2002 seminar odpada!

9. 1. 2002 Dokonceni Monotone paths in line arrangements (Valla) . Pak Which crossing number is it anyway? (J. Bystron) - V referovanem clanku je zavazna chyba?!

leden 2002