Graphs and their algebraic properties
Project goals
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.
Keywords
graphnowhere-zero flowTutte polynomialhomomorphismvector coloringembedded graphs
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
Standardní projekty 23 (SGA0201900001)
Main participants
Univerzita Karlova / Matematicko-fyzikální fakulta
Contest type
VS - Public tender
Contract ID
19-21082S
Alternative language
Project name in Czech
Grafy a jejich algebraické vlastnosti
Annotation in Czech
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.
Scientific branches
Completed project evaluation
Provider evaluation
U - Uspěl podle zadání (s publikovanými či patentovanými výsledky atd.)
Project results evaluation
The results obtained during the project fulfill the aims. There are enough published papers in impacted journals from the field of the project. Some of them have already attracted citations. The relatively small team successfully integrated students and postdocs.
Solution timeline
Realization period - beginning
Jan 1, 2019
Realization period - end
Dec 31, 2021
Project status
U - Finished project
Latest support payment
May 31, 2021
Data delivery to CEP
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data delivery code
CEP22-GA0-GA-U
Data delivery date
Jun 29, 2022
Finance
Total approved costs
7,470 thou. CZK
Public financial support
6,295 thou. CZK
Other public sources
963 thou. CZK
Non public and foreign sources
0 thou. CZK
Basic information
Recognised costs
7 470 CZK thou.
Public support
6 295 CZK thou.
84%
Provider
Czech Science Foundation
OECD FORD
Pure mathematics
Solution period
01. 01. 2019 - 31. 12. 2021