Projekti / Programi
Sodobne invariante grafov
| Koda |
Veda |
Področje |
Podpodročje |
| 1.01.00 |
Naravoslovje |
Matematika |
|
| Koda |
Veda |
Področje |
| P110 |
Naravoslovno-matematične vede |
Matematična logika, teorija množic, kombinatorika |
| Koda |
Veda |
Področje |
| 1.01 |
Naravoslovne vede |
Matematika |
barvanje grafa, dominacija grafa, vozliščno pokritje, metrična dimenzija, dominacijska igra, igra barvanja, igre na grafih
Raziskovalci (17)
Organizacije (2)
Povzetek
Teorija grafov je hitro rastoče področje sodobne matematike in obravnava invariant grafov njen inherenten sestavni del. V tem projektu obravnavamo nekatere probleme, ki zadevajo klasične koncepte teorije grafov in njihovo obravnavo na naraven način kombiniramo s študijami nedavno vpeljanih in pogosto uporabnih grafovskih parametrov. Nekatere od novejših invariant, ki jih obravnavamo, so bile motivirane s praktičnimi problemi in aplikacijami, druge pa so bile vpeljane ob iskanju orodij za naskok na pomembne odprte domneve. Obravnavane invariante lahko razdelimo na več tipov in sicer, invariante barvanj, dominacijske invariante, invariante pokritij, dimenzijske invariante in igralne invariante grafov.
Glavni cilji projekta so:
(1) Podati nov vpogled in po možnosti tudi rešiti znamenite odprte probleme in domneve. Raziskave bodo vključevale variacije dominantnih števil kartezičnega produkta grafov (Vizingova domneva in rezultati Vizingovega tipa), kromatično število direktnega produkta grafov (Hedetniemijeva domneva), L(2,1) barvanja grafov z omejeno stopnjo (domneva Grigga in Yeha), b-kromatično število regularnih grafov (domneva Erdős-Farber-Lovász), dominantno število ravninskih skoraj triangulacij (domneva Mathesona in Tarjana), vozliščno pokritje k-poti v ravninskih grafih (šibka verzija Albertson-Bermanove domneve), pokritje grafa z geodetskimi potmi (povezava z Meynielovo domnevo), domneve o igralnem (celotnem) dominantnem številu, odprti problemi o igralnem kromatičnem številu in njegovih variacijah.
(2) Nadaljevati raziskave nekaterih nedavno vpeljanih invariant grafov in prispevati pomemben napredek pri njihovi obravnavi.
Invariante vključujejo, a niso omejene na različna barvanja in (mavrične) dominacijske invariante, b-kromatična števila, (sproščena) L(j,k) označevanja, pakirno kromatično število, različice invariant pokritij (še posebej omenimo vozliščno pokritje k-poti in krepko geodetsko število), različne tipe metrične dimenzije grafov in invariante, ki izhajajo iz iger na grafih kot npr. igralno kromatično število, indicirano kromatično število, igralno Grundyjevo število in igralno (celotno) dominantno število.
(3) Prispevati celovite študije nekaterih med seboj prepletenih konceptov, ki bodo rezultirale v vsaj dveh preglednih člankih. V teh člankih nameravamo identificirati in poudariti osrednje odprte probleme kot tudi zastaviti nove odprte probleme. Pričakujemo, da bodo takšni pregledni članki imeli velik vpliv na pripadajoča raziskovalna področja. Osredotočili se bomo na več področij:
(i) dominacijske igre, za katere načrtujemo napisati monografijo;
(ii) pakirna barvanja in sorodni koncepti barvanj, porojeni z razdaljami v grafu;
(iii) invariante dominacijskega tipa in njihovo vedenje v kartezičnem produktu grafov (rezultati Vizingovega tipa).
(4) V načrtu tega projekta je monografija, ki bo obravnavala dominacijsko igro in sorodne igre ter invariante. Ta igra je bila vpeljana leta 2010 in je že v tem času postala ena najbolj široko obravnavanih iger na grafih. Pri pisanju knjige bosta sodelovala dva člana projektne skupine ter dva zunanja sodelavca, pri čemer smo bili vsi vključeni v raziskave dominacijske igre od samega začetka.
Pomen za razvoj znanosti
Projekt pripada temeljnim raziskavam s področja matematike in se s svojimi uporabnimi vidiki dotika nekaterih sorodnih področij kot na primer računalništva. Zastavljeni problemi so mednarodno pomembni, kar lahko utemeljimo z našimi publikacijami iz zadnjega obdobja kot tudi z odmevnostjo naših rezultatov. Načrtujemo naskok na nekatere pomembne matematične probleme, ki so odprti že vrsto let in katerih (popolna ali celo delna) rešitev bi pomenila znaten vpliv na razvoj raziskav v teoriji grafov in sorodnih področjih.
Problemi, ki smo jih zastavili v projektu niso le nerešeni, temveč tudi relevantni, kar dokazuje število uveljavljenih matematikov, ki so se jih je že lotevali. V nekaterih primerih so problemi povezani z drugimi matematičnimi vejami (kot npr. z linearno algebro v primeru števila ničelne prisile), v spet drugih primerih pa so povezani z drugimi (uporabnimi) znanstvenimi področji (kot v primeru L(j,k) označitev, metrične dimenzije in drugih). Pričakujemo objavo več znanstvenih člankov v ključnih revijah s področja diskretne matematike, ki se bodo nanašali na vsebino projekta. Dobljene rezultate bomo predstavili na relevantnih mednarodnih konferencah.
Delo na projektu bo lahko služilo tudi kot odlična podpora za monografijo o dominacijskih igrah, kar je želen in izvedljiv cilj projekta. To utemeljuje hiter razvoj na tem področju in številni odzivi, ki ocenjujejo, da bi se monografija o pomembnem primeru igre na grafih na naraven način umestila v (neprazen) prostor med teorijo grafov in kombinatorično teorijo iger.
Pomen za razvoj Slovenije
The project belongs to basic research in the area of mathematics and with its applicable aspects touches some related fields such as computer science. Problems that we will work on are internationally important, which can be justified by our publications from the last period as well as with the impact of our results. We plan to attack some important long-standing mathematical problems, whose (complete or even partial) solutions would have considerable impact on research developments in graph theory and related areas.
The problems that we propose to investigate are not only unsolved, but having in mind the number of established mathematicians that have considered them they are also relevant.
In some cases, the problems are related to other mathematical disciplines (such as to linear algebra in the case of zero forcing numbers) and in some other cases they are connected to other (applicable) scientific areas (such as in the case of L(j,k) labelings, metric dimensions and others). We expect to publish several papers in key journals from the area of discrete mathematics related to the topics of the proposed project. We will also present our results at relevant international conferences.
The work on the project will also serve as a perfect support for the monograph concerning domination game(s), which is a desirable and realistic goal of the project, This can be justified by the quick development of the area, and a number of responses that a monograph about the important instance of graph game(s) would in a natural way be placed in the (non-empty) space between graph theory and combinatorial game theory.
Najpomembnejši znanstveni rezultati
Vmesno poročilo
Najpomembnejši družbeno–ekonomsko in kulturno relevantni rezultati
