Šajna, Mateja; matematični kolokvij september 2005

Iz MaFiRaWiki

Sistemi ciklov: včeraj, danes, jutri -- na presečišču teorije grafov s teorijo kombinatoričnih načrtov

Mateja Šajna

University of Ottawa, Kanada

29. september 2005


V prvem delu predavanja bom predstavila začetke teorije kombinatoričnih načrtov, ki sovpada z zgodovino sistemov ciklov. Srečali se bomo s Plückerjem in prvimi načrti, ki jih je odkril v algebraični geometriji; z Woolhousom in njegovim nagradnimprašanjem o obstoju Steinerjevih sistemov, ki je še danes daleč od rešitve; ter s Kirkmanom in njegovim znamenitim problemom petnajstih šolark, ki je desetletja buril duhove.

V drugem delu se bomo seznanili s sistemi ciklov oziroma problemom dekompozicije polnih grafov (in polnih grafov z odstranjenim 1-faktorjem) na cikle iste dolžine. Za cikle dolžine tri je problem rešil že Kirkman sredi 19. stoletja, v vsej splošnosti pa smo ga rešili Alspach, Gavlas in avtorica šele pred nekaj leti, čeprav so se z njim ukvarjali več kot trideset let. Na kratko bom orisala dokaz izreka, ki pravi, da so očitni potrebni aritmetični pogoji za obstoj dekompozicije polnega grafa (ali polnega grafa z odstranjenim 1-faktorjem) z n točkami na cikle dolžine m tudi zadostni. Predstavila bom tudi primer uporabe dekompozicije polnega grafa na cikle pri načrtovanju poskusov v mikrobiologiji.

V zadnjem delu se bomo srečali z nekaterimi sorodnimi problemi, rešenimi in nerešenimi, med njimi s problemoma obstoja sistemov usmerjenih ciklov in dekompozicije polnih grafov na cikle predpisanih (različnih) dolžin, ter z znamenitim problemom iz Oberwolfacha.

Osebna orodja