Flows, cycles, surfaces and polynomials
Project goals
Flows in graphs and the dual notion of tensions permeate combinatorial theory, not least because their definition extends from graphs to other combinatorial structures such as matroids and embedded graphs, and due to their applications in e.g. optimization and physics. Tantalizing conjectures abound -- Tutte's flow conjectures, snark conjectures, the cycle double cover -- and continue to exert a productive influence on the theory. The defining properties of tensions and flows in graphs involve cutsets and cycles, and the ways in which the edges of a graph can be covered by its cycles is closely related to the surfaces in which it embeds (the faces of a plane embedding of a bridgeless graph cover each edge exactly twice). To this interplay of flows, cycle covers, and surface embeddings we add randomness: we plan to establish a theory of random embeddings of graphs in surfaces, inspired by the success of the theory of random graphs. Connections to important conjectures on flows, cycles and polynomials will serve us both as a guide and a gauge for how useful our results are.
Keywords
flows in graphscycle double coverrandom embeddingsgraph polynomials
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
SGA0202500001
Main participants
Univerzita Karlova / Matematicko-fyzikální fakulta
Contest type
VS - Public tender
Contract ID
25-16627S
Alternative language
Project name in Czech
Toky, cykly, plochy a polynomy
Annotation in Czech
Toky v grafech a duální pojem tenze prostupují kombinatorikou, nejen proto, že jejich definici lze rozšířit z grafů na jiné kombinatorické struktury jako jsou matroidy a grafy na plochách, a kvůli jejich aplikacím, např. v optimalizaci a fyzice. Je zde mnoho lákavých hypotéz -- Tutteovy tokové hypotézy, hypotézy o snarcích, o dvojitém pokrytí cykly -- a třebaže nevyřešeny, inspirují další rozvoj oblasti. Tenze a toky v grafech jsou definovány pomocí řezů a cyklů a způsoby, jakými mohou být hrany grafu pokryty jeho cykly, jsou úzce spojeny s plochou, na které je graf nakreslen (stěny rovinného nakreslení grafu bez mostů pokrývají každou hranu dvakrát). K této souhře toků, pokrytí cykly a nakreslení přidáme v našem projektu náhodnost. Plánujeme založit teorii náhodných vnoření grafů do povrchů, inspirovanou úspěchem teorie náhodných grafů. Důležité hypotézy o tocích, cyklech a polynomech nám poslouží jak jako ukazatel směru, tak jako měřítko užitečnosti našich výsledků.
Scientific branches
Solution timeline
Realization period - beginning
Jan 1, 2025
Realization period - end
Dec 31, 2027
Project status
Z - Beginning multi-year project
Latest support payment
—
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
CEP25-GA0-GA-R
Data delivery date
Feb 27, 2025
Finance
Total approved costs
12,500 thou. CZK
Public financial support
11,420 thou. CZK
Other public sources
1,080 thou. CZK
Non public and foreign sources
0 thou. CZK
Recognised costs
12 500 CZK thou.
Public support
11 420 CZK thou.
0%
Provider
Czech Science Foundation
OECD FORD
Pure mathematics
Solution period
01. 01. 2025 - 31. 12. 2027