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
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
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