Neodvisnost in dominacija v strukturiranih grafovskih razredih

V zadnjih nekaj desetletjih je teorija grafov zrasla v eno od osrednjih področij sodobnih znanstvenih raziskav v matematiki. Za njen bliskoviti razvoj je deloma zaslužen naraščajoči pomen tehnologije in omrežij, torej področij, kjer ima teorija grafov številne aplikacije, kot zrelo matematično disciplino pa so jo uveljavili predvsem številni originalni in tehtni prispevki nekaterih najuglednejših raziskovalcev. Skozi vsa ta leta je slovenska šola teorije grafov igrala eno ključnih vlog v globalnem razvoju področja. Njena mednarodna prepoznavnost je dosegla stopnjo, primerljivo s sorodnimi ustanovami iz tehnološko najbolj razvitih svetovnih držav.   Predlagani projekt je osredotočen na strukturno in algoritmično teorijo grafov, s poudarkom na izboru nekaterih klasičnih in sodobnih obetavnih raziskovalnih smeri na preseku teorije grafov in teoretičnega računalništva: problem neodvisne množice v hereditarnih grafovskih razredih; študij cene povezanosti za probleme neodvisnosti in dominacije; študij grafovskih razredov, definiranih preko klik in neodvisnih množic, vključno s CIS grafi in ekvistabilnimi grafi; študij grafovskih razredov, definiranih preko problemov dominacije; računska zahtevnost in algoritmi za probleme dominacije. Poleg naštetih področij bo projekt vključeval tudi raziskovalno delo na drugih vejah teorije grafov, vključno z algebraično teorijo grafov. Opomba: V angleškem naslovu je prišlo do napake. Pravilni naslov se glasi: "Independence and domination in structured graph classes".

Poleg umetnosti je matematika edini univerzalni jezik medčloveške komunikacije, ki je prisoten v vseh razvitih civilizacijah. Abstraktne matematične teorije se uporabljajo tako v naravoslovnih znanostih, inženirstvu in računalniških znanostih, kot tudi v socioloških, ekonomskih in biomedicinskih znanostih. Vloga matematike na nekaterih trenutno najbolj pomembnih področij človekovega udejstvovanja, kot so varno komuniciranje, varovanje podatkov in dekodiranje človeškega genoma, dokazuje, da je njen vpliv na same osnove moderne družbe tako bistven, da si ga v preteklosti nismo upali niti zamisliti.   Predlagani projekt je v samem vrhu dandanašnjih raziskav v teoriji grafov in njenih aplikacijah v drugih znanostih. Pomembnost naših raziskovalnih ciljev je vidna iz bibliografij članov projektne skupine, njihove citiranosti in iz njihovih številnih povezav z raziskovalci v tujini. Rezultati tega projekta bodo predstavljali velik prispevek k razvoju teorije grafov in sorodnih področij. Ta prispevek pa bo seveda dal dodaten zagon slovenski šoli teorije grafov.

Glede na socialne in ekonomske spremembe v zadnjih dvajsetih letih je obstoj slovenskega naroda kot razvite evropske nacije odvisen od tega, ali bomo znali ohraniti naš jezik in našo kulturo, kot tudi od tega, ali bomo imeli visoko izobraženo prebivalstvo. Slovenija potrebuje hitrejši tehnološki razvoj. To pa zahteva še intenzivnejše vključevanje matematike tako v znanstvene raziskave kot tudi v izobraževanje. Naša skupina ima na tem področju že veliko izkušenj in bo s tovrstnim delom nadaljevala tudi v okviru predlaganega projekta. Kljub dejstvu, da je predlagano raziskovanje primarno teoretično narave, pričakujemo, da bo vsaj del dobljenih rezultatov našel aplikacije v razvoju algoritmov za probleme realnega življenja, ki jih je moč modelirati s problemi neodvisnosti in dominacije (glej 11. razdelek). Raziskovalna skupina bo v celoti spoštovala načela "Evropske listine za raziskovalce" in "Kodeks ravnanja pri zaposlovanju raziskovalcev" v skladu z javnim ozaveščenjem pomena raziskovalcev in raziskovalne dejavnosti. Raziskovalna skupina organizira številne formalne in neformalne aktivnosti, ki so namenjene širši javnosti in ne-specialistom na raziskovalnem področju matematike.   Raziskovalna skupina bo poskrbela, da bodo raziskovalne dejavnosti predstavljene širši javnosti. S tem bo izboljšala javno razumevanje znanosti in raziskav. Raziskovalna skupina se zaveda, da bo neposredno sodelovanje z javnostjo pomagalo raziskovalcem pri boljšem razumevanju interesa javnosti pri prioritetnih nalogah znanosti in tehnologije. S predlaganim projektom bo raziskovalna skupina prispevala h krepitvi javnega priznanja raziskovalcev ter pomena njihove družbene vloge.   V tem smislu raziskovalna skupina že šest let organizira matematične večere "Famnitovi izleti v matematično vesolje" (tretji teden v mesecu) namenjene ne-strokovnjakom na področju matematike in širši javnosti, ki jih zanima znanost (od otrok do odraslih). Predavanja so usmerjena v poljudnoznanstevno razlago matematike z elementi sodobnih problemov in v predstavitev vloge matematike v sodobni tehnologiji in vsakdanjem življenju (glej http://matematicni-izleti.famnit.upr.si).