Toky a cykly v grafech na plochách
Cíle projektu
Toky v grafech jsou historicky jedním z centrálních témat kombinatoriky. Nikde-nulové toky byly zavedeny ve vlivném článku W. Tutteho jakožto duální koncept ke grafové barevnosti, a k jejich význačnosti přispěly i další souvislosti, například s hypotézou o dvojitém pokrytí cykly a Berge-Fulkersonovou hypotézou, či algebraické propojení s dalšími grafovými parametry přes Tutteho polynom. Většina výzkumu týkajícího se nikde-nulových toků je inspirována Tutteho hypotézami a zaměřuje se na toky v obecných grafech. V tomto projektu budeme studovat toky v grafech na plochách, což je motivováno aplikacemi v grafové barevnosti a ve slibném přístupu k hypotéze o dvojitém pokrytí cykly. Zaměříme se také na algebraické souvislosti a rozvineme teorii plochového Tutteho polynomu.
Klíčová slova
Veřejná podpora
Poskytovatel
Grantová agentura České republiky
Program
Standardní projekty
Veřejná soutěž
SGA0202200004
Hlavní účastníci
Univerzita Karlova / Matematicko-fyzikální fakulta
Druh soutěže
VS - Veřejná soutěž
Číslo smlouvy
22-17398S
Alternativní jazyk
Název projektu anglicky
Flows and cycles in graphs on surfaces
Anotace anglicky
Flows in graphs have a long and rich history in combinatorial theory. In his influential paper, Tutte introduced the concept of nowhere-zero flows motivated by the duality to graph colorings in plane graphs. Nowhere-zero flows rose to prominence in part due to their connections to other important topics such as the Cycle Double Cover conjecture and Berge–Fulkerson conjecture. The importance of the topic is further reinforced through algebraic connections, in particular through the Tutte polynomial which enumerates flows and relates them to other graph invariants when evaluated at suitable points. Much of the research into nowhere-zero flows is inspired by Tutte's insightful conjectures and focuses on general graphs. In this project, we investigate the topic of flows in graphs drawn on surfaces, motivated by applications in graph coloring and a possible approach towards the Cycle Double Cover conjecture. Moreover, we develop the algebraic connection via the study of the surface Tutte polynomial.
Vědní obory
Kategorie VaV
ZV - Základní výzkum
OECD FORD - hlavní obor
10101 - Pure mathematics
OECD FORD - vedlejší obor
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
OECD FORD - další vedlejší obor
—
CEP - odpovídající obory
(dle převodníku)AF - Dokumentace, knihovnictví, práce s informacemi
BA - Obecná matematika
BC - Teorie a systémy řízení
BD - Teorie informace
IN - Informatika
Termíny řešení
Zahájení řešení
1. 1. 2022
Ukončení řešení
31. 12. 2024
Poslední stav řešení
—
Poslední uvolnění podpory
29. 2. 2024
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
CEP25-GA0-GA-R
Datum dodání záznamu
12. 3. 2025
Finance
Celkové uznané náklady
10 780 tis. Kč
Výše podpory ze státního rozpočtu
9 743 tis. Kč
Ostatní veřejné zdroje financování
1 037 tis. Kč
Neveřejné tuz. a zahr. zdroje finan.
0 tis. Kč
Základní informace
Uznané náklady
10 780 tis. Kč
Statní podpora
9 743 tis. Kč
90%
Poskytovatel
Grantová agentura České republiky
OECD FORD
Pure mathematics
Doba řešení
01. 01. 2022 - 31. 12. 2024