Raziskovalni projekt (so)financira Javna agencija za raziskovalno dejavnost RS.
Članica UL: Fakulteta za matematiko in fiziko
Šifra projekta: N1-0095
Naziv projekta: Turanova števila in ekstremalni problemi za poti
Obdobje: 1. 10. 2019 - 30. 9. 2022
Letni obseg: 0,52 FTE cenovna kategorija: B
Vodja: Klavžar Sandi
Veda: Naravoslovje
Vsebinski opis projekta:
Glavni objekti našega raziskovanja so ekstremalni kombinatorični problemi. Načrtujemo raziskovanje več tipov takih problemov s poudarkom na problemih Turánovega tipa in na sorodnih ekstremalnih problemih o poteh. Razumevanje ekstremalnih parametrov različnih struktur, ki izvirajo iz lokalnih lastnosti, pomaga pri razumevanju globalnih lastnosti struktur. Poti v grafih sodijo med najbolj bazične strukture, ki tvorijo sestavne dele bolj kompleksnih struktur. Raziskovanje različnih ekstremalnih parametrov glede na poti lahko porodi informacijo o vedenju drugih struktur.
Prva glavna tema, ki jo bomo raziskovali v tem projektu, so problemi Turánovega tipa. Naštejmo pet sklopov vprašanj, ki jih nameravamo raziskovati in so vzporedna s klasičnim Turánovim vprašanjem. (i) Posplošena Turánova števila. Tu je problem preštevanje podgrafov v grafu, pri čemer prepovemo druge grafe kot podgrafe. (ii) Turánova števila Bergeovih hipergrafov. Glavna invarianta, ki jo bomo raziskovali, je Turánovo število od Berge-F. Slednji je definiran kot največje možno število hiperpovezav v hipergrafu, ki je brez Berge-F. (iii) Turánova števila usmerjenih grafov. Turánov problem za množico usmerjenih grafov H sprašuje po največjem številu povezav, ki jih lahko premore usmerjen graf, če ne vsebuje nobenega H kot usmerjenega podgrafa. (iv) Turánova števila z omejitvami na stopnje. V začetku 1990ih je Albertson dokazal, da graf ali njegov komplement na vsaj šestih vozliščih vsebuje tak trikotnik, da imata dve njegovi vozlišči isto stopnjo. Načrtujemo raziskovanje tega fenomena v različnih okoliščinah. (v) Vozliščna Turánova števila v hiperkockah. Poskusili bomo razviti tehnike, ki so bile izumljene za probleme prepovedanih delnih urejenosti, za reševanje problemov na tem področju.
Druga glavna tema predlaganega projekta so ekstremalni problemi o poteh na grafih. Številni pomembni grafovski problemi sprašujejo po (najmanjši) množici vozlišč S grafa G, tako da G − S ne vsebuje grafa iz dane družine grafov F kot podgraf. Na primer, število vozliščnega pokritja je že tak problem. Glavne teme, ki jih nameravamo raziskovati, so naslednje. (i) Vozliščno pokritje k-poti. Načrtujemo nadaljevanje raziskovanja vozliščnih pokritij k-poti in razširiti to raziskovanje na probleme ciljanja različnih vrst poti v grafih. (ii) Koncepti sorodni ciljanju poti. Načrtujemo študij povezavne inačice problema vozliščnih pokritij k-poti in tudi študij vozliščnih pokritij k-poti za druge vrste poti. (iii) Sočasno izogibanje najkrajšim potem. Raziskovali bomo problem vozlišč v splošni legi in v posebnem iskali povezave med tem novim konceptom in nekaterimi dobro znanimi koncepti. (iv) Ekstremalni problemi o sistemih poti. Predlagamo študij družine novih modelov, ki so skupna posplošitev nekaterih grafovskih problemov in problemov razporejanj pakiranjih. Ker gre pri tem modelu za skupno posplošitev omrežnih pretokov in razporeditev pakiranj, načrtujemo uporabo različnih idej in metod iz teh klasičnih področij.
