[an error occurred while processing this directive]

Kombinatorický seminář

V zimním semestru 2005/2006 se seminář koná pravidelně (modulo svátky) v úterý od 9:00 v posluchárně S4. Seminář vedou Martin Mareš a Robert Šámal.

Kombinatorický seminář (DMI022) je seminář pro studenty 2.-5. ročníku, zaměřený na řešení jednoduchých (ale často dosud nevyřešených) úloh z kombinatoriky a příbuzných oborů, jako je třeba teorie grafů a kombinatorická geometrie. Podstatnou součástí semináře je rovněž četba a referování odborných článků účastníky semináře. Každoročně je pro studenty Kombinatorického semináře pořádána Jarní škola kombinatoriky.

Program

18.10.Jan KynčlVariace na Hedetniemiho hypotezu
25.10.J.K./Ondra Plášilpokr. z minula + Grafy bez krátkých sudých kružnic
1.11.Ondra PlášilGrafy bez krátkých sudých kružnic
8.11.Tomáš BartošOrtogonality graf (aneb bez kvantové komunikace se téžko žije)
15.11.pokračování z minula
22.11.Josef CibulkaKorelace v náhodných kostrách a pokrývacích lesích
29.11.Bernard Lidickýin-place merging
6.12.Tomáš GavenčiakNimoidní hry
13.12.Robert SasákTrojúhelníkově nasycené grafy
20.12.Vánoční seminář
3.1.2006Michal FerovOptimal pebbling on paths and cycles
10.1.2006Marek TesařAnalýza míchání karet

Zamluvené články

Tomáš BartošGodsil, Newman: Colouring an ortogonality graph
Michal Ferovoptimal pebbling of paths and cycles
Jan KynčlDuffus, Sauer: Chromatic numbers and products
Ondra PlášilLam, Verstraëte: A note on graphs without short even cycles
Ondra PlášilBlass, Braun: Random orders and gambler's ruin
Robert SasákAshkenazi: C3-saturated graphs
Rudolf StolařBender et al.: Insertion Sort is O(n*log n)
Ondra SuchýTuza et al.: The cover pebbling number of graphs
Marek TesařHammarström: Card-shuffling analysis with Markov chains

Úloha na tento týden

I tento semestr budeme společně řešit problémy z knihy pana Lovásze: Combinatorial problems and exercises. Na konci jednoho semináře si řekneme zadání, na začátku příštího někdo, kdo problém vyřešil, řekne řešení. Tady na webu se kromě zadání dočtete i malou nápovědu.

Zadání: Máme několik přirozených čísel, jejich bitový xor je nenulový. Dokažte, že lze jedno z nich zmenšit (a ostatní nechat) tak, aby bitový xor získaných čísel byl nulový.

Odtud plyne řešení hry Nim: hru hrají dva hráči s několika hromádkami zápalek. Tah spočívá v odebrání libovolného počtu zápalek z jedné z hromádek, kdo nemůže táhnout, prohrál. Shora uvedené tvrzeníčko je nejtěžší část důkazu toho, že hra je vyhraná pro prvního hráče právě tehdy, když xor počtu sirek na jednotlivých hromádkách je nenulový.

Nápověda

Minulé úlohy

Historie semináře

minulý semestr [an error occurred while processing this directive]