Raziskovalni projekt (so)financira Javna agencija za raziskovalno dejavnost RS.
Članica UL: Fakulteta za matematiko in fiziko
Šifra projekta: N1-0355
Naziv projekta: Prirejanja, transverzale in hipergrafi
Obdobje: 1. 8. 2024 - 31. 7. 2027
Letni obseg: 0,67 FTE, cenovna kategorija: B
Vodja: Csilla Bujtás
Veda: Naravoslovje
Sodelujoče RO, sestava projektne skupine in bibliografske reference
Vsebinski opis projekta:
Hipergrafi so sistemi množic nad osnovno množico vozlišč. Osrednji temi tega predloga sta najmanjše transverzale in največja prirejanja v hipergrafu H. Transverzala je množica vozlišč, ki seka vsako povezavo hipergrafa H, prirejanje pa je množica neodvisnih povezav. Hipergraf H je k-uniformen, če vsaka povezava vsebuje k vozlišč. Prvi del projekta se osredotoča na iskanje zgornjih mej transverzalnega števila k-uniformnega hipergrafa, predvsem glede na njegovo število povezav in število vozlišč; drugi del pa se osredotoča na medsebojno vplivanje med transverzalnim številom in številom prirejanja uniformnih hipergrafov. Posebni cilji projekta so naslednji:
(O-1) Zgornje meje transverzalnih števil k-uniformnih hipergrafov.
Za vsak k >1 je iskanje najmanjše transverzale NP-težak problem v razredu k-uniformnih hipergrafov. Zato sta določitev zgornjih mej transverzalnega števila τ(H) in oblikovanje algoritmov s polinomskim časom, ki dajejo dovolj majhne transverzale, pomembna praktična in teoretična problema. Osredotočili se bomo na zgornje meje, zapisane v obliki τ(H)≤ c_k (n+m), kjer je c_k konstanta, H pa je k-uniformni hipergraf z n vozlišči in m povezavami. Natančne vrednosti konstante c_k so bile dokazane za k=2, 3 in 4 okoli leta 1990. Čeprav so se poskusi določitve natančnih vrednosti za k=5 in 6 nadaljevali v zadnjih treh desetletjih, še vedno nimamo točnih rezultatov za katerikoli k >4. Prvi cilj predlaganega projekta je izboljšati obstoječe rezultate glede zgornjih mej transverzalnih števil k-uniformnih hipergrafov.
(O-2) Zgornje meje transverzalnih števil k-uniformnih hipergrafov pod posebnimi pogoji.
Medtem ko cilj (O-1) zahteva zgornje meje za celoten razred k-uniformnih hipergrafov, se več zanimivih vprašanj in domnev nanaša na zgornje meje, kadar se obravnavajo samo hipergrafi s posebnimi lastnostmi. Najpomembnejši podrazredi, ki jih nameravamo raziskati, so hipergrafi, ki imajo isto šptevilo povezav kot vozlišč; linearni hipergrafi; hipergrafi odprtih okolic in hipergrafi zaprtih okoli. Ta cilj je povezan tudi s Thomassé-Yeo domnevo, ki napoveduje, da τ(H)≤4n/11 velja za vsak 5-uniformni hipergraf H z n vozlišči in n povezavami.
(O-3) Zgornje meje za razmerje med transverzalnim in ujemajočim se številom trikotniških hipergrafov.
Ta cilj je povezan z 42 let staro Tuzejevo domnevo, ki je v klasični knjigi Bondyja in Murtyja navedena med 100 najpomembnejšimi domnevami o problemih teorije grafov. Čeprav zadeva enostavne grafe, je problem mogoče modelirati s primerjavo števil prirejanja in transverzalnih števil (določenih) 3-uniformnih hipergrafov. Omenjeno razmerje τ(H)/ν(H) naj bi bilo največ 2, medtem ko je najboljša ugotovljena zgornja meja 66/23. V zvezi s Tuzovo domnevo je situacija z grafi brez K_4 posebna. Ni znan noben primer z τ(H)=2ν(H). Vendar pa verjetnostni pristop pokaže, da za vsak pozitiven ϵ obstaja graf G brez K_4, ki izpolnjuje τ(H)>(2-ϵ)ν(H) ustreznega trikotniškega hipergrafa H. V načrtovanih raziskavah se bomo osredotočili na trikotniške hipergrafe, pridobljene iz grafov brez K_4, in izboljšali zgornjo mejo 66/23.
(O-4) Karakterizacija trikotniških hipergrafov, ki izpolnjujejo τ(H)=3ν(H).
Vsak k-uniformni hipergraf H izpolnjuje τ(H)≤kν(H), za vsak k≥2 pa so znani tudi natančni primeri. Še vedno pa ni znana karakterizacija ekstremnih hipergrafov, če je k>2. Naš cilj je zapolniti to vrzel, da bi dosegli boljše razumevanje glede maksimalnih ujemanj v hipergrafih na splošno.
