Grafy a jejich algebraické vlastnosti
Cíle projektu
Projekt rozvíjí teorii barvení grafů a toků ve třech příbuzných směrech použitím algebraických technik. Homologické vlastnosti grafů (cyklově spojitá zobrazení) přinesly čerstvé podněty pro proslulou Hypotézu o 5-toku a další zásadní problémy ve strukturální teorii grafů. Budeme zkoumat tyto vlastnosti tokově a tenzně spojitých zobrazení obecněji. Vektorová obarvení rozšiřují klasická barvení grafů a umožňují použít semidefinitní programování pro aproximování (klasické) barevnosti pomocí barevnosti vektorové; budeme zkoumat její další strukturální a algoritmické vlastnosti. Nedávno objevený “topologický Tutteho polynom” pro grafy na plochách má podobnou motivaci jako klasický Tutteho dichromatický polynom. Budeme zkoumat další vlastnosti tohoto a příbuzných invariantů, a jejich potenciální aplikace v teorii uzlů a statistické fyzice. Využívajíce nedávného pokroku v této oblasti, chystáme se propojit kulturu řešení problémů typickou pro současnou teorii grafů s budováním teorií, typickým pro jiné oblasti matematiky.
Klíčová slova
graphnowhere-zero flowTutte polynomialhomomorphismvector coloringembedded graphs
Veřejná podpora
Poskytovatel
Grantová agentura České republiky
Program
Standardní projekty
Veřejná soutěž
Standardní projekty 23 (SGA0201900001)
Hlavní účastníci
Univerzita Karlova / Matematicko-fyzikální fakulta
Druh soutěže
VS - Veřejná soutěž
Číslo smlouvy
19-21082S
Alternativní jazyk
Název projektu anglicky
Graphs and their algebraic properties
Anotace anglicky
This project will develop the theory of graph colorings and flows in three related directions using algebraic techniques. Homological properties of graphs (cycle-continuous maps) have given fresh insights into the longstanding 5-Flow Conjecture and other pivotal open problems in structural graph theory: we shall explore these properties for flow- and tension-continuous mappings more generally. Vector coloring extends classical coloring and enables semidefinite programming to be used to approximate the (classical) chromatic number by way of the vector chromatic number: we will determine further structural and algorithmic properties of the latter. Recently a new "topological Tutte polynomial" for embedded graphs was constructed in the spirit of Tutte's original dichromate: we will investigate other properties of this and related invariants, and potential applications in knot theory and statistical physics. Building on recent momentum in the area, we unite the problem-solving spirit of current graph theory with the theory-building approach more typical of other areas of mathematics.
Vědní obory
Kategorie VaV
ZV - Základní výzkum
OECD FORD - hlavní obor
10101 - Pure mathematics
OECD FORD - vedlejší obor
—
OECD FORD - další vedlejší obor
—
CEP - odpovídající obory
(dle převodníku)BA - Obecná matematika
Hodnocení dokončeného projektu
Hodnocení poskytovatelem
U - Uspěl podle zadání (s publikovanými či patentovanými výsledky atd.)
Zhodnocení výsledků projektu
Výsledky obsažené během projektu naplňují cíle. Dostatek článků bylo již publikováno v impaktovaných oborových časopisech. Některé z těchto článků již získaly citace. Relativně malý tým úspěšně začlenil studenty a postdoky.
Termíny řešení
Zahájení řešení
1. 1. 2019
Ukončení řešení
31. 12. 2021
Poslední stav řešení
U - Ukončený projekt
Poslední uvolnění podpory
31. 5. 2021
Dodání dat do CEP
Důvěrnost údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Systémové označení dodávky dat
CEP22-GA0-GA-U
Datum dodání záznamu
29. 6. 2022
Finance
Celkové uznané náklady
7 470 tis. Kč
Výše podpory ze státního rozpočtu
6 295 tis. Kč
Ostatní veřejné zdroje financování
963 tis. Kč
Neveřejné tuz. a zahr. zdroje finan.
0 tis. Kč
Základní informace
Uznané náklady
7 470 tis. Kč
Statní podpora
6 295 tis. Kč
84%
Poskytovatel
Grantová agentura České republiky
OECD FORD
Pure mathematics
Doba řešení
01. 01. 2019 - 31. 12. 2021