Madžarsko-slovenski projekt, kjer Madžarska znanstvena raziskovalna fundacija (OTKA - Országos Tudományos Kutatási Alapprogramok) deluje kot vodilna agencija.

Vodja projekta: prof. dr. Sandi Klavžar

Naslov projekta: Kombinatorični problemi s poudarkom na igrah

Šifra projekta: N1-0043

Veda: Naravoslovno matematične vede

Trajanje projekta: 01. 01. 2016 - 31. 12. 2018.

Cenovna kategorija: B

Letni obseg projekta: 0,39 FTE

Vodilna agencija: Madžarska znanstvena raziskovalna fundacija (OTKA - Országos Tudományos Kutatási Alapprogramok)

Projekt sofinancira: Javna agencija Republike Slovenije za raziskovalno dejavnost.

Vsebinski opis projekta:

Glavni cilj projekta je raziskovanje iger povezanih z grafi in sistemi množic. Načrtujemo raziskovanje več tipov takih iger s poudarkom na igri dominacije. Iz različnih vidikov bomo študirali tudi širše področje iger nasičenosti. Raziskovanje igralnih inačic klasičnih raziskovalnih področij hkrati vodi tudi k boljšemu razumevanju originalnega področja in k novim rezultatom o njem, zato bomo raziskovali tudi pripadajoče klasične probleme.

Osrednja tema predlaganega projekta je igra dominacije. Dominacija je področje teorije grafov, ki je uporabna na številnih praktičnih področjih. Njegova igralna inačica je bila vpeljana šele pred petimi leti, a ima že bogato literaturo, ki med rezultati razkriva številne presenetljive fenomene. Načrtujemo raziskovanje zgornjih meja za igralno dominacijsko število, kritičnih konceptov, kot tudi nadaljnjih iger povezanih z dominacijsko igro. Slednje igre vključujejo totalno inačico dominacijske igre, disjuktno dominacijo in več vrst iger na hipergrafih. Dominacijsko igro bomo postavili v širši okvir iger nasičenosti, to je tistih pozicijskih iger, v katerih je pomembna le dolžina odigrane igre. Igra dominacije je očitno poseben primer igre nasičenosti. Načrtujemo raziskovanje iger nasičenosti, ki so definirane z navzdol zaprtimi družinami množic, nadalje igre, v katerih pameten igralec igra proti naključnemu igralcu,  raziskovali bomo tudi kombinatorično iskanje na teh igrah. Poleg iger nasičenosti bomo obravnavali tudi igre pakiranja v zaboje in t.i. igro prodajanja melone. Gre za igre, ki so tesno povezane s problemi kombinatorične optimizacije.

Ker so klasična področja in njihove pripadajoče igre naravno prepleteni, bomo študirali tudi teme iz teorije dominacije. Osredotočili se bomo na nedavno vpeljano tehniko dokazovanja, ki uporablja barvanja vozlišč in njihovo utežitev (s tem spominja na tehniko "naboja" iz teorije barvanja grafov), ki je že pripeljala do novih rezultatov o klasičnem dominantnem številu in 2-dominantnem številu. Nadalje bomo raziskovali tudi k-dominacijo, električno dominacijo, dominacijska zaporedja v grafih, dominacijo v hipergrafih, kot tudi transverzale, neodvisne množice in modele barvanja.

Tako slovenska kot tudi madžarska ekipa raziskovalcev vključenih v projekt premoreta globok vpogled v teme, navedene v raziskovalnem predlogu. Po drugi strani sta raziskovalni skupini dosedaj delovali v različnih smereh in imata različne izhodiščne vpoglede. To se zdi nadvse pomembno za uspeh projekta. Naj tu poudarimo le eno izmed teh razlik. Slovenska skupina ima široke izkušnje v računalniško podprtem raziskovanju. Ker so mnogi izmed kombinatoričnih problemov pretežki, da bi jih rešili eksaktno, so aproksimacijske rešitve in/ali približne rešitve zelo pomembne. Računalniki nadalje omogočajo prvi in pogosto ključen vpogled v težke probleme, ki potem omogoča razvoj ustrezne matematične teorije.

Člani obeh raziskovalnih ekip so objavili veliko število člankov, povezanih s temami iz raziskovalnega načrta. Nekatere izmed teh tem so bile celo vpeljane z njihove strani in nadalje raziskovane s strani drugih avtorjev. Poleg tega so člani projektnih ekip nedavno razvili nove metode raziskovanja, ki so bile tudi že uporabljene v nadaljnjih raziskavah s strani drugih raziskovalcev. Zato smo prepričani, da bo predlagani projekt prinesel nova dognanja ter tudi obširen razvoj predlaganih tematik.

Sestava projektne skupine: povezava na SICRIS

Bibliografske reference: povezava na SICRIS