Extremální teorie grafů a aplikace
Cíle projektu
Grafy jsou jedny z nejjednodušších matematických struktur. Tvoří základy velké části informatiky a jejich význam nesmírně vzrostl v souvislosti s v rozvojem počítačových sítí. Extremální teorie grafů se zaměřuje na souvislosti mezi různými vlastnostmi grafů. Náš projekt propojuje extrémální teorii grafů s několika dalšími obory včetně pravděpodobnosti, analýzy a geometrie. Využíváme nové techniky, které byly vyvinuty pro problémy vnořování v souvislých grafech, a techniky pocházející z teorie limit hustých grafů. Cílem projektu je vyvíjet obecné metody související se Szemerédiho regularity lemmatem, metodou stability, extremálními problémy pro grafony a aplikacemi Chatterjee-Varadhanova postupu pro velké odchylky v Erdős-Rényiho náhodných grafech. Mezi naše hlavní cíle patří řešení domněnky Loebl-Komlós-Sós, aplikace extremální teorie grafů v geometrické kombinatorice nebo práce na problému "nechvalně známého pravého chvostu" pro počty podgrafů v náhodných grafech.
Klíčová slova
Extremal graph theorygraph limitsrandom graphsregularity lemmaflag complexes
Veřejná podpora
Poskytovatel
Grantová agentura České republiky
Program
Juniorské granty
Veřejná soutěž
Juniorské granty 2 (SGA0201600002)
Hlavní účastníci
Ústav informatiky AV ČR, v. v. i.
Druh soutěže
VS - Veřejná soutěž
Číslo smlouvy
16-07822Y
Alternativní jazyk
Název projektu anglicky
Extremal graph theory and applications
Anotace anglicky
Graphs are among the simplest mathematical structures. They form the foundation for much of Computer Science and their importance has grown enormously with the development of computer networks. Extremal graph theory focuses on interactions between different properties of graphs. In this project we link extremal graph theory to several other fields, including probability theory, analysis and geometry. We exploit novel techniques that were developed for embedding problems in sparse graphs and those that arose from the theory of dense graph limits. The aim of the project is to develop general tools that relate to the Szemerédi Regularity lemma, the Stability method, extremal problems in graphons, and applications of the Chatterjee-Varadhan approach to large deviations of Erdős-Rényi random graphs. Among our main goals are the resolution of the Loebl-Komlós-Sós conjecture, applications of extremal graph theory in geometric combinatorics, or work on the "infamous upper tail problem" for subgraph counts in random graphs.
Vědní obory
Kategorie VaV
ZV - Základní výzkum
CEP - hlavní obor
BA - Obecná matematika
CEP - vedlejší obor
—
CEP - další vedlejší obor
—
OECD FORD - odpovídající obory
(dle převodníku)10101 - Pure mathematics
Hodnocení dokončeného projektu
Hodnocení poskytovatelem
V - Vynikající výsledky projektu (s mezinárodním významem atd.)
Zhodnocení výsledků projektu
V rámci projektu bylo dosaženo několika zajímavých výsledků v oboru extremální teorie grafů, publikovaných ve špičkových kombinatorických časopisech. Celkem je vykázáno 22 publikací v časopisech a 6 v konferenčních sbornících, což výrazně přesahuje plán z návrhu projektu. Do řešení projektu byli zapojeni dva studenti. Nedočerpání finančních prostředků je odůvodněné změnami v řešitelském týmu.
Termíny řešení
Zahájení řešení
1. 1. 2016
Ukončení řešení
11. 12. 2020
Poslední stav řešení
U - Ukončený projekt
Poslední uvolnění podpory
30. 5. 2018
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
CEP21-GA0-GJ-U/02:1
Datum dodání záznamu
30. 6. 2021
Finance
Celkové uznané náklady
7 610 tis. Kč
Výše podpory ze státního rozpočtu
7 610 tis. Kč
Ostatní veřejné zdroje financování
0 tis. Kč
Neveřejné tuz. a zahr. zdroje finan.
0 tis. Kč
Uznané náklady
7 610 tis. Kč
Statní podpora
7 610 tis. Kč
0%
Poskytovatel
Grantová agentura České republiky
CEP
BA - Obecná matematika
Doba řešení
01. 01. 2016 - 11. 12. 2020