Problemovy seminar z kombinatoriky
Anotace
Tymova spoluprace pri reseni otevrenych kombinatorickych problemu. Vybirany jsou jednoduse formulovatelne stredne tezke problemy z kombinatoriky.V letnim semestru 2012/13 v prvnich tydnech semestru zkoumame kombinatorickou hru mezi dvema hraci tykajici se deleni pizzy. Schazime se ve stredu v 15:40 v pracovne 223 na Male Strane.
V zimnim semestru 2006/2007 jsme resili otazku, kolik policajtu je potreba na dopadeni zlodeje na libovolnem grafu nakreslitelnem bez krizeni na pneumatice, resp. jinych plochach.
V letnim semestru 2005/2006 byly reseny nektere slozitostni otazky.
V zimnim semestru 2005/2006 jsme studovali ulohu prerovnani palacinek. Vstupem teto ulohy je libovolna posloupnost navzajem ruzne velkych palacinek a vystupem posloupnost utridena od nejmensi po nejvetsi. Jedinou povolenou opereraci je otoceni libovolne zvoleneho pocatecniho useku posloupnosti, napr. posloupnost 1367254 lze pozmenit jednou operaci sesti zpusoby, napr. na posloupnost 6317254 nebo 5276314. Otazkou je, jaky je minimalni pocet operaci potrebny pro utrideni dane posloupnosti a pro kterou matici dane velikosti n je tento pocet nejvetsi. Take jsme se zabyvali prumernym poctem operaci pro nahodne zvolenou pocatecni posloupnost dane velikosti. Na sepsani vysledku pracuje J. Cibulka.
V letnim semestru 2004/2005 jsme se zabyvali 0-1 maticemi, ktere maji zakazanou danou permutacni matici P, tj. neobsahuji podmatici, ktera by mela jednicky vsude tam, kde je ma P. Je znamo, ze pocet jednicek v 0-1 matici n x n, ktera ma zakazanou permutacni matici P, je nejvyse c(P)*n. Take plati, ze pocet permutacnich n x n matic, ktere maji zakazanou permutacni matici P, lze shora omezit s(P)^n. Mezi hlavni vysledky patri dukaz, ze oba podily s(P)/c(P) i c(P)/S(P) jsou shora omezeny funkci polynomialni v k (k=pocet radku matice P), z cehoz plyne vylepseni obecneho horniho odhadu pro s(P). Dale jsme nasli matice, jejichz c(P) roste alespon kvadraticky s jejich velikosti. Clanek s vysledky sepsany J. Cibulkou ziskal druhe misto na SVOC a je zaslan k publikovani.
V zimnim semestru 2004/2005 jsme resili otazku, kolik bodu staci na prispendleni konecne mnoha oznameni konvexnich tvaru pevne umistenych na nastence, jestlize z kazdych 4 muzeme vybrat 3, ktere lze pripevnit (tj. propichnout) jednim spolecnym spendlikem. Soudi se, ze staci 3, ale horni odhad je mnohem vyssi (13). Na seminari jsme domnenku dokazali pro nektere specialni tvary (napr. usecky, jednotkove kruhy). Clanek o dosazenych vysledcich sepsali J. Kyncl a M. Tancer. Clanek je nyni uvazovan pro publikaci.
V letnim semestru 2003/2004 jsme resili nekolik otazek z Euklidovske Ramseyovske teorie. Mezi hlavni vysledky patri nalezeni (v prubehu semestru a v nasledujicich mesicich) nekolika ruznych prirozenych podminek na obarveni roviny 2 barvami zarucujici, ze kazdy trojuhelnik lze polozit (tj. posunout a natocit) tak, ze jeho vrcholy jsou potom obarveny jednou barvou. Mezi takovymi podminkami je napr. podminka, ze mnozina bodu obarvenych jednou z barev je uzavrena. Byla charakterizovana vsechna 'polygonalni (dlazdicova)' obarveni dvema barvami, pro ktera nelze nalezt rovnostranny jednotkovy trojuhelnik se vsemi vrcholy obarvenymi stejnou barvou. Vysledky sepsali Vit Jelinek, Jan Kyncl, Rudolf Stolar a Tomas Valla v clanku, ktery je uvazovan pro publikaci v Combinatorice.
V zimnim semestru 2003/2004 jsme resili nasledujici dva problemy:
- Snazime se urcit hodnotu funkce f(n) definovane jako maximalni cislo f takove, ze pri libovolnem rozmisteni n cervenych a n modrych bodu na obvodu kruznice lze najit nekrizici se cestu delky alespon f, jejiz kazda hrana je usecka spojujici cerveny bod s modrym.
- Snazime se charakterizovat grafy, ktere maji konfluentni nakresleni v rovine a najit algoritmus jejich rozpoznavani. Konfluentni nakresleni grafu je zobecneni rovinneho nakresleni. V konfluentnim nakresleni jsou vrcholy reprezentovany jako body v rovine a hrany jsou reprezentovany pomoci systemu krivek. Krivky se nesmi navzajem krizit, ale mohou se libovolne rozvetvovat a slevat, podobne jako zeleznicni trate s vyhybkami. Dva vrcholy jsou spojeny hranou, prave kdyz v konfluentnim nakresleni jsou prislusne dva body spojene hladkou krivkou.
V letnim semestru 2002/2003 jsme studovali problem rekonstrukce grafu na zaklade znalosti nekterych jeho indukovanych podgrafu. Necht H je pevne dany graf na k vrcholech a G=(V,E) je libovolny graf. Jako H-strukturu grafu G potom oznacime k-uniformni hypergraf na mnozine vrcholu V, jehoz hyperhrany jsou prave ty k-tice vrcholu, ktere v grafu G indukuji podgraf izomorfni s H. Pro ruzne grafy H jsme zkoumali slozitost nasledujici ulohy: na vstupu je dan hypergraf, rozhodnete, jestli je H-strukturou nejakeho grafu G. Ukazali jsme, ze pro nahodny graf H na k vrcholech je tato uloha NP-uplna s pravdepodobnosti, ktera se blizi jedne, pokud se k blizi k nekonecnu, navic je tato uloha NP-uplna pro dostatecne dlouhe cesty a pro nektere dalsi specialni tridy grafu. Vysledky ziskane na seminari sepsali Zdenek Dvorak a Vit Jelinek v clanku "On the complexity of the G-reconstruction problem", ktery byl prezentovan na konferenci ISAAC'05. (sepsal V. Jelinek)
V zimnim semestru 2002/2003 jsme zkoumali, jak rychle roste funkce f(n) definovana jako maximalni cislo f takove, ze kazdy geometricky graf na n vrcholech, ktery lze doplnit pridanim nejvyse f hran na uplny geometricky graf, obsahuje nekrizici se hamiltonovskou cestu. Bylo znamo, ze cislo f(n) je alespon 2 a mensi nez n/2. Na seminari jsme mj. ukazali, ze je f(n) roste alespon jako c krat odmocnina z n. Clanek o tomto a dalsich pribuznych vysledcich sepsali Jakub Cerny, Zdenek Dvorak, Vit Jelinek a Jan Kara. Clanek ziskal prvni misto ve SVOC a byl publikovan ve sborniku Graph Drawing 2003.
V letnim semestru 2001/2002 jsme pokracovali v tematu minuleho semestru (hrava orientovana barevnost). Clanek, ktery opet uspesne soutezil ve SVOC, sepsali Jakub Cerny, Zdenek Dvorak, Vit Jelinek, Jan Kara a Pavel Podbrdsky.
V zimnim semestru 2001/2002 se
Problemovy seminar z kombinatoriky konal poprve oficialne.
Jeho kod je DMI052. V tomto semestru jsme se zabyvali
otazkou zda lze omezit konstantou hravou barevnost orientovanych stromu.
Toto tvrzeni zatim umime ukazat pro disjunktni sjednoceni jakkoliv
orientovanych hvezd. Na druhou stranu jeste nezname odpoved ani v pripade
jednosmerne orientovanych cest. V reseni problemu
budeme pokracovat v letnim semestru.
[Hrava barevnost grafu je minimalni pocet barev pri kterem se podari
dany graf obarvit, jestlize jsou vrcholy grafu obarvovany
postupne dvema hraci, hraci se stridaji, v kazdem kroku si
hrac na tahu zvoli neobarveny vrchol a obarvi ho pripustnou
barvou, jeden z hracu (konstruktor) se snazi aby se podarilo
obarvit cely graf, druhy (destruktor) se mu v tom snazi zabranit.
Pripustna obarveni jsou takova, ze zadna hrana nespojuje stejne
obarvene vrcholy a v pripade orientovanych grafu navic
vsechny hrany s koncovymi vrcholy obarvenymi touz dvojici
barev jsou orientovany vzdy smerem ke stejne barve.]
V letnim semestru 2000/2001 se poprve (byt neoficialne) konal Problemovy seminar z kombinatoriky. Byla resena nasledujici otazka: V kolika nejvyse bodech se mohou protinat hranice jednoducheho k-uhelniku a jednoducheho l-uhelniku? Neni tezke nahlednout, ze odpoved je kl pokud k a l jsou suda cisla a k(l-1) pokud k je sude a l liche. Otevrenou otazkou zustava pripad kdy k i l jsou licha cisla. Opet neni tezke nahlednout, ze odpoved je nejmene (k-1)(l-1)+2 a nejvyse k(l-1). Podarilo se ukazat, ze dolni hranice je presna pokud alespon jedno z cisel k,l je mensi nez 7. Dale byl zlepsen horni odhad tak, ze rozdil mezi dolnim a hornim odhadem se zmensil priblizne o jednu sestinu. Clanek s temito vysledky sepsany sesti ucastniky seminare (Cerny, Kara, Kral, Podbrdsky, Sotakova, Samal) uspesne soutezil ve SVOC a vysel ve CMUC 44 (2003), 217-228.
Jan Kratochvil a Pavel Valtr.
Webmaster: kamweb@kam.mff.cuni.cz Modified: 28. 02. 2013