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”

Graph limits and inhomogeneous random graphs

Project goals

Theories of dense and sparse graph limits are one of the most important recent tools of discrete mathematics. Their emergence and development have led to many breakthroughs on old problems in extremal graph theory and random graph theory, and especially have linked discrete mathematics to areas such as probability theory, functional analysis or group theory in a profound way. Recognitions related to the development of the field include the 2012 Fulkerson Prize, the 2013 Coxeter-James Prize, and the 2013 David P. Robbins Prize. The project will study the theories of dense a sparse graph limits as well as the related theory of inhomogeneous random graphs. Specific problems in the area of inhomogeneous random graphs include questions on key graph parameters such as the chromatic number or the independence number. In the theory of sparse graph limits our main goal is to extend our understanding of local-global convergence. A further goal is to create a comprehensive theory of limits of subgraphs of hypercubes.

Keywords

discrete mathematicsgraph theorygraph limitsrandom graphs

Public support

  • Provider

    Czech Science Foundation

  • Programme

    Junior Grants

  • Call for proposals

    Juniorské granty 4 (SGA0201800002)

  • Main participants

    Matematický ústav AV ČR, v. v. i.

  • Contest type

    VS - Public tender

  • Contract ID

    18-01472Y

Alternative language

  • Project name in Czech

    Limity grafů a nehomogenní náhodné grafy

  • Annotation in Czech

    Teorie hustých a řídkých grafových limit jsou jedním z nejdůležitějších nedávno vzniklých nástrojů diskrétní matematiky. Jejich vznik a rozvoj vedly k prolomení mnoha starých problémů v extremální teorii grafů, teorii náhodných grafů a zejména k výraznému propojení diskrétní matematiky s oblastmi jako teorie pravděpodobnosti, funkcionální analýza nebo teorie grup. Rozvoj tohoto oboru byl oceněn Fulkersonovou cenou z roku 2012, Coxeter-Jamesovou cenou z roku 2013 a cenou Davida P. Robbinse z roku 2013. V projektu bude zkoumána teorie hustých a řídkých grafových limit a související teorie nehomogenních náhodných grafů. Konkrétní problémy v teorii nehomogenních náhodných grafů zahrnují otázky klasických grafových parametrů jako je chromatické číslo či velikost nezávislé množiny. V teorii řídkých grafových limit si jako hlavní cíl klademe rozvinout chápání lokálně-globální konvergence. Cílem dále je vytvořit ucelenou teorii limit podgrafů hyperkrychlí.

Scientific branches

  • R&D category

    ZV - Basic research

  • OECD FORD - main branch

    10101 - Pure mathematics

  • OECD FORD - secondary branch

  • OECD FORD - another secondary branch

  • BA - General mathematics

Completed project evaluation

  • Provider evaluation

    U - Uspěl podle zadání (s publikovanými či patentovanými výsledky atd.)

  • Project results evaluation

    The results obtained during the project fulfil the project's main aim: developing the theory of graph limits. The outputs were published in relevant impacted journals.

Solution timeline

  • Realization period - beginning

    Jan 1, 2018

  • Realization period - end

    Dec 31, 2021

  • Project status

    U - Finished project

  • Latest support payment

    Apr 1, 2021

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

    CEP22-GA0-GJ-U

  • Data delivery date

    Jun 29, 2022

Finance

  • Total approved costs

    8,941 thou. CZK

  • Public financial support

    8,941 thou. CZK

  • Other public sources

    0 thou. CZK

  • Non public and foreign sources

    0 thou. CZK

Basic information

Recognised costs

8 941 CZK thou.

Public support

8 941 CZK thou.

100%


Provider

Czech Science Foundation

OECD FORD

Pure mathematics

Solution period

01. 01. 2018 - 31. 12. 2021