Na jare 2000 se seminar kona v patek ve 12:40-14:10 v seminarni mistnosti DIMATIA
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: 17.-27. kvetna 2000.
Aktualni info (jaro 2000): Postupujeme podle textu A. Bjornera
a R. P. Stanleyho "A combinatorial
miscellany" (CM), ktery je k dosazeni na homepage
druheho autora.
25.2. M. Klazar kap. 2 a 3 z CM: rozklady cisel, funkce p(n),
Eulerova identita, rovinne rozklady cisel (plane partition), funkce pp(n).
3.3. O. Crha kap. 3 z CM: Benderuv a
Knuthuv bijektivni dukaz (pomoci Schenstedovy korespondence) MacMahonova
vzorce pp(0)+pp(1)x+pp(2)x^2+... = (1-x)^{-1}.(1-x^2)^{-2}.(1-x^3)^{-3}.
...
10.3. J. Kratochvil - problemek o permutacich. D. Kral
nas prehledne a jasne poucil, jak se Schenstedova korespondence otoci (jak
se z dvojice tabulek (P,Q) vyrobi dvouradkove pole A).
17.3. D. Stanovsky nam povedel podle 4. kap. CM o Young tableaux
a postrasil nas algebrou. J. Nemecek - zacatek dukazu hakove formule
(Hook
formula) pro pocet Y. t. cisla n.
24.3. J. Nemecek - dokonceni dukazu hakove formule. M. Klazar
- dva bijektivni problemy. 1. Dokazte bijektivne, ze a(n)=8b(n-2),
kde a(n) je pocet nekrizicich se grafu s n vrcholy (izolovane vrcholy
dovoleny, nasobne hrany zakazany) a b(n) je pocet nekrizicich se grafu
s n hranami (izolovane vrcholy zakazany, nasobne hrany dovoleny). 2.
Dokazte bijektivne, ze a(n-2)=b(n), kde a(n) je pocet slov
nad {1, 2, 3} delky n, v nichz kazdy pocatecni usek obsahuje
alespon tolik 1 co 2 a b(n) je pocet rozkladu mnoziny {1, 2,
..., n}, v nichz (i) dve po sobe jdouci cisla nejsou v temze bloku
a (ii) neexistuji ctyricisla a<b<c<d a dva ruzne bloky
P a Q tak, ze a, d lezi v P a b, c v
Q.
31.3. R. Chocholous kap. 5 z CM o rostoucich a klesajicich podposloupnostech.
D. Piquet - rekurence pro cisla a(n) z 1. problemu.
7.4. V. Janda kap. 6 z CM o "Reduced decompositions". J.
Nemecek (vlastni!) dukaz identity a(n)=8b(n-2) z 1. problemu
pomoci GF.
14.4. J. Nesetril oznameni o www strance jarni skoly 2000 a
o prislusnych textech (vse bude pristi tyden). P. Podbrdsky
bijektivni dukaz identity
a(n)=8b(n-2) z 1. problemu. p. Hudec zacatek clanku
o hrave barevnosti (chi_a(G)<k+1 -> chi_g(G)<k(k+1)+1, kde
chi_a je acyklicka a chi_g hrava
barevnost).
21.4. Velky patek -> zrusena vyuka -> seminar neni.
28.4. D. Kral informace o jarni skole. V. Sisma cl. "Lecture
Hall partitions".
5.5. M. Kupsa kap. 7 z CM o dlazdenich a jejich poctech, v zaveru
ziva diskuse.
12.5. M. Klazar - problem. 3. Necht s(n)
je pocet permutaci a_1a_2...a_{2n-1} cisel 1, 2, ..., 2n-1
splnujicich a_2=a_1+a_3, a_4=a_3+a_5, ...,
a_{2n-2}=a_{2n-3}+a_{2n-1}. Napriklad s(3)=4: 14352,
25341, 45132 a 23154. Dokazte, ze vzdy s(n)>0 (znamo, ale chtelo
by to lepsi dukaz). Je pravda, ze s(n)<c^n pro nejakou konstantu
c>1? Jak pocitat cisla s(n)? Jejich asymptotika? J.
Nemecek bijektivni dukaz identity a(n-2)=b(n) z 2. problemu.
19.5. Seminar odpada kvuli jarni skole.
26.5. Seminar se kona! (S doc. Kratochvilem.)
vyhledove: p. Hudec dokonceni clanku o hrave barevnosti.
J. Foniok clanek o hornim odhadu cisla S_n(p) (pocet n-permutaci
neobsahujicich danou
permutaci p). P. Rexova cl. "Diagonal checker jumping..." (Eriksen,
Eriksson & Eriksson). D. Piquet cl. o novem grafovem polynomu
(Arratia & spol).
Letos opet koname separatni kombinatoricky seminar pro pokrocile, kde se budou referovat narocnejsi clanky.
Seminar tomto semestru vedou Martin Klazar a Jan Kratochvil.
kveten 2000