Oznaka poročila: ARRS-RPROJ-ZP-2015/124 H^SllI Sap® 0W ZAKLJUČNO POROČILO RAZISKOVALNEGA PROJEKTA A. PODATKI O RAZISKOVALNEM PROJEKTU 1.Osnovni podatki o raziskovalnem projektu Šifra projekta J1-4106 Naslov projekta Izredno veliki grafi in omrežja Vodja projekta 1931 Bojan Mohar Tip projekta J Temeljni projekt Obseg raziskovalnih ur 4537 Cenovni razred B Trajanje projekta 07.2011 - 06.2014 Nosilna raziskovalna organizacija 101 Inštitut za matematiko, fiziko in mehaniko Raziskovalne organizacije -soizvajalke 1554 Univerza v Ljubljani, Fakulteta za matematiko in fiziko 2547 Univerza v Mariboru, Fakulteta za naravoslovje in matematiko Raziskovalno področje po šifrantu ARRS 1 NARAVOSLOVJE 1.01 Matematika 1.01.05 Teorija grafov Družbenoekonomski cilj Naravoslovne vede - RiR financiran iz drugih virov (ne iz SUF) Raziskovalno področje po šifrantu FOS 1 Naravoslovne vede 1.01 Matematika B. REZULTATI IN DOSEŽKI RAZISKOVALNEGA PROJEKTA 2.Povzetek raziskovalnega projekta1 SLO Glavna tema projekta je bil študij zelo velikih grafov in matematičnih orodij za delo z zelo velikimi objekti. Gre za bazične raziskave, katerih namen je razviti matematična orodja za delo z velikimi podatkovnimi strukturami. Zanimal nas je odnos med lokalnimi in globalnimi lastnostmi skozi koncepte, kot so limite grafov in konvergenca zaporedij končnih grafov, naključna omrežja in geometrijski modeli, povezani z velikimi grafi. Dobljeni rezultati so v glavnem teoretični in se navezujejo na strukturne, algebrajske in algoritmične aspekte. Ena od glavnih tematik je bil študij lastnih vrednosti velikih grafov, obravnavali pa smo tudi lastnosti družin grafov s prepovedanimi minorji, algoritmične probleme presečnih grafov in verjetnostne algoritme, ki temeljijo na uporabi lokalnih lastnosti. ANG_ Our main concern is the study of very large graphs. Although this is a purely theoretical research, one of the main motivations comes from the need to develop mathematical tools to work with large data sets. The prevailing theme is the relationship between local and global properties through concepts like graph limits and convergence, random networks, and geometric models associated to large graphs. Results related to structural, algebraic, and algorithmic aspects of such large graphs have been obtained. In particular, we have studied eigenvalues of graphs, families of graphs with forbidden minors, algorithmic problems in large intersection graphs, and probabilistic algorithms based on local observations. 3.Poročilo o realizaciji predloženega programa dela na raziskovalnem projektu2 Raziskave velikih grafov in omrežij so v pionirski fazi. Njihov pomen se v zadnjem desetletju kaže tako v teoretičnem pristopu kot tudi v aplikacijah (obdelava velikih količin podatkov, sociološka omrežja, v prihodnosti tudi omrežna zgradba možganov). V raziskavi obdelujemo probleme, ki se pokažejo kot pomembni pri analizi velikih struktur. Eno od področij so limite grafov, kjer smo se vključli v tok novih spoznanj na tem področju. Predvsem smo se posvetili nekaterim algebrajskim in geometrijskim problemom, ki se pojavljajo pri analizi velikih omrežij. Ker gre za novo področje raziskovanja, smo se v začetku raziskav seznanjali z obstoječo literaturo in razvili nekaj preliminarnih rezultatov. Pomemben pojem pri študiju velikih omrežij so algebrajske lastnosti, predvsem lastne vrednosti prirejenih Laplaceovih matrik. V tem kontekstu smo objavili vrsto člankov, npr. Many large eigenvalues in sparse graphs, ki je izšel v European J. on Combinatorics. V tem delu je dokazana groba karakterizacija obstoja velikega števila velikih lastnih vrednosti v redkih grafih (npr. v poljubnih družinah grafov, ki so zaprte za minorje). Druga članka na tem področju sta Eigenvalues of graphs with vertices of large degree at distance three apart (avtorji B. Mohar, A. Sheikh Ahmady, R.P. Singh), ki je bil objavljen na Linear Algebra and its Applications, in članek Spectrally degenerate graphs: Hereditary case (avtorja Z. Dvorak, B. Mohar), objavljen v Journal of Combinatorial Theory, Series B. Ključna tema projekta je koncept limite grafov, o čemer nosilec projekta pripravlja tudi učbenik. Preliminarno, zgoščeno verzijo rezultatov s področja grafovskih limit je nosilec pripravil kot poglavje za knjigo Handbook of Graph Theory, Second Edition, Jonathan L. Gross, Jay Yellen, and Ping Zhang (Eds.), CRC Press. To poglavje je bilo dodano v drugo izdajo (2013) te popularne monografije iz teorije grafov na povabilo urednikov, saj dokaj nova teorija grafovskih limit postaja vse pomembnejše področje raziskav. V projektu smo dobili pomembne nove rezultate tudi v geometrijski interpretaciji zelo velikih grafov in zato bomo v nadaljevanju povedali nekaj več o tem. V skupnem članku s kolegi iz Belgije (Cabello, Cardinal in Langermann) smo določili računsko zahtevnost iskanja maksimalne klike v grafu presekov daljic. Problem sta zastavila Kratochvil in Nešetril in je ostal nerešen polnih dvajset let. Tudi na področju grafov presekov smo napisali članek (avtorja S. Cabello in P. Giannopoulos, ki je bil sprejet na ACM Symposium on Computational Geometry 2013 in Algorithmica. V tem članku obravnavamo problem računanja najmanjše podmnožice podanih krivulj, da bosta dve dani točki še vedno ločeni. Pokazali smo, da je jezik grafov presekov krivulj z dodatno strukturo grupe pravo orodje za reševanje tega problema v polinomskem času. S sodelavci v Čilu smo proučevali problem iskanje največje neodvisne množice v grafu presekov intervalov na premici, pri modelu kjer so intervali podani v tok podatkov in imamo majhen dodatni spomin. Članek Interval Selection in the Streaming Model (soavtorja Cabello in Perez-Lantero) je bil poslan v objavo. Raziskovali smo gostoto povezav naslednjega neskončnega grafa, definiranega za poljubni večkotnik P: množica vozlišč je P, med dvema vozliščema pa je povezava natanko tedaj, ko je eno vozlišče vidno iz drugega (in obratno). Ekvivalentno, zanimala nas je verjetnost, da sta dve naključni točki poligona medsebojno vidni. Problem se je prvič pojavil v kontekstu problema geometrijske optimizacije: radi bi poiskali konveksen poligon z največjo ploščino znotraj danega poligona. Našli smo ocene, ki povezujejo verjetnost, da ste dve točki poligona medsebojno vidni, in preko tega rezultata določili velikost največjega konveksnega poligona. S pomočjo teh rezultatov smo našli naključnostni algoritem, ki daje skoraj optimalno rešitev v skoraj optimalnem času. Naši rezultati so zbrani v članku Peeling potatoes near-optimally in near-linear time (avtorji S. Cabello, J. Cibulka, J. Kyncl, M. Saumell and P. Valtr), ki je bil sprejet na ACM Symposium on Computational Geometry 2015. Na področju vizualizacije grafov smo pokazali, da je problem računanja aproksimacije prekrižnega števila težji, kot smo mislili prej. Rezultat te raziskove je bil objavljen kot [S. Cabello, Hardness of approximation for crossing numbers, Discrete and Computational Geometry]. S kolegi iz ZDA smo raziskovali 1-ravninske grafe. Graf je 1-ravninski, če ga lahko narišemo v ravnini tako, da ima vsaka povezava največ eno križanje. Prepoznavanje 1-ravninskih grafov je NP-težak problem. V članku [M. J. Bannister, S. Cabello, D. Eppstein: Parameterized Complexity of 1-Planarity, objavljen na WADS 2013] smo obravnavali problem prepoznavanja 1-ravninskih grafov v polinomskem času za posebne družine grafov z vidika parametrične zahtevnosti. Izbor objav, ki so povezane s problemi raziskovalnega projekta: 1. B. Mohar, A. Sheikh Ahmady, R. Singh, Eigenvalues of graphs with vertices of large degree at distance three apart, Linear Algebra Appl. 436 (2012) 4342-4347. 2. B. Mohar, Graph Limits, Section 8.5, Handbook of Graph Theory, Second Edition, J.L. Gross, J. Yellen, P. Zhang (Eds.), Chapman and Hall/CRC, 2013, pp. 1038-1057. 3. Bojan Mohar, Many large eigenvalues in sparse graphs, Eur. J. Combin. 34 (2013) 11251129. 4. Zdenek Dvorak, Bojan Mohar, Robert Samal, Star chromatic index, J. Graph Theory 72 (2013) 313-326. 5. Sergio Cabello, Jean Cardinal, Stefan Langerman, The Clique Problem in Ray Intersection Graphs. Discrete & Computational Geometry 50(3): 771-783 (2013) 6. Sergio Cabello, Hardness of approximation for crossing numbers, Discrete & Computational Geometry 49 (2013) 348-358 7. Michael J. Bannister, Sergio Cabello, D. Eppstein, Parameterized complexity of 1-planarity. Algorithms and Data Structures (WADS 2013), LNCS 8037. 8. Matt DeVos, Zdenek Dvorak, Jacob Fox, Jessica McDonald, Bojan Mohar, Diego Scheide: A minimum degree condition forcing complete graph immersion. Combinatorica 34(3): 279-298 (2014) 9. Sergio Cabello, Josef Cibulka, Jan Kyncl, Maria Saumell and Pavel Valtr, Peeling potatoes near-optimally in near-linear time, Symposium on Computational Geometry 2014: 224232. 10. Sergio Cabello, Panos Giannopoulos, The complexity of separating points in the plane, sprejeto v Algorithmica. 11. Matt DeVos, Bojan Mohar, Small separations in vertex transitive graphs, poslano v objavo v Forum Math. Sigma. 12. Sergio Cabello, Pablo Perez-Lantero, Interval Selection in the Streaming Model, poslano v objavo, dostopen na http://arxiv.org/abs/1501.02285 4.Ocena stopnje realizacije programa dela na raziskovalnem projektu in zastavljenih raziskovalnih ciljev3 Delo na raziskavah je potekalo po pričakovanjih. Pri obravnavi izredno velikih grafov se pojavlja potreba po slučajni izbiri in zato smo raziskovali tudi verjetnostne algoritme in lastnosti slučajnih grafov v različnih geometrijskih modelih. Ukvarjali se smo s porazdelitvijo lastnih vrednosti izredno velikih grafov. Dobili smo pomembne in zanimive nove rezultate s področja izredno velikih grafov in omrežij in smo objavili več člankov na tem področju. Z dobljenimi in objavleni rezultati smo zadovoljni tako kvantitativno kot tudi kvalitativno. 5.Utemeljitev morebitnih sprememb programa raziskovalnega projekta oziroma sprememb, povečanja ali zmanjšanja sestave projektne skupine4 Ni sprememb. 6.Najpomembnejši znanstveni rezultati projektne skupine5 Znanstveni dosežek 1. COBISS ID 16199769 Vir: COBISS.SI Naslov SLO Degenerirana in zvezdna barvanja grafov na ploskvah ANG Degenerate and star colorings of graphs on surfaces Opis SLO V članku so podane zgornje meje za degenerirano in zvezdno kromatično število in za njuno skupno posplošitev v odvisnosti od roda grafov. Kot pomožno orodje je dokazana naslednja posplošitev rezultata, ki ga je dokazal Fertin s soavtorji za zvezdno kromatično število. Če je $G$ graf z maksimalno stopnjo $\Delta$, potem ima $G$ degenerirano zvezdno barvanje z $O(\Delta^3/2})$ barvami. Ta rezultat je uporabljen v dokazu glavnega izreka, ki pravi, da ima vsak graf roda $g$ degenerirano zvezdno barvanje z $O(g^3/5})$ barvami. Dodani so primeri, ki dokazujajo, da so dobljene ocene optimalne do logaritemskega faktorja. ANG We study the degenerate, the star and the degenerate star chromatic numbers and their relation to the genus of graphs. As a tool we prove the following strengthening of a result of Fertin et al.: If $G$ is a graph of maximum degree $\Delta$, then $G$ admits a degenerate star coloring using $O(\Delta^3/2})$ colors. We use this result to prove that every graph of genus $g$ admits a degenerate star coloring with $O(g^3/5})$ colors. It is also shown that these results are sharp up to a logarithmic factor. Objavljeno v Elsevier; Topological and geometric graph theory; European journal of combinatorics; 2012; Str. 340-349; Impact Factor: 0.658;Srednja vrednost revije / Medium Category Impact Factor: 0.673; WoS: PQ; Avtorji / Authors: Mohar Bojan, Špacapan Simon Tipologija 1.01 Izvirni znanstveni članek 2. COBISS ID 16410457 Vir: COBISS.SI Naslov SLO Spektralno degenerirani grafi: prenos na podgrafe ANG Spectrally degenerate graphs: Hereditary case Opis SLO Znano je, da spektralni radij drevesa maksimalne stopnje $\Delta$ nikoli ne presega vrednosti $2\sqrt{\Delta-1}$. Znana je tudi posplošitev tega dejstva na poljubne ravninske grafe in na $d$-degenerirane grafe. Ti rezultati so motivacija za uvedbo novega parametra. Pravimo, da je graf $G$ spektralno $d$-degeneriran, kadar ima vsak njegov podgraf $H$ spektralni radij manjši od $\sqrt{d\Delta(H)}$. Dokazan je šibki obrat zgoraj omenjenih rezultatov, ki pove, da ima vsak spektralno $d$-degeneriran graf $G$ vozlišče, ki je stopnje kvečjemu $4d\log_2(\Delta (G)/d)$ (če je $\Delta(G) \ge 2d$). V tej oceni se odvisnosti od $\Delta$ ne da odpraviti, kar je dokazano z verjetnostno konstrukcijo posebnih primerov. Dokazano je tudi, da je odločitveni problem, ali je dani graf spektralno $d$-degeneriran, co-NP-poln. ANG It is well known that the spectral radius of a tree whose maximum degree is $\Delta$ cannot exceed $2\sqrt{\Delta-1}$. A similar upper bound holds for arbitrary planar graphs, whose spectral radius cannot exceed $\sqrt{8 \Delta} + 10$, and more generally, for all $d$-degenerate graphs, where the corresponding upper bound is $\sqrt{4d\Delta}$. Following this, we say that a graph $G$ is spectrally $d$-degenerate if every subgraph $H$ of $G$ has spectral radius at most $\sqrt{d\Delta(H)}$. In this paper we derive a rough converse of the above-mentioned results by proving that each spectrally $d$-degenerate graph $G$ contains a vertex whose degree is at most $4d\log_2(\Delta(G)/d)$ (if $\Delta(G) \ge 2d$). It is shown that the dependence on $\Delta$ in this upper bound cannot be eliminated, as long as the dependence on $d$ is subexponential. It is also proved that the problem of deciding if a graph is spectrally $d$-degenerate is co-NP-complete. Objavljeno v Academic Press; Journal of combinatorial theory. Series B; 2012; Vol. 102, iss. 5; str. 1099-1109; Impact Factor: 0.845;Srednja vrednost revije / Medium Category Impact Factor: 0.673; A': 1; WoS: PQ; Avtorji / Authors: Dvorak Zdenek, Mohar Bojan Tipologija 1.01 Izvirni znanstveni članek 3. COBISS ID 16921945 Vir: COBISS.SI Naslov SLO Limite grafov ANG Graph limits Opis SLO Poglavje v referenčni izdaji Handbook of Graph Theory, ki je izšla pri CRC Press. V poglavju so prikazani glavni rezultati teorije grafovskih limit: grafoni, gostota homomorfizmov, konvergenčna zaporedja končnih grafov in njihovih limit, metrični prostor grafonov, Szemeredijeva lema o regularnosti in aproksimacija grafonov z uteženimi grafi, slučajni grafi, ki ustrezajo grafonu, grafovski parametri in pripadajoče matrike, ekstremalna teorija grafov in algebra kvantnih grafov. ANG Chapter in the Handbook of Graph Theory (CRC Press) describing Graph Limits. The content includes: Graphons, Homomorphism Density, Convergent Sequences of Graphs and Graphons, Metric Space Topology on Graphs and Graphons, Regularity Lemma and Approximation of Graphons by Weighted Graphs, W-Random Graphs, Graph Parameters and Connection Matrices, Extremal Graph Theory and the Algebra of Quantum Graphs. Objavljeno v CRC Press; Handbook of graph theory; 2013; Str. 1038-1057; A': 1; Avtorji / Authors: Mohar Bojan Tipologija 1.16 Samostojni znanstveni sestavek ali poglavje v monografski publikaciji 4. COBISS ID 16648537 Vir: COBISS.SI Naslov SLO Mnogo velikih lastnih vrednosti grafa v grafih z malo povezavami ANG Many large eigenvalues in sparse graphs Opis SLO V članku je pokazano, da so za poljubno družino grafov, ki je zaprta za minorje, naslednji pogoji primerljivo ekvivalentni za vsak graf v tej družini: (a) graf ima mnogo velikih lastnih vrednosti; (b) graf ima mnogo velikih negativnih lastnih vrednosti; (c) graf ima mnogo vozlišč visoke stopnje. Primerljiva ekvivalenca je izražena kvantitativno preko pogojev, kako velike so lastne vrednosti in koliko jih je. Vsaka smer ekvivalence lahko to velikost spremeni največ za konstantni faktor, ki je odvisen le od družine grafov in ne od posamenih članov družine. It is shown that, in every family $\mathscr{G}$ of graphs that is closed under taking minors, the following properties are roughly equivalent for ANG every $G \in \mathscr{G}$: (a) $G$ has many large eigenvalues; (b) $G$ has many large negative eigenvalues; (c) $G$ has many vertices of large degree. By a rough equivalence we mean that, in the quantitative version of the result, specifying the values of "how many" eigenvalues we want and "how large" they are, each implication may change these values by a constant factor. Objavljeno v Academic Press; European journal of combinatorics; 2013; Vol. 34, iss. 7; str. 1125-1129; Impact Factor: 0.612;Srednja vrednost revije / Medium Category Impact Factor: 0.674; WoS: PQ; Avtorji / Authors: Mohar Bojan Tipologija 1.01 Izvirni znanstveni članek 5. COBISS ID 16340313 Vir: COBISS.SI Naslov SLO Težavnost aproksimacije prekrižnega števila. ANG Hardness of approximation for crossing number Opis SLO Ob predpostavki P$\ne$NP pokažemo naslednji izrek: obstaja taka konstanta $c > 1$, da ni nobenega $c$-aproksimacijskega polinomskega algoritma za računanje prekrižnega števila grafa. Rezultat velja tudi za 3-regularne grafe. ANG We show that, if P$\ne$NP, there is a constant $c_0 > 1$ such that there is no $c_0$-approximation algorithm for the crossing number, even when restricted to 3-regular graphs. Objavljeno v Springer; Discrete & computational geometry; 2013; Vol. 49, iss. 2; str. 348-358; Impact Factor: 0.606;Srednja vrednost revije / Medium Category Impact Factor: 0.674; WoS: EX, PQ; Avtorji / Authors: Cabello Sergio Tipologija 1.01 Izvirni znanstveni članek 7.Najpomembnejši družbeno-ekonomski rezultati projektne skupine6 Družbeno-ekonomski dosežek 1. COBISS ID Vir: vpis v poročilo Naslov SLO Vabljeno predavanje ANG Invited lecture Opis SLO 3 ure vabljenih predavanj na GraDR 2012 Crossing Number Workshop and Minischool (maj 2012, Valtice, Češka). Naslovi predavanj: 1) Križanja v skoraj-ravninskih grafih. 2) Algoritmi za vložene grafe. ANG 3 hours of invited lectures at the GraDR 2012 Crossing Number Workshop and Minischool (May 2012, Valtice, Czech Republic). Titles: 1) Crossings of near-planar graphs. 2) Algorithms for embedded graphs. Šifra B.04 Vabljeno predavanje Objavljeno v Ni objavljeno. Tipologija 3.16 Vabljeno predavanje na konferenci brez natisa 2. COBISS ID Vir: vpis v poročilo Naslov SLO Uredništvo mednarodne znanstvene revije ANG Editor of international journals Opis SLO V teku projekta je bil B. Mohar urednik v revijah Electronic Journal of Combinatorics (Editor in Chief), SIAM Journal on Discrete Mathematics (Associate Editor), Discrete Mathematics (Associate Editor), Ars Mathematica Contemporanea (Editorial Board), Linear and Multilinear Algebra (Editor), Journal of Graph Theory (Editorial Board), Journal of Combinatorial Theory, Ser.B (Editorial board), Discrete and Computational Geometry (Editorial board), MATCH (Editorial board). ANG In the curse of the project B. Mohar has been editor of Electronic Journal of Combinatorics (Editor in Chief),SIAM Journal on Discrete Mathematics (Associate Editor), Discrete Mathematics (Associate Editor), Ars Mathematica Contemporanea (Editorial Board), Linear and Multilinear Algebra (Editor), Journal of Graph Theory (Editorial Board), Journal of Combinatorial Theory, Ser.B (Editorial board), Discrete and Computational Geometry (Editorial board), MATCH (Editorial board). Šifra C.04 Uredništvo mednarodne revije Objavljeno v Ni objavljeno. Tipologija 3.25 Druga izvedena dela 3. COBISS ID Vir: vpis v poročilo Naslov SLO Programski odbor mednarodne konference ANG Program Committee of an international meeting Opis SLO S. Cabello je bil član programskega odbora konference ACM-SIAM Symposium on Discrete Algorithms (SODA'14, Oregon, ZDA). ANG S. Cabello was a Program Committee member for ACM-SIAM Symposium on Discrete Algorithms (SODA'14, Oregon, USA). Šifra B.01 Organizator znanstvenega srečanja Objavljeno v Ni objavljeno. Tipologija 3.25 Druga izvedena dela 4. COBISS ID Vir: vpis v poročilo Naslov SLO Organizacijski odbor poletne šole ANG Organization Committee of a summer school Opis SLO S. Cabello je bil član organizacijskega odbora za Summer School on Computational Topology and Topological Data Analysis, Ljubljana, 2013. ANG S. Cabello was a member of the organization committee for the Summer School on Computational Topology and Topological Data Analysis, Ljubljana, 2013. Šifra D.10 Pedagoško delo Objavljeno v Ni objavljeno. Tipologija 3.25 Druga izvedena dela 8.Drugi pomembni rezultati projetne skupine7 9.Pomen raziskovalnih rezultatov projektne skupine8 9.1.Pomen za razvoj znanosti9 SLO Projekt spada med bazne raziskave s področja matematike. Problemi, ki si jih zastavljamo, so fundamentalni za razvoj področja in za njegovo uporabo. Pomembnost dokazuje naša bibliografija iz zadnjega obdobja in odmevnost rezultatov. Obravnavani problemi so osrednji v moderni teoriji grafov. Rezultate tega raziskovalnega projekta smo objavili v uglednih znanstvenih revijah in predstavili na mednarodnih znanstvenih konferenceh. V naslednjem obodbju pričakujemo, do bomo imeli večje število vabljenih, med njimi tudi plenarnih predavanj, kar bo še povečalo vidnost naših raziskovalnih dosežkov. S tem bomo okrepili že sedaj zavidljiv ugled slovenske šole teorije grafov. ANG_ The project belongs to basic research from the area of mathematics. Problems that we work on are internationally important, which can in particular be justified with our bibliography from the last period as well as with the (citation) impact of our results. The problems are central in the area of modern graph theory. Our newly obtained results have been published in established international journals and are presented at international scientific conferences. For the next period we expect that we will be invited to deliver several invited plenary talks which will further emphasize the visibility of our research achievements. In this way we will further increase the role of the Slovenian graph theory school. 9.2. Pomen za razvoj Slovenije10 SLO_ Doseženi rezultati so predvsem teoretični. Kljub temu pa imajo veliko potencialno uporabo v praksi, kar se posebej nanaša na naša algoritmična in optimizacijska raziskovanja. Področje velikih podatkovnih baz in s tem tudi osrednje teme tega projekta je eno od prioritetnih razvojno-raziskovalnih področij na svetu. ANG_ The results obtained are mostly theoretical. Nevertheless, some of our results have a potential for applications which is in particular the case with our research in algorithmic and optimization aspects of graph theory. The area of "big data" and hence also our main theme of large graphs is one of the priorities listed in the research policy documents worldwide. lO.Samo za aplikativne projekte in podoktorske projekte iz gospodarstva! Označite, katerega od navedenih ciljev ste si zastavili pri projektu, katere konkretne rezultate ste dosegli in v kakšni meri so doseženi rezultati uporabljeni Cilj F.01 Pridobitev novih praktičnih znanj, informacij in veščin Zastavljen cilj DA NE Rezultat 1 v Uporaba rezultatov 1 v F.02 Pridobitev novih znanstvenih spoznanj Zastavljen cilj DA NE Rezultat 1 - Uporaba rezultatov 1 v F.03 Večja usposobljenost raziskovalno-razvojnega osebja Zastavljen cilj DA NE Rezultat 1 - Uporaba rezultatov 1 v F.04 Dvig tehnološke ravni Zastavljen cilj DA NE Rezultat 1 - Uporaba rezultatov 1 v F.05 Sposobnost za začetek novega tehnološkega razvoja Zastavljen cilj DA NE Rezultat 1 v Uporaba rezultatov 1 v F.06 Razvoj novega izdelka Zastavljen cilj DA NE Rezultat 1 v Uporaba rezultatov 1 v F.07 Izboljšanje obstoječega izdelka Zastavljen cilj DA NE Rezultat 1 - Uporaba rezultatov 1 v F.08 Razvoj in izdelava prototipa Zastavljen cilj DA NE Rezultat 1 - Uporaba rezultatov 1 v F.09 Razvoj novega tehnološkega procesa oz. tehnologije Zastavljen cilj DA NE Rezultat 1 - Uporaba rezultatov 1 v F.10 Izboljšanje obstoječega tehnološkega procesa oz. tehnologije Zastavljen cilj DA NE Rezultat 1 v Uporaba rezultatov 1 v F.11 Razvoj nove storitve Zastavljen cilj DA NE Rezultat 1 v Uporaba rezultatov 1 v F.12 Izboljšanje obstoječe storitve Zastavljen cilj DA NE Rezultat 1 - Uporaba rezultatov 1 v F.13 Razvoj novih proizvodnih metod in instrumentov oz. proizvodnih procesov Zastavljen cilj DA NE Rezultat 1 - Uporaba rezultatov 1 v F 14 Izboljšanje obstoječih proizvodnih metod in instrumentov oz. proizvodnih procesov Zastavljen cilj DA NE Rezultat 1 - Uporaba rezultatov 1 v F.15 Razvoj novega informacijskega sistema/podatkovnih baz Zastavljen cilj DA NE Rezultat 1 v Uporaba rezultatov 1 v F.16 Izboljšanje obstoječega informacijskega sistema/podatkovnih baz Zastavljen cilj DA NE Rezultat 1 v Uporaba rezultatov 1 v F.17 Prenos obstoječih tehnologij, znanj, metod in postopkov v prakso Zastavljen cilj DA NE Rezultat 1 - Uporaba rezultatov 1 v F 18 Posredovanje novih znanj neposrednim uporabnikom (seminarji, forumi, konference) Zastavljen cilj DA NE Rezultat 1 v Uporaba rezultatov 1 v F.19 Znanje, ki vodi k ustanovitvi novega podjetja ("spin off") Zastavljen cilj DA NE Rezultat 1 - Uporaba rezultatov 1 v F.20 Ustanovitev novega podjetja ("spin off") Zastavljen cilj DA NE Rezultat 1 v Uporaba rezultatov 1 v F.21 Razvoj novih zdravstvenih/diagnostičnih metod/postopkov Zastavljen cilj DA NE Rezultat 1 v Uporaba rezultatov 1 v F.22 Izboljšanje obstoječih zdravstvenih/diagnostičnih metod/postopkov Zastavljen cilj DA NE Rezultat 1 v Uporaba rezultatov 1 v F.23 Razvoj novih sistemskih, normativnih, programskih in metodoloških rešitev Zastavljen cilj DA NE Rezultat 1 - Uporaba rezultatov 1 v F 24 Izboljšanje obstoječih sistemskih, normativnih, programskih in metodoloških rešitev Zastavljen cilj DA NE Rezultat 1 - Uporaba rezultatov 1 - F.25 Razvoj novih organizacijskih in upravljavskih rešitev Zastavljen cilj DA NE Rezultat 1 v Uporaba rezultatov 1 - F.26 Izboljšanje obstoječih organizacijskih in upravljavskih rešitev Zastavljen cilj DA NE Rezultat 1 - Uporaba rezultatov 1 - F.27 Prispevek k ohranjanju/varovanje naravne in kulturne dediščine Zastavljen cilj DA NE Rezultat 1 v Uporaba rezultatov 1 - F.28 Priprava/organizacija razstave Zastavljen cilj DA NE Rezultat 1 - Uporaba rezultatov 1 - F.29 Prispevek k razvoju nacionalne kulturne identitete Zastavljen cilj DA NE Rezultat 1 v Uporaba rezultatov 1 - F.30 Strokovna ocena stanja Zastavljen cilj DA NE Rezultat 1 v Uporaba rezultatov 1 - F.31 Razvoj standardov Zastavljen cilj DA NE Rezultat 1 - Uporaba rezultatov 1 - F.32 Mednarodni patent Zastavljen cilj DA NE Rezultat 1 - Uporaba rezultatov 1 - F.33 Patent v Sloveniji Zastavljen cilj DA NE Rezultat 1 - Uporaba rezultatov 1 - F.34 Svetovalna dejavnost Zastavljen cilj DA NE Rezultat 1 - Uporaba rezultatov 1 - F.35 Drugo Zastavljen cilj DA NE Rezultat 1 - Uporaba rezultatov 1 - Komentar ll.Samo za aplikativne projekte in podoktorske projekte iz gospodarstva! Označite potencialne vplive oziroma učinke vaših rezultatov na navedena področja Vpliv Ni vpliva Majhen vpliv Srednji vpliv Velik vpliv G.01 Razvoj visokošolskega izobraževanja G.01.01. Razvoj dodiplomskega izobraževanja O o o o G.01.02. Razvoj podiplomskega izobraževanja o o o o G.01.03. Drugo: o o o o G.02 Gospodarski razvoj G.02.01 Razširitev ponudbe novih izdelkov/storitev na trgu O O O O G.02.02. Širitev obstoječih trgov o o o o G.02.03. Znižanje stroškov proizvodnje o o o o G.02.04. Zmanjšanje porabe materialov in energije O O O O G.02.05. Razširitev področja dejavnosti o o o o G.02.06. Večja konkurenčna sposobnost o o o o G.02.07. Večji delež izvoza o o o o G.02.08. Povečanje dobička o o o o G.02.09. Nova delovna mesta o o o o G.02.10. Dvig izobrazbene strukture zaposlenih O O O O G.02.11. Nov investicijski zagon o o o o G.02.12. Drugo: o o o o G.03 Tehnološki razvoj G.03.01. Tehnološka razširitev/posodobitev dejavnosti O O O O Tehnološko prestrukturiranje G.03.02. dejavnosti o o o o G.03.03. Uvajanje novih tehnologij o o o o G.03.04. Drugo: o o o o G.04 Družbeni razvoj G.04.01 Dvig kvalitete življenja o o o o G.04.02. Izboljšanje vodenja in upravljanja o o o o G.04.03. Izboljšanje delovanja administracije in javne uprave O O O O G.04.04. Razvoj socialnih dejavnosti o o o o G.04.05. Razvoj civilne družbe o o o o G.04.06. Drugo: o o o o G.05. Ohranjanje in razvoj nacionalne naravne in kulturne dediščine in identitete O O O O G.06. Varovanje okolja in trajnostni razvoj O O O O G.07 Razvoj družbene infrastrukture G.07.01. Informacijsko-komunikacijska infrastruktura O O O O G.07.02. Prometna infrastruktura o o o o G.07.03. Energetska infrastruktura o o o o G.07.04. Drugo: o o o o G.08. Varovanje zdravja in razvoj zdravstvenega varstva O O O O G.09. Drugo: o o o o Komentar 12.Pomen raziskovanja za sofinancerje11 Sofinancer 1. Naziv Naslov Vrednost sofinanciranja za celotno obdobje trajanja projekta je znašala: EUR Odstotek od utemeljenih stroškov projekta: % Najpomembnejši rezultati raziskovanja za sofinancerja Šifra 1. 2. 3. 4. 5. Komentar Ocena 13.Izjemni dosežek v letu 201412 13.1. Izjemni znanstveni dosežek 13.2. Izjemni družbeno-ekonomski dosežek V letu 2014 je bil nosilec projekta Bojan Mohar v uredniških odborih skoraj vseh najpomembnejših revij za področje teorije grafov: The Electronic Journal of Combinatorics (Editor-in-Chief) Discrete Mathematics (Associate Editor) SIAM Journal on Discrete Mathematics (Associate Editor) Journal of Combinatorial Theory, Series B Discrete and Computational Geometry Journal of Graph Theory C. IZJAVE Podpisani izjavljam/o, da: • so vsi podatki, ki jih navajamo v poročilu, resnični in točni • se strinjamo z obdelavo podatkov v skladu z zakonodajo o varstvu osebnih podatkov za potrebe ocenjevanja ter obdelavo teh podatkov za evidence ARRS • so vsi podatki v obrazcu v elektronski obliki identični podatkom v obrazcu v pisni obliki • so z vsebino zaključnega poročila seznanjeni in se strinjajo vsi soizvajalci projekta Podpisi: zastopnik oz. pooblaščena oseba i vodja raziskovalnega projekta: raziskovalne organizacije: Inštitut za matematiko, fiziko in Bojan Mohar mehaniko ZIG Kraj in datum: Ljubljana |12.3.2015 Oznaka poročila: ARRS-RPROJ-ZP-2015/124 1 Napišite povzetek raziskovalnega projekta (največ 3.000 znakov v slovenskem in angleškem jeziku) Nazaj 2 Napišite kratko vsebinsko poročilo, kjer boste predstavili raziskovalno hipotezo in opis raziskovanja. Navedite ključne ugotovitve, znanstvena spoznanja, rezultate in učinke raziskovalnega projekta in njihovo uporabo ter sodelovanje s tujimi partnerji. Največ 12.000 znakov vključno s presledki (približno dve strani, velikost pisave 11). Nazaj 3 Realizacija raziskovalne hipoteze. Največ 3.000 znakov vključno s presledki (približno pol strani, velikost pisave 11) Nazaj 4 V primeru bistvenih odstopanj in sprememb od predvidenega programa raziskovalnega projekta, kot je bil zapisan v predlogu raziskovalnega projekta oziroma v primeru sprememb, povečanja ali zmanjšanja sestave projektne skupine v zadnjem letu izvajanja projekta, napišite obrazložitev. V primeru, da sprememb ni bilo, to navedite. Največ 6.000 znakov vključno s presledki (približno ena stran, velikost pisave 11). Nazaj 5 Navedite znanstvene dosežke, ki so nastali v okviru tega projekta. Raziskovalni dosežek iz obdobja izvajanja projekta (do oddaje zaključnega poročila) vpišete tako, da izpolnite COBISS kodo dosežka - sistem nato sam izpolni naslov objave, naziv, IF in srednjo vrednost revije, naziv FOS področja ter podatek, ali je dosežek uvrščen v A'' ali A'. Nazaj 6 Navedite družbeno-ekonomske dosežke, ki so nastali v okviru tega projekta. Družbeno-ekonomski rezultat iz obdobja izvajanja projekta (do oddaje zaključnega poročila) vpišete tako, da izpolnite COBISS kodo dosežka - sistem nato sam izpolni naslov objave, naziv, IF in srednjo vrednost revije, naziv FOS področja ter podatek, ali je dosežek uvrščen v A'' ali A'. Družbeno-ekonomski dosežek je po svoji strukturi drugačen kot znanstveni dosežek. Povzetek znanstvenega dosežka je praviloma povzetek bibliografske enote (članka, knjige), v kateri je dosežek objavljen. Povzetek družbeno-ekonomskega dosežka praviloma ni povzetek bibliografske enote, ki ta dosežek dokumentira, ker je dosežek sklop več rezultatov raziskovanja, ki je lahko dokumentiran v različnih bibliografskih enotah. COBISS ID zato ni enoznačen, izjemoma pa ga lahko tudi ni (npr. prehod mlajših sodelavcev v gospodarstvo na pomembnih raziskovalnih nalogah, ali ustanovitev podjetja kot rezultat projekta ... - v obeh primerih ni COBISS ID). Nazaj 7 Navedite rezultate raziskovalnega projekta iz obdobja izvajanja projekta (do oddaje zaključnega poročila) v primeru, da katerega od rezultatov ni mogoče navesti v točkah 6 in 7 (npr. ni voden v sistemu COBISS). Največ 2.000 znakov, vključno s presledki. Nazaj 8 Pomen raziskovalnih rezultatov za razvoj znanosti in za razvoj Slovenije bo objavljen na spletni strani: http://sicris.izum.si/ za posamezen projekt, ki je predmet poročanja Nazaj 9 Največ 4.000 znakov, vključno s presledki Nazaj 10 Največ 4.000 znakov, vključno s presledki Nazaj 11 Rubrike izpolnite / prepišite skladno z obrazcem "izjava sofinancerja" http://www.arrs.gov.si/sl/progproj/rproj/gradivo/, ki ga mora izpolniti sofinancer. Podpisan obrazec "Izjava sofinancerja" pridobi in hrani nosilna raziskovalna organizacija -izvajalka projekta. Nazaj 12 Navedite en izjemni znanstveni dosežek in/ali en izjemni družbeno-ekonomski dosežek raziskovalnega projekta v letu 2014 (največ 1000 znakov, vključno s presledki). Za dosežek pripravite diapozitiv, ki vsebuje sliko ali drugo slikovno gradivo v zvezi z izjemnim dosežkom (velikost pisave najmanj 16, približno pol strani) in opis izjemnega dosežka (velikost pisave 12, približno pol strani). Diapozitiv/-a priložite kot priponko/-i k temu poročilu. Vzorec diapozitiva je objavljen na spletni strani ARRS http://www.arrs.gov.si/sl/gradivo/, predstavitve dosežkov za pretekla leta pa so objavljena na spletni strani http://www.arrs.gov.si/sl/analize/dosez/. Nazaj Obrazec: ARRS-RPROJ-ZP/2015 v1.00a F7-43-3F-91-65-B6-22-05-DF-D8-1C-C4-58-E4-2F-5A-16-DA-19-6B Priloga 1 NARAVOSLOVJE Področje: 1.01 -Matematika i i ГО (lil Пкчргу / л v___ The Electronic Journal of Combinatorics V letu 2014 je bil nosilec projekta Bojan Mohar v uredniških odborih skoraj vseh najpomembnejših revij za področje teorije grafov: ❖The Electronic Journal of Combinatorics (Editor-in-Chief) ❖Discrete Mathematics (Associate Editor) ❖SIAM Journal on Discrete Mathematics (Associate Editor) ❖Journal of Combinatorial Theory, Series B ❖Discrete and Computational Geometry ❖Journal of Graph Theory