Extremal graph theory and applications
Project goals
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.
Keywords
Extremal graph theorygraph limitsrandom graphsregularity lemmaflag complexes
Public support
Provider
Czech Science Foundation
Programme
Junior Grants
Call for proposals
Juniorské granty 2 (SGA0201600002)
Main participants
Ústav informatiky AV ČR, v. v. i.
Contest type
VS - Public tender
Contract ID
16-07822Y
Alternative language
Project name in Czech
Extremální teorie grafů a aplikace
Annotation in Czech
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.
Scientific branches
Completed project evaluation
Provider evaluation
V - Vynikající výsledky projektu (s mezinárodním významem atd.)
Project results evaluation
Several interesting results in extremal graph theory were obtained; these results were published in the top combinatorial journals. In total, there are 22 journal publications and 6 publications in conference proceedings, exceeding the goals given in the proposal. Two students participated in the project. The budget changes are justified by the changes in the project team.
Solution timeline
Realization period - beginning
Jan 1, 2016
Realization period - end
Dec 11, 2020
Project status
U - Finished project
Latest support payment
May 30, 2018
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
CEP21-GA0-GJ-U/02:1
Data delivery date
Jun 30, 2021
Finance
Total approved costs
7,610 thou. CZK
Public financial support
7,610 thou. CZK
Other public sources
0 thou. CZK
Non public and foreign sources
0 thou. CZK
Recognised costs
7 610 CZK thou.
Public support
7 610 CZK thou.
0%
Provider
Czech Science Foundation
CEP
BA - General mathematics
Solution period
01. 01. 2016 - 11. 12. 2020