Univerza na Primorskem Fakulteta za matematiko, naravoslovje in informacijske tehnologije
-->
SI | EN

Nekateri problemi v hipergrafih, grafih, in igrah

natisni
Predstavitev projekta Project presentation

Predstavitev projekta

Naslov: Nekateri problemi v hipergrafih, grafih, in igrah

Vodja projekta: dr. Matjaž Krnc

Vodilna institucija v Sloveniji: UP FAMNIT

Partnerska institucija: Rutgers University

Financer projekta: Javna agencija za znanstvenoraziskovalno in inovacijsko dejavnost Republike Slovenije (ARIS)

Raziskovalno področje (ARIS): 1.07 - Računalniško intenzivne metode in aplikacije

Vrsta projekta: Znanstveno-raziskovalno sodelovanje med RS in ZDA

Trajanje projekta: 1. 7. 2022–30. 6. 2024

Opis projekta:

V okviru tega projekta se bomo posvetili reševanju naslednjih: Problem 1 (domneva Bi-SP). Problem 2 (O izogibnih poteh): Pot je izogibna, če lahko vsako obojestransko razširitev podaljšamo v induciran cikel. 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. Problem 4 (Deterministične grafične igre brez Nashevega ravnovesja): 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): 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.

Oddelek UP FAMNIT, v okviru katerega se izvaja projekt:

Oddelek za informacijske znanosti in tehnologije

Project presentationna vrh

Title: Certain problems in hypergraphs, graphs, and games

Principal investigator: dr. Matjaž Krnc

Leading institution in Slovenia: UP FAMNIT

Partner institution: Rutgers University

Funding organization: Slovenian Research and Innovation Agency (ARIS)

Research field (ARIS):  1.07 - Computer intensive methods and applications

Duration: 1. 7. 2022–30. 6. 2024

Description:

In the course of this project, we plan to focus on the following: Problem 1: The Bi-SP conjecture. Problem 2: On the avoidable paths. A path is called avoidable if every linear extension may be extended to an induced cycle. Problem 3: An efficient characterization of threshold 3-uniform hypergraphs. A hypergraph is said to be threshold if there exists a linear weight function on the vertices separating the independent sets from the dependent ones. Problem 4: Deterministic graphical games with no Nash equilibria. We plan to analyze the existence of deterministic graphical games that have no Nash equilibria in pure stationary strategies, with respect to additive effective payoffs. Problem 5: Exact transversals in graphs and hypergraphs. We plan to study the related exact transversal hypergraph operator, study conditions under which it is involutive, and examine connections with strong cliques in graphs and related concepts.

Department: 

Department of Information Sciences and Technologies