Sek­cja Struk­tu­ral­nej Teo­rii Gra­fów dzia­ła pod opie­ką dr Moni­ki Pil­śniak i zaj­mu­je się otwar­ty­mi pro­ble­ma­mi mię­dzy inny­mi z dzie­dzi­ny kolo­ro­wań prze­ła­mu­ją­cych auto­mor­fi­zmy w gra­fie oraz podzia­łów gra­fów. Zagad­nie­nie, któ­rym zaj­mu­je­my się ostat­nio, to kolo­ro­wa­nie kra­wę­dzio­we pro­duk­tów pro­ste­go i sil­ne­go, prze­ła­mu­ją­ce automorfizmy.

Defi­ni­cja. Niech będą wierz­choł­ka­mi gra­fu . Mówi­my, że są w rela­cji , jeże­li speł­nio­ny jest waru­nek . Graf nazy­wa­my -cienkim, jeże­li żad­ne dwa wierz­choł­ki tego gra­fu nie są w rela­cji .

Podob­nie wierz­choł­ki są w rela­cji , jeże­li . Graf nazy­wa­my -cienkim, jeże­li żad­ne dwa wierz­choł­ki tego gra­fu nie są w rela­cji .

Celem naszych prac jest udo­wod­nie­nie hipo­te­zy w takiej posta­ci jak poni­żej (być może z tro­chę innym gór­nym ogra­ni­cze­niem na rząd gra­fu ).

Hipo­te­za. Niech będą gra­fa­mi -cienkimi (-cienkimi) speł­nia­ją­cy­mi warunek

Wów­czas indeks roz­róż­nia­ją­cy gra­fu (odpo­wied­nio ) jest rów­ny co naj­wy­żej 2, to zna­czy ist­nie­je takie kolo­ro­wa­nie kra­wę­dzi tego gra­fu dwo­ma kolo­ra­mi, że jedy­nym auto­mor­fi­zmem zacho­wu­ją­cym kolo­ry wszyst­kich kra­wę­dzi jest identyczność.

 


 

Poprzed­nim obiek­tem badań człon­ków koła był pro­blem podzia­łu gra­fów na żywo.

Defi­ni­cja. Mówi­my, że graf rzę­du jest dowol­nie podziel­ny, gdy dla dowol­ne­go cią­gu liczb natu­ral­nych takie­go, że , ist­nie­je podział zbio­ru wierz­choł­ków taki, że oraz graf indu­ko­wa­ny przez zbiór jest spój­ny, .
Graf jest dowol­nie podziel­ny na żywo, jeśli taki podział da się wyko­nać, wybie­ra­jąc kolej­no zbio­ry , przy czym w chwi­li zna­my tyl­ko licz­by .

Pro­blem gra­fów dowol­nie podziel­nych był roz­wa­ża­ny przez wie­lu mate­ma­ty­ków, rów­nież z Kate­dry Mate­ma­ty­ki Dys­kret­nej dzia­ła­ją­cej przy naszym wydzia­le. Są to mię­dzy inny­mi: Mariusz Woź­niak, Rafał Kali­now­ski, Moni­ka Pil­śniak, Irmi­na Zio­ło, Anto­ni Mar­czyk oraz Jakub Przy­by­ło. Szcze­gól­nie inte­re­su­ją­ce oka­za­ło się dla nas nastę­pu­ją­ce twierdzenie.

Twier­dze­nie (Kali­now­ski, 2015+). Jeśli jest gra­fem, któ­ry speł­nia jeden z poniż­szych dwóch warunków:

  1. , lub ,

wów­czas jest dowol­nie podziel­ny wte­dy i tyl­ko wte­dy, gdy jest dowol­nie podziel­ny na żywo.

W efek­cie badań nauko­wych pię­ciu człon­ków koła, wyka­za­li­śmy nastę­pu­ją­ce twierdzenie.

Twier­dze­nie (Bur­kot, Bed­narz, Dudzik, Kwa­śny, Paw­łow­ski, 2016+). Niech będzie gra­fem rzę­du i roz­mia­ru więk­sze­go niż . Wów­czas jest dowol­nie podziel­ny wte­dy i tyl­ko wte­dy, gdy jest dowol­nie podziel­ny na żywo.

Jest to więc uzu­peł­nie­nie twier­dze­nia udo­wod­nio­ne­go przez Kali­now­skie­go, praw­dzi­wy jest zatem poniż­szy wniosek.

Wnio­sek. Niech będzie gra­fem rzę­du i roz­mia­ru więk­sze­go niż . Wów­czas jest dowol­nie podziel­ny wte­dy i tyl­ko wte­dy, gdy jest dowol­nie podziel­ny na żywo.


Spo­tka­nia sek­cji odby­wa­ją się w czwart­ki o godzi­nie 12:00 w sali 325 w łącz­ni­ku A3-A4.