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”

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

  • R&D category

    ZV - Basic research

  • CEP classification - main branch

    BA - General mathematics

  • CEP - secondary branch

  • CEP - another secondary branch

  • 10101 - Pure mathematics

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