All
All

What are you looking for?

All
Results
Organizations

Quick search

  • Projects supported by TA ČR
  • Excellent projects
  • Projects with the highest public support
  • Current projects

Smart search

  • That is how I find a specific +word
  • That is how I leave the -word out of the results
  • “That is how I can find the whole phrase”

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

  • R&D category

    ZV - Basic research

  • OECD FORD - main branch

    10101 - Pure mathematics

  • OECD FORD - secondary branch

  • OECD FORD - another secondary branch

  • BA - General mathematics

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