Nekateri problemi na hipergrafih, grafih ter igrah / Certain problems in hypergraphs, graphs, and games

Naslov: Nekateri problemi na hipergrafih, grafih ter igrah / Certain problems in hypergraphs, graphs, and games

Oznaka projekta: BI-US: 2019-2021:018

Koordinator (vodilni partner): 
UP Famnit, Koper

Partnerske institucije: Rutgers University

Vodja projekta na UP FAMNIT: 
dr. Krnc Matjaž

Oddelek UP FAMNIT, v okviru katerega se izvaja projekt: 
Oddelek za informacijske znanosti in tehnologije

Financer projekta: 
Javna agencija RS za raziskovalno dejavnost (ARRS)

Raziskovalno področje (ARRS): 
1.01 Matematika

Trajanje projekta: 
1.10.2019 - 30.9.2021

Opis projekta: 

V okviru tega projekta se bomo posvetili reševanju naslednjih problemov. Problem 1: Igra jemanja zlata Naj bo T drevo, kjer je vsakemu vozlišču v iz T prirejena količina zlata, tj. pozitivno celo število wt(v). Dva igralca, Alenka ter Bine, zaporedoma odstranjujeta liste iz drevesa T, pri čemer v vsaki potezi igralec obdrži tudi pripadajočo količino zlata iz odstranjenega lista. Zmaga igralec ki ima na koncu več zlata. Micek ter Walczak (2011) sta dokazala, da si lahko v drevesu na sodo mnogo vozliščih Alenka vedno zagotovi izkupiček vsaj četrtine celotnega zlata v T. Postavili so tudi hipotezo, da na takih drevesih Alenka nikoli ne izgubi, tj. si lahko zagotovi vsaj polovico zlata. V tem projektu nameravamo preučevati nekatere variante teh iger, vključno s posplošitvijo igre na družino tetivnih grafov, ter algoritmičnim vprašanjem iskanja optimalnih strategij. Problem 2: O izogibnih poteh Pot je izogibna, če lahko vsako obojestransko razširitev podaljšamo v induciran cikel. Koncept izogibnih poti je bil vpeljan v Beisegel, Chudnovsky, Gurvich, Milanič, Servatius (2019), kjer so avtorji postavili hipotezo, da lahko v vsakem grafu najdemo izogibno pot, če le ta graf premore inducirano pot enake dolžine. Hipoteza o izogibnih poteh je bila potrjena od Bonamy, Defrain, Hatzel, Thiebaut (2019). V tem projektu se bomo osredotočili na nekatere povezane probleme. Problem 3: Učinkovita karakterizacija pragovno 3-uniformnih hipergrafov Hipergrafu pravimo da je pragoven če domeni vozlišč obstaja linearna funkcija uteži ki ločuje neodvisne množice od odvisnih. S pomočjo linearnega programiranja lahko sicer pragovne hipergrafe prepoznavamo v polinomskem času, kljub temu pa ostaja pomembno vprašanje če lahko najdemo kombinatorični algoritem s podobno učinkovitostjo. Omenjen problem je že rešen za primer 2-uniformnih hipergrafov (tj. za primer grafov). Nameravamo si ogledati splošnejši problem za k-uniformne hipergrafe, kjer je k večji od 2. Problem 4: Deterministične grafične igre brez Nashevega ravnovesja Primer deterministične grafične igre za tri igralce, brez Nashovega ravnovesja v smislu čistih stacionarnih strategij je bil nedavno najden, glej Boros, Gurvich, Milanič, Oudalov, Vičič (2018). Tekom projekta bomo poskusili razrešiti vprašanje obstoja nekaterih podobnih determinističnih grafičnih iger brez Nashovega ravnovesja v smislu čistih stacionarnih strategij. Problem 5: Natančne transverzale v grafih in hipergrafih Znano je da je, za razred Spernerjevih hipergrafov, hipergrafovski transverzalni operator involucija. Naš namen je preučiti podoben hipergrafovski transverzalni operator, ugotoviti pod katerimi pogoji je le-ta involucija, ter si ogledati morebitne povezave s krepkimi klikami v grafih, ter druge sorodne koncepte.