Aplikácie inverzných pologrúp v kombinatorike (projekt VEGA)
Cieľom projektu je štúdium inverzných pologrúp čiastočných automorfizmov kombinatorických štruktúr ako rozšírenie štandardne používaného pojmu grupy automorfizmov. Takýto prístup nám umožní aplikovať metódy čiastočných permutačných pologrúp na triedy kombinatorických štruktúr, ktoré majú iba veľmi málo alebo žiadne automorfizmy, a preto sa nedajú študovať tradičnými metódami permutačnej teórie grúp.
Zodpovední riešitelia: Robert Jajcay a Tatiana Jajcayová
Financovanie projektu: Vedecká grantová agentúra MŠVVaŠ SR a SAV, VEGA 1/0577/14
Obdobie riešenia projektu: 2014 - 2016
V teórii grafov existuje možstvo problémov odvíjajúcich sa od podmienky lokálnej regularity alebo symetrie, ktorú treba následne rozšíriť na celý graf. V našom projekte sa plánujeme venovať niekoľkým špecifickým problémom z teórie grafov, pre ktoré štúdium pologrúp čiastočných automorfizmov podľa nášho názoru sľubuje nové a originálne porozumenie.
Hypotéza rekonštrukcie grafov: Ak v je vrchol grafu G, podgraf G-v, ktory vznikne odstránením vrchola v a hrán s ním incidentných sa nazýva podgraf grafu G s vymazaným vrcholom v. Zoznam (vrátane opakovaní v prípade izomorfných podgrafov) všetkých podgrafov G-v, pre všetky v z V(G), sa nazýva balíkom podgrafov grafu G s vymazanými vrcholmi. Kelly a Ulam vo svojej slávnej hypotéze o jednoznačnej rekonstrukcii grafov predpokladajú, že každé dva grafy H a K s aspoň troma vrcholmi a identickými balíkmi podgrafov s vymazanými vrcholmi sú nevyhnutne izomorfné. Ich hypotéza zostáva napriek úsiliu mnohých matematikov aj po vyše 60 rokoch otvorená.
Vzájomne pseudo-podobné vrcholy: Dvojica vrcholov u,v grafu G sa nazýva pseudo-podobná, ak sú podgrafy G-u a G-v izomorfné, ale žiaden automorfizmus grafu G nie je rozšírením čiastočného izomorfizmu z G-u do G-v (neexistuje automorfizmus G, ktorý by zobrazil G-u na G-v).
Extremálne grafy s daným stupňom a priemerom alebo s daným stupňom a obvodom: Jedným z najdôležitejších problémov teórie grafov, ktorý má veľké množstvo aplikácií v navrhovaní zložitých prepájacích sietí, je úloha určenia najmenšieho priemeru pre grafy danej veľkosti a stupňa [Miller, Širáň, Moore graphs and beyond, 2005]. Priemer grafu je maximálna dĺžka najkratšej cesty medzi ktorýmikoľvek dvoma vrcholmi grafu G. Tento parameter je prirodzenou mierou efektívnosti alebo kompaktnosti siete. Problém klietok, v ktorom sa určuje veľkosť najmenšieho grafu daného stupňa a daného obvodu (dĺžky najkratšej kružnice), je komplementárny k problému stupňa a priemeru.